Número de saídas exclusivas substituindo variáveis

9

Dado um conjunto de fórmulas como este:

bacb
bcab
cbba
abbc

Forneça um algoritmo que encontre o número de resultados exclusivos que você pode obter quando cada variável for substituída por "0" ou "1" em todas as fórmulas.

Existem (k!)^2fórmulas, cada uma com 2k-1variáveis ​​e k^2termos. Expresse seus assintóticos em termos de k.

O algoritmo mais rápido vence. Em caso de empate, a solução com menor uso de memória assintótica vence. Se ainda houver empate, o primeiro post vence.

Para o exemplo acima, os seguintes resultados podem ser obtidos substituindo as variáveis:

1110, 0110, 1001, 0100, 1000, 0000, 0010, 1101, 1111, 0001, 1011, 0111

Portanto, a resposta correta é 12. Entre outras, 1010não pode ser feita usando as fórmulas acima.

Fiz mais três casos de teste, com as respectivas soluções de 230 , 12076 e 1446672 .

combinatorics fastest-algorithm orlp
fonte
Esclarecimento: o que é k na pergunta? É apenas alguma constante abstrata?
Isaacg
@isaacg Sim. É para evitar laços entre soluções que são mais rápidas para fórmulas menores, porém maiores, por exemplo.
orlp
Então cada letra a, b... é uma variável ? E sempre temos apenas um número desigual de variáveis? Não importa quanto tempo a sequência de variáveis ​​é e quantas fórmulas são dadas?
flawr
@flawr A relação exata entre o número de variáveis, número de termos e número de fórmulas é dada na pergunta.
orlp
'Can be' significa que você pode obter até $ (k!) ^ 2 $ fórmulas ou existem exatamente $ (k!) ^ 2 $ fórmulas? Além disso, você tem algum aplicativo para um algoritmo com essas especificações? Só estou perguntando, porque as especificações parecem bastante arbitrárias.
flawr

Respostas:

2

Mathematica, tempo O (k ^ 2 (k!) ^ 2)

Length[Union@@(Fold[Flatten[{StringReplace[#,#2->"0"],StringReplace[#,#2->"1"]}]&,#,Union[Characters[#]]]&/@#)]&

Espero ter calculado a complexidade do tempo corretamente. Entrada é uma lista de fórmulas como {"bacb","bcab","cbba","abbc"}. É executado em menos de 30 segundos para cada caso de teste na minha máquina, mas quem se importa com os tempos absolutos?

Explicação:

  • Primeiro, &no final a torna uma função pura, com #referência ao primeiro argumento, #2sendo o segundo argumento, etc.
  • Length[*..*] ocupa o comprimento da lista contida nela.
  • Union@@(*..*)pega a lista contida e a fornece como argumentos para Union, que retorna uma lista dos elementos exclusivos em qualquer um de seus argumentos.
  • *..*&/@#assume uma função pura e mapeia-a sobre a lista de fórmulas, para que {a,b,c}se torne {f[a],f[b],f[c]}. Observe que nas funções puras aninhadas, #nrefere-se aos seus argumentos mais internos.
  • Fold[*..*&,#,*..*]pega uma função acumuladora, valor inicial e lista, e retorna f[f[...[f[starting value,l_1],l_2],...],l_n].
  • Union[Characters[#]] pega todos os caracteres da fórmula atual e obtém todos os elementos exclusivos, fornecendo as variáveis.
  • Flatten[*..*]achata seu argumento, de modo que {{{a},b},{{c,{d}}}}se torna {a,b,c,d}.
  • {*..*,*..*}é simplesmente uma maneira de combinar os dois resultados usando o descrito acima Flatten.
  • StringReplace[#,#2->"0/1"]pega o resultado anterior e o retorna com a variável atual substituída por 0ou 1.
LegionMammal978
fonte
Por que você está usando kcomo variável no seu tempo? Ainda assim, tempo fatorial! Ufa!
theonlygusti
O op disse: "Expresse seus assintóticos em termos de k". Além disso, eu tive que fazer um GeneralUtilities`Benchmarkpara cada método usado.
LegionMammal978
Gostaria de adicionar uma descrição simples em inglês do seu algoritmo? Não estou familiarizado com o Mathematica, por isso não posso verificar sua solução.
orlp