Número máximo de substrings exclusivos de uma partição

Modifiquei o título para que fique mais compreensível.

Aqui está uma versão detalhada da pergunta:

Temos uma string s e queremos dividi-la em substrings . Cada substring é diferente um do outro. Qual é o número máximo de substrings únicos que podemos ter de um corte. Em outras palavras, qual é o número máximo de substrings exclusivos que concatenam para formar s.

aqui estão alguns exemplos:

Example 1
s = 'aababaa'
output = 4
Explain: we can split `s` 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 : scontém apenas caracteres minúsculos. Não me disseram quanto tempo se, portanto, não consigo adivinhar a complexidade do tempo ideal. :(

É um problema difícil de NP? Caso contrário, como posso resolvê-lo com eficiência?

Eu ouvi esse problema de um amigo e não consegui responder. Estou tentando usar um Trie + ganancioso para resolver esse problema. O método falha no primeiro exemplo.

Aqui está a solução Trie que eu vim com:

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

Por exemplo 1, o código acima retornará 3, uma vez que está tentando dividir sem a|ab|abaa.

Adicionar: Graças à ideia de todos, parece que esse problema está muito próximo de um problema de NP. No momento, estou tentando pensar nessa direção. Suponha que tenhamos uma função Guess(n). Esta função retornará Truese pudermos encontrar nsubstrings exclusivos de uma divisão ou Falsenão. Uma observação aqui é que se Guess(n) == True, então, Guess(i) == Truepara todos i <= n. Como podemos mesclar duas substrings adjacentes juntas. Essa observação pode levar a uma solução binária. No entanto, ainda requer que possamos calcular a Guessfunção com muita eficiência. Infelizmente, ainda não consegui descobrir uma maneira polinomial de calcular Guess(n).

Isso é conhecido como problema de partição de cadeia com detecção de colisão e é mostrado como NP-completo com uma redução de 3-SAT em um artigo de Anne Condon, Ján Maňuch e Chris Thachuk - Complexidade de um problema de partição de cadeia com detecção de colisão e sua relação ao design de oligo para síntese gênica ( International Computing and Combinatorics Conference , 265-275, 2008).

(Muito obrigado a Gilad Barkan (גלעד ברקן) por me informar sobre essa discussão.)

Deixe-me compartilhar meus pensamentos sobre esse problema de um ponto de vista puramente teórico (observe que eu também uso "fator" em vez de "subpalavra").

Penso que uma definição suficientemente formal do problema (ou problemas) considerados aqui é a seguinte:

Dada uma palavra w, encontre as palavras u_1, u_2, ..., u_k de modo que

• u_i! = u_j para cada i, j com 1 <= i <j <= ke
• u_1 u_2 ... u_k = w

Variante de maximização (queremos muitos u_i): maximize k

Variante de minimização (queremos u_i curto): minimize max {| u_i | : 1 <= i <= k}

Esses problemas se tornam problemas de decisão, fornecendo adicionalmente um B vinculado, que, de acordo com a variável "muitos fatores" ou a variável "fatores curtos", é um limite inferior em k (queremos pelo menos B fatores) ou um limite superior em max {| u_i | : 1 <= i <= k} (queremos fatores de comprimento no máximo B), respectivamente. Para falar sobre dureza NP, precisamos falar sobre problemas de decisão.

Vamos usar os termos SF para a variável "fatores curtos" e MF para a variável "muitos fatores". Em particular, e este é um ponto realmente crucial, os problemas são definidos de tal maneira que obtemos uma palavra sobre um alfabeto que não é de forma alguma restrito. A versão do problema é que sabemos a priori que apenas obtemos palavras de entrada, digamos, alfabeto {a, b, c, d} é um problema diferente! A dureza NP não transita automaticamente da variante "irrestrita" para a "alfabeto fixo" (a última pode ser mais simples).

SF e MF são problemas completos de NP. Isso foi mostrado em [1, 1b] e [2], respectivamente (como Gilad já apontou). Se eu entendi corretamente a definição do problema informal (talvez também) aqui no início desta discussão, o problema dessa discussão é exatamente o problema MF. Inicialmente, não é mencionado que as palavras são restritas a vir de algum alfabeto fixo; depois, diz-se que podemos assumir que apenas letras minúsculas são usadas. Se isso significa que consideramos apenas as palavras sobre o alfabeto fixo {a, b, c, ..., z}, isso mudaria bastante, na verdade, em termos de dureza NP.

Um olhar mais atento revela algumas diferenças na complexidade de SF e MF:

1. O artigo [1, 1b] mostra que SF permanece NP-completo se fixarmos o alfabeto em um binário (mais precisamente: obter uma palavra w sobre as letras aeb e um limite B, podemos fatorá-lo em fatores distintos de comprimento em mais B?).
2. O artigo [1, 1b] mostra que SF permanece NP-completo se fixarmos o limite B = 2 (mais precisamente: obter uma palavra w, podemos fatorá-la em fatores distintos de comprimento, no máximo 2?).
3. O artigo [3] mostra que, se o alfabeto e o limite B são fixos, o SF pode ser resolvido em tempo polinomial.
4. O artigo [2] mostra que MF é NP completo, mas apenas se o alfabeto não for restrito ou corrigido a priori! Em particular, ele não responde à pergunta se o problema é NP-completo se considerarmos apenas as palavras de entrada sobre algum alfabeto fixo (como é habitual no caso de configurações práticas).
5. O artigo [3] mostra que MF pode ser resolvido em tempo polinomial se os limites de entrada B forem novamente delimitados por alguma constante, ou seja, a entrada do problema for uma palavra e um limite B de {1, 2, ..., K} , onde K é alguma constante fixa.

Alguns comentários sobre esse resultado: Wrt (1) e (2), é intuitivamente claro que se o alfabeto é binário, então, para dificultar o problema SF, o limite B também não pode ser corrigido. Por outro lado, fixar B = 2 significa que o tamanho do alfabeto deve ser muito grande para produzir instâncias difíceis. Como conseqüência, (3) é bastante trivial (na verdade, [3] diz um pouco mais: então podemos resolvê-lo em tempo de execução não apenas polinomial, mas também | w | ^ 2 vezes um fator que depende apenas do tamanho do alfabeto e ligado B). (5) também não é difícil: se nossa palavra é longa em comparação com B, então podemos obter a fatoração desejada simplesmente dividindo fatores de diferentes comprimentos. Caso contrário, podemos forçar com força bruta todas as possibilidades, que são exponenciais apenas em B, que neste caso é assumido como uma constante.

Portanto, a imagem que temos é a seguinte: SF parece mais difícil, porque temos dureza mesmo para alfabetos fixos ou para um limite fixo B. O problema MF, por outro lado, é solucionável em tempo polivalente se o limite for fixo (em nesse sentido, é mais fácil do que SF), enquanto a pergunta correspondente indica o tamanho do alfabeto está aberto. Portanto, MF é um pouco menos complexo que SF, mesmo que MF para alfabetos fixos também seja NP-completo. No entanto, se for possível mostrar que o MF pode ser resolvido para alfabetos fixos no tempo polifólio, o MF é muito mais fácil que o SF ... porque o único caso em que é difícil é algo artificial (alfabeto ilimitado!) .

Esforcei-me ao tentar resolver o caso do MF com alfabeto delimitado, mas não consegui resolvê-lo e parei de trabalhar nele desde então. Não acredito que outros pesquisadores tenham se esforçado muito para resolvê-lo (portanto, este não é um desses problemas abertos muito difíceis, muitas pessoas já tentaram e falharam; considero-o de alguma forma factível). Meu palpite seria que também é NP-difícil para alfabetos fixos, mas talvez a redução seja tão complicada que você obteria algo como "MF é difícil para alfabetos de tamanho 35 ou maior" ou algo assim, o que também não seria muito bom .

Em relação à literatura adicional, conheço o artigo [4], que considera o problema de dividir uma palavra w em fatores distintos u_1, u_2, ..., u_k que são todos palíndromos, que também é NP completo.

Dei uma rápida olhada no artigo [5], apontado por Gilad. Parece considerar uma configuração diferente, no entanto. Neste artigo, os autores estão interessados ​​na questão combinatória de quantas subsequências ou subpalavras distintas podem estar contidas em uma determinada palavra, mas elas podem se sobrepor. Por exemplo, aaabaab contém 20 subpalavras diferentes a, b, aa, ab, ba, bb, aaa, aab, aba, baa, aaab, aaba, aba, baab, aaaba, aabaa, abaab, aabaab, aaabaa, aaabaab (talvez eu mal contado, mas você entendeu). Alguns deles têm apenas uma ocorrência, como baa, outros, como aa. De qualquer forma, a questão não é como podemos, de alguma maneira, dividir a palavra para obter muitos fatores distintos, pois isso significa que cada símbolo individual contribui para exatamente um fator.

Em relação às soluções práticas para esse tipo de problema (lembre-se de que eu sou um teórico, leve isso com um pouco de sal):

• Que eu saiba, não há limites teóricos mais baixos (como dureza NP) que descartariam resolver MF em tempo polinomial se considerarmos apenas as palavras de entrada sobre um alfabeto fixo. Porém, há uma ressalva: se você obtiver um algoritmo de politempo, ele deverá ser executado exponencialmente no número de símbolos do alfabeto fixo (ou exponencial em alguma função disso)! Caso contrário, também seria um algoritmo de tempo polinomial para o caso de alfabetos ilimitados. Sendo um teórico, eu procuraria por tarefas algorítmicas que podem ser computadas em tempo exponencial apenas se o número de símbolos e que de alguma forma ajudarem a criar um algoritmo para MF. Por outro lado, é provável que esse algoritmo não exista e MF também seja NP-hard no caso de alfabeto fixo.

• Se você estiver interessado em soluções práticas, pode ser útil aproximar a solução. Portanto, obter fatoração garantida em apenas metade do tamanho ideal, no pior dos casos, não seria tão ruim.

• Heurísticas que não fornecem uma taxa de aproximação comprovável, mas funcionam bem em um ambiente prático também seriam interessantes, eu acho.

• Transformar as instâncias do problema em instâncias SAT ou ILP não deve ser muito difícil e, em seguida, você pode executar um SAT ou ILP-Solver para obter soluções ideais.

• Minha opinião pessoal é que, embora não se saiba se o alfabeto fixo da MF é NP-difícil, há idéias teóricas suficientes que sugerem que o problema é difícil o suficiente para que seja justificado procurar soluções heurísticas etc. que funciona bem em um ambiente prático.

Bibliografia:

[1] Anne Condon, Ján Manuch, Chris Thachuk: A complexidade do particionamento de strings. J. Algoritmos Discretos 32: 24-43 (2015)

[1b] Anne Condon, Ján Manuch, Chris Thachuk: Complexidade de um problema de partição de cadeia sensível a colisões e sua relação com o Oligo Design para síntese de genes. COCOON 2008: 265-275

[2] Henning Fernau, Florin Manea, Robert Mercas e Markus L. Schmid: correspondência de padrões com variáveis: algoritmos rápidos e novos resultados de dureza. STACS 2015: 302-315

[3] Markus L. Schmid: Computando fatorações de seqüência repetitivas e sem igualdade. Theor. Comput. Sci. 618: 42-51 (2016)

[4] Hideo Bannai, Travis Gagie, Shunsuke Inenaga, Juha Kärkkäinen, Dominik Kempa, Marcin Piatkowski, Shiho Sugimoto: A fatoração palindrômica diversificada é NP-completa. Int. J. Found. Comput. Sci. 29 (2): 143-164 (2018)

[5] Abraham Flaxman, Aram Wettroth Harrow, Gregory B. Sorkin: cordas com no máximo muitas subseqüências e substrings distintas. Electr. J. Comb. 11 (1) (2004)

Aqui está uma solução, mas ela explode muito rápido e não chega nem perto de uma solução eficiente. Primeiro, divide a string em uma lista de substrings exclusivos, sem preocupação com o pedido, depois tenta usar itertools.permutation para remontar esses substrings de volta à string original, testando cada permutação para verificar se ela corresponde à string original.

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]}")

Para o primeiro teste, obtemos o seguinte:

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

Talvez isso possa ser otimizado de alguma forma, mas isso leva alguns segundos nesta máquina.

Eu tentei pensar nesse problema em termos ou fazer uma partição em um determinado índice. Portanto, essa função é recursiva e cria 2 ramificações em cada índice 1. Não particione no índice i 2. Particione no índice i.

Com base na partição, preencho um conjunto e, em seguida, retorno o tamanho do conjunto

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

Você pode usar uma função recursiva com um conjunto como um segundo parâmetro para acompanhar as seqüências exclusivas no caminho atual até o momento. Para cada recursão, itere através de todos os índices mais 1 para dividir a sequência de uma possível sequência candidata e, se a sequência candidata ainda não estiver no conjunto, faça uma chamada recursiva com a sequência restante e o candidato adicionado ao conjunto para obter o número máximo de substrings exclusivos da cadeia restante, adicione 1 a ela e retorne o máximo dos máximos das iterações. Retorne 0 se a sequência especificada estiver vazia ou todas as sequências candidatas já estiverem no conjunto:

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

Demonstração: https://repl.it/@blhsing/PriceyScalySphere

No Python 3.8, a lógica acima também pode ser escrita com uma chamada para a maxfunção com uma expressão geradora que filtra candidatos que foram "vistos" com uma expressão de atribuição:

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)

Aqui está uma resposta baseada na teoria dos grafos.

Modelagem
Esse problema pode ser modelado como um problema de conjunto independente máximo em um gráfico de tamanho da O(n²)seguinte maneira:
Seja w = c_1, ..., c_na sequência de entrada.
Let G = (V,E)ser um grafo não-dirigido, construído como se segue:
V = { (a, b) such that a,b in [1, n], a <= b }. Podemos ver que o tamanho de Vé n(n-1)/2, onde cada vértice representa uma substring de w.
Então, para cada par de vértices (a1, b1)e (a2, b2), construímos a aresta ((a1, b1), (a2, b2))iff
(i) [a1, b1]cruza [a2, b2]ou
(ii) c_a1...c_b1 = c_a2...c_b2.
Dito de outra forma, construímos uma aresta entre dois vértices se (i) os substrings que eles representam se sobrepõem wou (ii) os dois substrings são iguais.

Podemos então ver por que um conjunto máximo independente de Gfornece a resposta para o nosso problema.

Complexidade
No caso geral, o problema do conjunto independente independente (MIS) é NP-difícil, com uma complexidade temporal O(1.1996^n)e no espaço polinomial [Xiao, NamaGoshi (2017)] .
Inicialmente, pensei que o gráfico resultante seria um gráfico cordal (sem ciclo induzido de comprimento> 3), o que teria sido muito bom desde então, o problema do MIS pode ser resolvido em tempo linear nessa classe de gráficos.
Mas rapidamente percebi que não é esse o caso, é muito fácil encontrar exemplos em que há ciclos induzidos de comprimento 5 ou mais.
Na verdade, o gráfico resultante não exibe nenhuma propriedade 'agradável' que normalmente procuramos e que permite reduzir a complexidade do problema MIS para um polinomial.
Esse é apenas um limite superior da complexidade do problema, uma vez que a redução do tempo polinomial ocorre apenas em uma direção (podemos reduzir esse problema ao problema MIS, mas não o contrário, pelo menos não trivialmente). Por fim, acabamos resolvendo esse problema no O(1.1996^(n(n-1)/2))pior dos casos.
Então, infelizmente, eu não poderia provar que está em P ou que é NP-completo ou NP-difícil. Uma coisa certa é que o problema está no NP, mas acho que isso não é uma surpresa para ninguém.

Implementação
A vantagem de reduzir esse problema ao problema do MIS é que o MIS é um problema clássico, para o qual várias implementações podem ser encontradas, e que o problema do MIS também é facilmente gravado como um ILP.
Aqui está uma formulação ILP do problema MIS:

Objective function 
maximize sum(X[i], i in 1..n)
Constraints:
for all i in 1..n, X[i] in {0, 1}
for all edge (i, j), X[i] + X[j] <= 1

Na minha opinião, essa deve ser a maneira mais eficiente de resolver esse problema (usando essa modelagem como problema MIS), já que o ILP solver é incrivelmente eficiente, especialmente quando se trata de grandes instâncias.

Esta é uma implementação que fiz usando Python3 e o solucionador GLPK . Para testá-lo, você precisa de um solucionador de LP compatível com o formato de arquivo Cplex.

from itertools import combinations

def edges_from_string(w):
    # build vertices
    vertices = set((a, b) for b in range(len(w)) for a in range(b+1))
    # build edges
    edges = {(a, b): set() for (a, b) in vertices}
    for (a1, b1), (a2, b2) in combinations(edges, 2):
        # case: substrings overlap
        if a1 <= a2 <= b1:
            edges[(a1, b1)].add((a2, b2))
        if a2 <= a1 <= b2:
            edges[(a2, b2)].add((a1, b1))
        # case: equal substrings
        if w[a1:b1+1] == w[a2:b2+1]:
            if a1 < a2:
                edges[(a1, b1)].add((a2, b2))
            else:
                edges[(a2, b2)].add((a1, b1))
    return edges

def write_LP_from_edges(edges, filename):
    with open(filename, 'w') as LP_file:
        LP_file.write('Maximize Z: ')
        LP_file.write("\n".join([
            "+X%s_%s" % (a, b)
            for (a, b) in edges
        ]) + '\n')
        LP_file.write('\nsubject to \n')
        for (a1, b1) in edges:
            for (a2, b2) in edges[(a1, b1)]:
                LP_file.write(
                    "+X%s_%s + X%s_%s <= 1\n" %
                    (a1, b1, a2, b2)
                )
        LP_file.write('\nbinary\n')
        LP_file.write("\n".join([
            "X%s_%s" % (a, b)
            for (a, b) in edges.keys()
        ]))
        LP_file.write('\nend\n')
write_LP_from_edges(edges_from_string('aababaa'), 'LP_file_1')
write_LP_from_edges(edges_from_string('kzshidfiouzh'), 'LP_file_2')

Você pode resolvê-los com o glpsolcomando:
glpsol --lp LP_file_1
O aababaaproblema é resolvido rapidamente (0,02 s no meu laptop), mas, como esperado, as coisas ficam (muito) mais difíceis à medida que o tamanho da string aumenta ...
Este programa fornece apenas o valor numérico (e não a partição ideal), no entanto, a partição ideal e as substrings correspondentes podem ser encontradas com uma implementação semelhante, usando uma interface do solver LP / python, como pyomo

Tempo e memória
aababaa : 0,02 segundos, 0,4 MB, valor: 4
kzshidfiouzh: 1,4 segundos, 3,8 MB, valor: 10
aababababbababab: 60,2 segundos, 31,5 MB, valor: 8
kzshidfiouzhsdjfyu: 207,5 segundos, 55,7 MB, valor: 14
Observe que o solver LP também oferece os limites inferior e superior atuais da solução; portanto, no último exemplo, eu poderia obter a solução real como um limite inferior após um minuto.

Minha outra resposta estava intimamente relacionada, mas não correspondia exatamente a esse problema, deixando ambíguo se encontrar a maior fatoração de cadeia livre de igualdade pode ser de classe de complexidade diferente de se existe alguma fatoração livre de igualdade com comprimento de fator vinculado (o último sendo abordado pelo artigo citado).

No artigo, Correspondência de padrões com variáveis: algoritmos rápidos e novos resultados de dureza (Henning Fernau, Florin Manea, Robert Mercaş e Markus L. Schmid, no Proc. 32º Simpósio sobre Aspectos Teóricos da Ciência da Computação, STACS 2015, volume 30 de Leibniz International Proceedings in Informatics (LIPIcs) , páginas 302-315, 2015), os autores mostram que é NP-completo decidir, para um determinado número ke uma palavra w, se wpode ser fatorado em kfatores distintos.

Se considerarmos templatetypedef do comentário , o que implica que pode haver uma solução em tempo polinomial para o maior factorisation irrestrita, livre de igualdade, então certamente nós poderíamos usar um algoritmo como a resposta se pudéssemos dividir a string em kfatores distintos (substrings), simplesmente observando se ké menor que o máximo que já sabemos.

Schmid (2016), no entanto, escreve que "ainda é um problema em aberto se o MaxEFF-s permanece NP-completo se o alfabeto for corrigido". (Computação de fatorações de igualdade repetitivas e livres de igualdade, Theoretical Computer Science Volume 618 , 7 de março de 2016, páginas 42-51)

O Tamanho Máximo de Fatorização Sem Igualdade (MaxEFF-s) ainda é parametrizado e é definido como:

Instância: A palavra we um número m, 1 ≤ m ≤ |w|.

Pergunta: Será que não existe um livre de igualdade factorisation p de wcom s(p) ≥ m? ( s(p)sendo o tamanho da fatoração).