Количество уникальных выходов путем подстановки переменных

9

Дан набор формул, подобных этому:

bacb
bcab
cbba
abbc

Дайте алгоритм, который находит количество уникальных результатов, которые вы можете получить, когда каждая переменная заменяется на «0» или «1» в каждой формуле.

Есть (k!)^2формулы, каждая с 2k-1переменными и k^2терминами. Выразите свою асимптотику в терминах k.

Самый быстрый алгоритм выигрывает. В случае ничьей выигрывает решение с меньшим использованием асимптотической памяти. Если это все еще ничья, первый пост выигрывает.

Для приведенного выше примера можно получить следующие результаты, подставив переменные:

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

Таким образом, правильный ответ - 12. Среди прочего, 1010нельзя сделать, используя приведенные выше формулы.

Я сделал еще три теста с соответствующими решениями 230 , 12076 и 1446672 .

combinatorics fastest-algorithm orlp
источник
Пояснение: что такое k в вопросе? Это просто какая-то абстрактная константа?
Исаак
@isaacg Да. Например, для предотвращения связей между решениями, которые быстрее для меньших, но более крупных формул.
orlp
Таким образом, каждая буква a, b... является переменной ? А у нас всегда только неравномерное количество переменных? Не имеет значения, какова длина последовательности переменных и сколько формул вам дано?
flawr
@flawr Точное соотношение между числом переменных, количеством слагаемых и количеством формул приведено в вопросе.
orlp
Означает ли «может быть», что вы можете получить до $ (k!) ^ 2 $ формул или есть в точности $ (k!) ^ 2 $ формул? Кроме того, есть ли у вас приложение для алгоритма с этими спецификациями? Я просто спрашиваю, потому что спецификации кажутся довольно произвольными.
flawr

Ответы:

2

Mathematica, O (k ^ 2 (k!) ^ 2) время

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

Надеюсь, я правильно рассчитал сложность времени. Ввод представляет собой список формул, таких как {"bacb","bcab","cbba","abbc"}. Запускается менее чем за 30 секунд для каждого теста на моей машине, но кого волнует абсолютное время?

Объяснение:

  • Во-первых, &в конце делает его чистой функцией, #ссылаясь на первый аргумент, #2являясь вторым аргументом и т. Д.
  • Length[*..*] берет длину списка, содержащегося в нем.
  • Union@@(*..*)берет содержащийся список и предоставляет его в качестве аргументов для Union, который возвращает список уникальных элементов в любом из своих аргументов.
  • *..*&/@#берет чистую функцию и отображает ее в списке формул, так что {a,b,c}становится {f[a],f[b],f[c]}. Обратите внимание, что во вложенных чистых функциях #nссылается на свои внутренние аргументы.
  • Fold[*..*&,#,*..*]принимает функцию аккумулятора, начальное значение, список и возвращает f[f[...[f[starting value,l_1],l_2],...],l_n].
  • Union[Characters[#]] берет все символы в текущей формуле и получает все уникальные элементы, давая нам переменные.
  • Flatten[*..*]сглаживает свой аргумент, так что {{{a},b},{{c,{d}}}}становится {a,b,c,d}.
  • {*..*,*..*}это просто способ объединить два результата, используя выше Flatten.
  • StringReplace[#,#2->"0/1"]принимает предыдущий результат и возвращает его с заменой текущей переменной либо на, 0либо на 1.
LegionMammal978
источник
Почему вы используете kв качестве переменной в свое время? Все-таки факториальное время! Уф!
theonlygusti
Оператор сказал: «Выразите свою асимптотику в терминах k». Кроме того, я должен был сделать GeneralUtilities`Benchmarkдля каждого используемого метода.
LegionMammal978
Хотите добавить простое английское описание вашего алгоритма? Я не знаком с Mathematica, поэтому не могу проверить ваше решение.
orlp