Nombre de sorties uniques en substituant des variables

9

Étant donné un ensemble de formules comme ceci:

bacb
bcab
cbba
abbc

Donnez un algorithme qui trouve le nombre de résultats uniques que vous pouvez obtenir lorsque chaque variable est remplacée par "0" ou "1" dans chaque formule.

Il existe des (k!)^2formules, chacune avec des 2k-1variables et des k^2termes. Exprimez vos asymptotiques en termes de k.

L'algorithme le plus rapide gagne. En cas d'égalité, la solution avec une utilisation asymptotique de la mémoire plus faible l'emporte. Si c'est toujours une égalité, le premier post l'emporte.

Pour l'exemple ci-dessus, les résultats suivants peuvent être obtenus en remplaçant les variables:

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

Donc, la bonne réponse est 12. Entre autres, 1010ne peut pas être faite en utilisant les formules ci-dessus.

J'ai fait trois autres cas de tests, avec des solutions respectives de 230 , 12076 et 1446672 .

combinatorics fastest-algorithm orlp
la source
Clarification: qu'est-ce que k dans la question? Est-ce juste une constante abstraite?
isaacg
@isaacg Oui. C'est pour éviter des liens entre des solutions plus rapides pour des formules moins grandes mais plus grandes, par exemple.
orlp
Donc , chaque lettre a, b... est une variable de ? Et nous n'avons toujours qu'un nombre inégal de variables? Peu importe la longueur de la séquence de variables et le nombre de formules qui vous sont données?
flawr
@flawr La relation exacte entre le nombre de variables, le nombre de termes et le nombre de formules est donnée dans la question.
orlp
Est-ce que «peut être» signifie que vous pouvez obtenir jusqu'à $ (k!) ^ 2 $ formules ou existe-t-il exactement des formules $ (k!) ^ 2 $? En plus de cela, avez-vous une application pour un algorithme avec ces spécifications? Je demande juste parce que les spécifications semblent assez arbitraires.
flawr

Réponses:

2

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

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

J'espère que j'ai calculé correctement la complexité du temps. L'entrée est une liste de formules telles que {"bacb","bcab","cbba","abbc"}. Fonctionne en moins de 30 secondes pour chaque test sur ma machine, mais qui se soucie des temps absolus?

Explication:

  • Tout d'abord, le &à la fin en fait une fonction pure, avec #référence au premier argument, #2étant le deuxième argument, etc.
  • Length[*..*] prend la longueur de la liste contenue à l'intérieur.
  • Union@@(*..*)prend la liste contenue et la fournit comme arguments pour Union, ce qui renvoie une liste des éléments uniques dans l'un de ses arguments.
  • *..*&/@#prend une fonction pure et la mappe sur la liste des formules, ce qui {a,b,c}devient {f[a],f[b],f[c]}. Notez que dans les fonctions pures imbriquées, #nfait référence à ses arguments les plus intimes.
  • Fold[*..*&,#,*..*]prend une fonction d'accumulateur, une valeur de départ et une liste et retourne f[f[...[f[starting value,l_1],l_2],...],l_n].
  • Union[Characters[#]] prend tous les caractères de la formule actuelle et obtient tous les éléments uniques, en nous donnant les variables.
  • Flatten[*..*]aplatit son argument, ce qui {{{a},b},{{c,{d}}}}devient {a,b,c,d}.
  • {*..*,*..*}est simplement un moyen de combiner les deux résultats en utilisant ce qui précède Flatten.
  • StringReplace[#,#2->"0/1"]prend le résultat précédent et le renvoie avec la variable courante remplacée par 0ou 1.
LegionMammal978
la source
Pourquoi utilisez-vous kcomme variable dans votre temps? Pourtant, le temps factoriel! Phew!
theonlygusti
L'op a dit: "Exprimez vos asymptotiques en termes de k." De plus, j'ai dû faire un GeneralUtilities`Benchmarkpour chaque méthode utilisée.
LegionMammal978
Voulez-vous ajouter une description en anglais simple de votre algorithme? Je ne connais pas Mathematica, donc je ne peux pas vérifier votre solution.
orlp