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

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

Liczba unikalnych wyników przez podstawienie zmiennych

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

Wyjaśnienie: