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




algorithm (5)

Modificado o título um pouco para torná-lo mais compreensível.

Aqui está a versão detalhada. Supondo que temos uma string s , queremos dividi-la em algumas substrings . Cada substring é diferente um do outro. Qual é o número máximo de substrings exclusivos que podemos ter de um corte. Em outras palavras, você pode recuperar s concatenando essas substrings.

aqui estão alguns exemplos:

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 contém apenas caracteres minúsculos. Não sei quanto tempo s é o que me faz não conseguir adivinhar a complexidade do tempo ideal. :(

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

Eu ouvi esse problema de um amigo meu. E eu não consegui tirá-lo. Estou tentando usar um Trie + ganancioso para resolver esse problema. Mas 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, pois está tentando dividi-lo em a|ab|abaa .

Adicione: Obrigado a 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á True se pudermos encontrar n substrings exclusivos de uma divisão ou False caso contrário. Uma observação aqui é que, se Guess(n) == True , Guess(i) == True para 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 função Guess muito eficiente. Infelizmente, ainda não consegui descobrir uma maneira polinomial de calcular Guess(n) .


(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").

Eu acho 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 palavras sobre o alfabeto fixo {a, b, c, ..., z}, então 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 está completo como NP 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, 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, 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 B. fixo. O problema MF, por outro lado, fica solucionável em polí-tempo se o limite for fixo (em nesse sentido, é mais fácil 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, abaa, 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 forma, 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 existem limites teóricos inferiores (como dureza NP) que descartariam a resolução de 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 sem limites. 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, na pior das hipóteses, 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 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: Diversas fatorações palindrômicas são NP-completas. 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 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 O(n²) seguinte maneira:
Seja w = c_1, ..., c_n a sequência de entrada.
Seja G = (V,E) um gráfico não direcionado, construído da seguinte maneira:
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)) se
(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 em w ou (ii) os dois substrings são iguais.

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

Complexidade
No caso geral, o problema do conjunto independente independente (MIS) é NP-difícil, com uma complexidade temporal de O(1.1996^n) e no espaço polinomial [Xiao, NamaGoshi (2017)] .
A princípio, 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 geralmente procuramos e que permite reduzir a complexidade do problema do MIS a um polinômio.
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 do MIS, mas não o contrário, pelo menos não trivialmente). Então, finalmente, resolvemos esse problema em O(1.1996^(n(n-1)/2)) no pior dos casos.
Então, infelizmente, não pude provar que ele esteja em P ou que seja 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 comando glpsol :
glpsol --lp LP_file_1
O aababaa é resolvido rapidamente (0,02 s no meu laptop), mas como esperado, as coisas ficam (muito) mais difíceis à medida que o tamanho da corda cresce ....
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 do 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 solucionador de 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.


Eu tentei e pensei sobre esse problema em termos ou se deseja 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


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).


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 função max 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)




algorithm