Liczba unikalnych wyników przez podstawienie zmiennych

9

Biorąc pod uwagę zestaw takich wzorów:

bacb
bcab
cbba
abbc

Podaj algorytm, który wyszukuje liczbę unikalnych wyników, które można uzyskać, gdy każda zmienna jest zamieniana na „0” lub „1” w każdej formule.

Istnieją (k!)^2formuły, każda ze 2k-1zmiennymi i k^2terminami. Wyraź swoją asymptotykę pod względem k.

Najszybszy algorytm wygrywa. W przypadku remisu wygrywa rozwiązanie o niższym zużyciu pamięci asymptotycznej. Jeśli nadal jest remis, wygrywa pierwszy post.

W powyższym przykładzie można uzyskać następujące wyniki, zastępując zmienne:

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

Tak więc poprawna odpowiedź to 12. Między innymi, 1010nie można dokonać przy użyciu powyższych wzorów.

Zrobiłem jeszcze trzy przypadki testowe z odpowiednimi rozwiązaniami 230 , 12076 i 1446672 .

combinatorics fastest-algorithm orlp
źródło
Wyjaśnienie: o co chodzi w pytaniu? Czy to tylko jakaś abstrakcyjna stała?
isaacg
@isaacg Tak. Ma to na celu zapobieganie powiązaniom między rozwiązaniami, które są szybsze, na przykład dla mniejszych, ale większych formuł.
orlp
Więc każdej litery a, b... jest zmienna ? I zawsze mamy tylko nierówną liczbę zmiennych? Czy nie ma znaczenia, jak długa jest sekwencja zmiennych i ile otrzymujesz wzorów ?
flawr
@flawr Dokładne powiązanie między liczbą zmiennych, liczbą terminów i liczbą wzorów podano w pytaniu.
orlp
Czy „może być” oznacza, że ​​możesz dostać formuły do $ (k!) ^ 2 $, czy są dokładnie formuły $ (k!) ^ 2 $? Poza tym, czy masz jakieś zastosowanie algorytmu o tych specyfikacjach? Pytam tylko, ponieważ specyfikacje wydają się dość arbitralne.
flawr

Odpowiedzi:

2

Matematyka, czas O (k ^ 2 (k!) ^ 2)

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

Mam nadzieję, że poprawnie obliczyłem złożoność czasu. Dane wejściowe to lista formuł takich jak {"bacb","bcab","cbba","abbc"}. Działa w mniej niż 30 sekund dla każdego przypadku testowego na mojej maszynie, ale kogo to obchodzi o czasach bezwzględnych?

Wyjaśnienie:

  • Po pierwsze, &na końcu sprawia, że ​​jest to czysta funkcja, w #odniesieniu do pierwszego argumentu, #2będącego drugim argumentem itp.
  • Length[*..*] przyjmuje długość zawartej w nim listy.
  • Union@@(*..*)pobiera zawartą listę i dostarcza ją jako argumenty Union, co zwraca listę unikalnych elementów w dowolnym z jej argumentów.
  • *..*&/@#przyjmuje czystą funkcję i mapuje ją na liście formuł, dzięki czemu {a,b,c}staje się {f[a],f[b],f[c]}. Zauważ, że w zagnieżdżonych funkcjach czystych #nodwołuje się do najbardziej wewnętrznych argumentów.
  • Fold[*..*&,#,*..*]pobiera funkcję akumulatora, wartość początkową i listę, i zwraca f[f[...[f[starting value,l_1],l_2],...],l_n].
  • Union[Characters[#]] pobiera wszystkie znaki z bieżącej formuły i pobiera wszystkie unikalne elementy, podając nam zmienne.
  • Flatten[*..*]spłaszcza argument, więc {{{a},b},{{c,{d}}}}staje się {a,b,c,d}.
  • {*..*,*..*}jest po prostu sposobem na połączenie dwóch wyników przy użyciu powyższego Flatten.
  • StringReplace[#,#2->"0/1"]trwa poprzedni wynik i zwraca go z bieżącej zmiennej zastąpione albo 0albo 1.
LegionMammal978
źródło
Dlaczego używasz kjako zmiennej w swoim czasie? Mimo to czas czynnikowy! Uff!
theonlygusti
Op powiedział: „Wyraź swoją asymptotykę pod względem k”. Musiałem też zrobić GeneralUtilities`Benchmarkdla każdej użytej metody.
LegionMammal978
Chcesz dodać zwykły angielski opis swojego algorytmu? Nie znam matematyki, więc nie mogę zweryfikować twojego rozwiązania.
lub