python - Numero massimo di sottostringhe univoche da una partizione




algorithm (5)

Modificato un po 'il titolo per renderlo più comprensibile.

Ecco la versione dettagliata. Supponiamo di avere una stringa s , vogliamo dividerla in alcune sottostringhe . Ogni sottostringa è diversa l'una dall'altra. Qual è il numero massimo di sottostringhe uniche che possiamo avere da un taglio. In altre parole, è possibile recuperare s concatenando quelle sottostringhe.

Ecco alcuni esempi:

Example 1
s = 'aababaa'
output = 4
Explain: we can split it into aa|b|aba|a or aab|a|b|aa, 
         and 4 is the max number of substrings we can get from one split.

Example 2
s = 'aba'
output = 2
Explain: a|ba

Example 3
s = 'aaaaaaa'
output = 3
Explain: a|aa|aaaa

Nota : s contiene solo caratteri minuscoli. Non sono sicuro di quanto sia lunga la s che non può indovinare la complessità temporale ottimale. :(

È un problema NP-difficile? In caso contrario, come risolverlo in modo efficiente?

Ho sentito questo problema da uno dei miei amici. E non sono riuscito a tirarlo fuori. Sto cercando di usare un avido Trie + per risolvere questo problema. Ma fallisce nel primo esempio.

Ecco la soluzione trie che mi è venuta in mente:

def triesolution(s):
    trie = {}
    p = trie
    output = 0
    for char in s:
        if char not in p:
            output += 1
            p[char] = {}
            p = trie
        else:
            p = p[char]
    return output

Ad esempio 1, il codice sopra restituirà 3, poiché sta cercando di dividerlo in a|ab|abaa .

Aggiungi: Grazie all'idea di tutti, sembra che questo problema sia molto vicino a un problema NP. In questo momento, sto provando a pensarlo da questa direzione. Supponiamo di avere una funzione Guess(n) . Questa funzione restituirà True se potessimo trovare n sottostringhe univoche da una divisione o False contrario. Un'osservazione qui è che se Guess(n) == True , allora Guess(i) == True per tutti i <= n . Dal momento che possiamo unire insieme due sottostringhe adiacenti. Questa osservazione può portare a una soluzione binaria. Tuttavia, richiede ancora che possiamo calcolare la funzione Guess modo molto efficiente. Purtroppo, non riuscivo ancora a trovare un modo polinomiale per calcolare Guess(n) .


È possibile utilizzare una funzione ricorsiva con un set come secondo parametro per tenere traccia delle stringhe univoche nel percorso corrente finora. Per ogni ricorsione, scorrere tutti gli indici più 1 in corrispondenza del quale dividere la stringa per una possibile stringa candidata e, se la stringa candidata non è ancora nell'insieme, effettuare una chiamata ricorsiva con la stringa rimanente e il candidato aggiunto all'insieme per ottenere il numero massimo di sottostringhe univoche dalla stringa rimanente, aggiungere 1 ad essa e restituire il massimo dei massimi dalle iterazioni. Restituisce 0 se la stringa specificata è vuota o tutte le stringhe candidate sono già nel set:

def max_unique_substrings(s, seen=()):
    maximum = 0
    for i in range(1, len(s) + 1):
        candidate = s[:i]
        if candidate not in seen:
            maximum = max(maximum, 1 + max_unique_substrings(s[i:], {candidate, *seen}))
    return maximum

Demo: https://repl.it/@blhsing/PriceyScalySphere

In Python 3.8, la logica di cui sopra può anche essere scritta con una chiamata alla funzione max con un'espressione del generatore che filtra i candidati che sono stati "visti" con un'espressione di assegnazione:

def max_unique_substrings(s, seen=()):
    return max((1 + max_unique_substrings(s[i:], {candidate, *seen}) for i in range(1, len(s) + 1) if (candidate := s[:i]) not in seen), default=0)

(Mille grazie a Gilad Barkan (גלעד ברקן) per avermi reso consapevole di questa discussione.)

Consentitemi di condividere le mie opinioni su questo problema da un punto di vista puramente teorico (si noti che uso anche "fattore" anziché "parola chiave").

Penso che una definizione sufficientemente formale del problema (o dei problemi) considerata qui sia la seguente:

Data una parola w, trova parole u_1, u_2, ..., u_k tali

  • u_i! = u_j per ogni i, j con 1 <= i <j <= k e
  • u_1 u_2 ... u_k = w

Variante di massimizzazione (ne vogliamo molti u_i): massimizza k

Variante di minimizzazione (vogliamo breve u_i): minimizzare max {| u_i | : 1 <= i <= k}

Questi problemi diventano problemi di decisione dando inoltre un limite B, che, a seconda che si parli della variante "molti fattori" o della variante "fattori corti", è un limite inferiore di k (vogliamo almeno B fattori) o un limite superiore su max {| u_i | : 1 <= i <= k} (vogliamo fattori di lunghezza al massimo B), rispettivamente. Per parlare di durezza NP, dobbiamo parlare di problemi decisionali.

Usiamo i termini SF per la "variante di fattori corti" e MF per la "variante di molti fattori". In particolare, e questo è un punto davvero cruciale, i problemi sono definiti in modo tale da ottenere una parola su qualche alfabeto che non è in alcun modo limitato. La versione del problema è che sappiamo a priori che abbiamo solo parole di input, diciamo, alfabeto {a, b, c, d} è un problema diverso! La durezza NP non passa automaticamente dalla variante "senza restrizioni" a quella "alfabeto fisso" (quest'ultima potrebbe essere più semplice).

Sia SF che MF sono problemi NP-completi. Questo è stato mostrato in [1, 1b] e [2], rispettivamente (come Gilad ha già sottolineato). Se capisco correttamente (forse troppo) la definizione di problema informale qui all'inizio di questa discussione, allora il problema di questa discussione è esattamente il problema MF. Inizialmente non si dice che le parole siano limitate a provenire da qualche alfabeto fisso, in seguito si dice che possiamo usare solo lettere minuscole. Se ciò significa che consideriamo solo le parole sull'alfabeto fisso {a, b, c, ..., z}, allora questo cambierebbe molto in termini di durezza NP.

Uno sguardo più ravvicinato rivela alcune differenze nella complessità di SF e MF:

  1. il documento [1, 1b] mostra che SF rimane NP-completo se fissiamo l'alfabeto a uno binario (più precisamente: ottenendo una parola w sulle lettere a e b e un bordo B, possiamo fattorizzarlo in distinti fattori di lunghezza a più B?).
  2. il documento [1, 1b] mostra che SF rimane NP-completo se fissiamo il limite B = 2 (più precisamente: ottenendo una parola w, possiamo fattorizzarla in distinti fattori di lunghezza al massimo 2?).
  3. la carta [3] mostra che se sia l'alfabeto che il B legato sono fissi, allora SF può essere risolto in tempo polinomiale.
  4. paper [2] mostra che MF è NP-completo, ma solo se l'alfabeto non è limitato o risolto a priori! In particolare, non risponde alla domanda se il problema è NP-completo se consideriamo le parole di input solo su un alfabeto fisso (come al solito nelle impostazioni pratiche).
  5. la carta [3] mostra che MF può essere risolto in tempo polinomiale se i limiti di input B sono di nuovo delimitati da una costante, ovvero, l'input del problema è una parola e un limite B da {1, 2, ..., K} , dove K è una costante fissa.

Alcuni commenti su questi risultati: Wrt (1) e (2), è intuitivamente chiaro che se l'alfabeto è binario, quindi, per rendere difficile il problema SF, anche il limite B non può essere risolto. Al contrario, la correzione di B = 2 significa che la dimensione dell'alfabeto deve diventare piuttosto grande per produrre casi difficili. Di conseguenza, (3) è piuttosto banale (in effetti, [3] dice leggermente di più: possiamo quindi risolverlo in tempo di esecuzione non solo polinomiale, ma anche | w | ^ 2 volte un fattore che dipende solo dalla dimensione dell'alfabeto e legato B). (5) non è difficile: se la nostra parola è lunga rispetto a B, allora possiamo ottenere la fattorizzazione desiderata semplicemente tagliando in fattori di diversa lunghezza. Altrimenti, possiamo forzare tutte le possibilità, che è esponenziale solo in B, che in questo caso si presume sia una costante.

Quindi l'immagine che abbiamo è la seguente: SF sembra più difficile, perché abbiamo durezza anche per alfabeti fissi o per un limite fisso B. Il problema MF, d'altra parte, diventa risolvibile in poli-tempo se il limite è fisso (in a questo proposito è più semplice di SF), mentre la domanda corrispondente indica la dimensione dell'alfabeto è aperta. Quindi MF è leggermente meno complesso di SF, anche se risulta che anche MF per alfabeti fissi è NP-completo. Tuttavia, se si può dimostrare che MF può essere risolto per alfabeti fissi in tempi polifunzionali, allora MF viene mostrato molto più facile di SF ... perché l'unico caso per il quale è difficile è un po 'artificiale (alfabeto illimitato!) .

Ho fatto uno sforzo per cercare di risolvere il caso di MF con alfabeto limitato, ma non sono stato in grado di risolverlo e da allora ho smesso di lavorarci. Non credo che altri ricercatori abbiano cercato molto duramente di risolverlo (quindi questo non è uno di questi problemi aperti molto difficili, molte persone hanno già provato e fallito; lo considero in qualche modo fattibile). La mia ipotesi sarebbe che sia anche NP-difficile per alfabeti fissi, ma forse la riduzione è così complicata che otterresti qualcosa del tipo "MF è difficile per alfabeti di dimensioni 35 o più grandi" o qualcosa del genere, che non sarebbe neanche molto bello .

Per quanto riguarda ulteriormente la letteratura, conosco il documento [4], che considera il problema di dividere una parola w in fattori distinti u_1, u_2, ..., u_k che sono tutti palindromi, che è anche NP-completo.

Ho dato una rapida occhiata al foglio [5], sottolineato da Gilad. Sembra considerare un ambiente diverso, però. In questo articolo, gli autori sono interessati alla domanda combinatoria di quante sottosequenze o parole chiave distinte possono essere contenute in una determinata parola, ma queste possono sovrapporsi. Ad esempio, aaabaab contiene 20 diverse parole chiave a, b, aa, ab, ba, bb, aaa, aab, aba, baa, aaab, aaba, abaa, baab, aaaba, aabaa, abaab, aabaab, aaabaa, aaabaab (forse I contato male, ma hai avuto l'idea). Alcuni di essi hanno un solo evento, come baa, alcuni diversi, come aa. In ogni caso, la domanda non è come possiamo in qualche modo dividere la parola per ottenere molti fattori distinti, dal momento che ciò significa che ogni singolo simbolo contribuisce esattamente a un fattore.

Per quanto riguarda le soluzioni pratiche a questo tipo di problemi (tieni presente che sono un teorico, quindi prendi questo con granello di sale):

  • Per quanto ne sappia, non esistono limiti teorici inferiori (come la durezza NP) che escluderebbero la risoluzione di MF in tempo polinomiale se consideriamo solo le parole di input su un alfabeto fisso. C'è un avvertimento, però: se si ottiene un algoritmo poly-time, questo dovrebbe essere eseguito in modo esponenziale nel numero di simboli dell'alfabeto fisso (o esponenziale in alcune funzioni di questo)! Altrimenti sarebbe anche un algoritmo temporale polinomiale per il caso di alfabeti illimitati. Quindi, essendo un teorico, sarei alla ricerca di compiti algoritmici che possono essere calcolati in tempo esponenziale solo se il numero di simboli e che in qualche modo aiutano a escogitare un algoritmo per MF. D'altra parte, è probabile che un tale algoritmo non esista e che MF sia anche NP-difficile nel caso dell'alfabeto fisso.

  • Se sei interessato a soluzioni pratiche, potrebbe essere utile approssimare la soluzione. Quindi ottenere fattorizzazione che è garantita solo la metà dell'ottimale nel peggiore dei casi non sarebbe male.

  • Anche l'euristica che non fornisce un rapporto di approssimazione dimostrabile, ma che funziona bene in un contesto pratico sarebbe interessante, immagino.

  • Trasformare le istanze problematiche in istanze SAT o ILP non dovrebbe essere troppo difficile e quindi è possibile eseguire un solutore SAT o ILP per ottenere anche soluzioni ottimali.

  • La mia opinione personale è che anche se non è noto se il caso dell'alfabeto fisso di MF sia NP-difficile, ci sono abbastanza intuizioni teoriche che suggeriscono che il problema è abbastanza difficile da giustificare la ricerca di soluzioni euristiche ecc. Che funziona bene in un ambiente pratico.

Bibliografia:

[1] Anne Condon, Ján Manuch, Chris Thachuk: La complessità del partizionamento delle stringhe. J. Discrete Algorithms 32: 24-43 (2015)

[1b] Anne Condon, Ján Manuch, Chris Thachuk: Complessità di un problema di partizione di stringa consapevole della collisione e relativo rapporto con Oligo Design per la sintesi genica. COCOON 2008: 265-275

[2] Henning Fernau, Florin Manea, Robert Mercas, Markus L. Schmid: pattern matching con variabili: algoritmi veloci e nuovi risultati di durezza. STACS 2015: 302-315

[3] Markus L. Schmid: calcolo delle fattorizzazioni di stringhe ripetitive e prive di uguaglianza. Theor. Comput. Sci. 618: 42-51 (2016)

[4] Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski, Shiho Sugimoto: la diversa fattorizzazione palindromica è NP-completa. Int. J. Found. Comput. Sci. 29 (2): 143-164 (2018)

[5] Abraham Flaxman, Aram Wettroth Harrow, Gregory B. Sorkin: stringhe con sequenze e sottostringi distinti al massimo. Elettr. J. Comb. 11 (1) (2004)


Ecco una soluzione, ma esplode molto velocemente e non è vicino a una soluzione efficiente. Per prima cosa suddivide la stringa in un elenco di sottostringhe univoche senza preoccupazioni per l'ordinamento, quindi tenta di utilizzare itertools.permutation per riassemblare quelle sottostringhe nella stringa originale, testando OGNI permutazione per vedere se corrisponde alla stringa originale.

import itertools as it

def splitter(seq):                                                             
    temp = [seq]
    for x in range(1, len(seq)):
        print(seq[:x], seq[x:])
        temp.append(seq[:x])
        temp.append(seq[x:])
    return temp

if __name__ == "__main__":
    test = input("Enter a string: ")
    temp = splitter(test)
    copy = temp[::]
    condition = True
    for x in temp:
        if len(x) > 1:
            copy.extend(splitter(x))
    copy = sorted(list(set(copy)))
    print(copy)
    count = []
    for x in range(len(test)):
        item = it.permutations(copy, x)
        try:
            while True:
                temp = next(item)
                if "".join(list(temp)) == test:
                    if len(temp) == len(set(temp)):
                        count.append((len(temp), temp))
        except StopIteration:
            print('next permutation begin iteration')
            continue
    print(f"All unique splits: {count}")
    print(f"Longest unique split : {max(count)[0]}")

Per il primo test otteniamo questo:

All unique splits: [(1, ('aababaa',)), (2, ('a', 'ababaa')), (2, ('aa', 'babaa')), (2, 
('aab', 'abaa')), (2, ('aaba', 'baa')), (2, ('aabab', 'aa')), (2, ('aababa', 'a')), (3, 
('a', 'ab', 'abaa')), (3, ('a', 'aba', 'baa')), (3, ('a', 'abab', 'aa')), (3, ('aa', 'b',
 'abaa')), (3, ('aa', 'ba', 'baa')), (3, ('aa', 'baba', 'a')), (3, ('aab', 'a', 'baa')),
 (3, ('aab', 'ab', 'aa')), (3, ('aab', 'aba', 'a')), (3, ('aaba', 'b', 'aa')), (3,
 ('aaba', 'ba', 'a')), (4, ('a', 'aba', 'b', 'aa')), (4, ('aa', 'b', 'a', 'baa')), (4,
 ('aa', 'b', 'aba', 'a')), (4, ('aab', 'a', 'b', 'aa'))]
Longest unique split : 4

Forse questo può essere ottimizzato in qualche modo, ma ci vogliono alcuni secondi su questa macchina.


Ho provato questo problema e ci ho pensato in termini o se creare una partizione in un determinato indice. Quindi questa funzione è ricorsiva e crea 2 rami in ciascun indice 1. Non partizionare all'indice i 2. Partizione all'indice i.

In base alla partizione compilo un set e quindi restituisco la dimensione del set

def max(a,b):
    if a>b: return a
    return b



def keep(last, current, inp, map):
    # print last
    # print current
    # print map

    if len(inp) == 2 :
        if inp[0]==inp[1]: return 1
        return 2

    if current >= len(inp):
        return len(map)
    // This is when we are at the start of the string. 
    // In this case we can only do one thing not partition and thus take the entire string as a possible string.

    if current == last :
        map11 = map.copy()
        map11.add(inp[current:])
        return keep(last, current + 1, inp, map11)

    map1 = map.copy();
    if current != (len(inp)-1):
        map1.add(inp[last:current])

    map2 = map.copy()

    return max(keep(last,current+1,inp, map2), keep(current, current+1, inp, map1))

print keep(0,0,"121", set([]))
print keep(0,0,"aaaaaaa", set([]))
print keep(0,0,"aba", set([]))
print keep(0,0,"aababaa", set([]))
print keep(0,0,"21", set([]))
print keep(0,0,"22", set([]))

https://onlinegdb.com/HJynWw-iH


Questo è noto come il problema della partizione di stringa sensibile alle collisioni e viene mostrato come NP completo da una riduzione da 3-SAT in un articolo di Anne Condon, Ján Maňuch e Chris Thachuk - Complessità di un problema di partizione di stringa sensibile alle collisioni e relazione con la progettazione dell'oligo per la sintesi genica ( Conferenza internazionale di informatica e combinatoria , 265-275, 2008).







algorithm