Cykliczne słowa
Opis problemu
Możemy myśleć o cyklicznym słowie jak o słowie wpisanym w okrąg. Aby przedstawić słowo cykliczne, wybieramy dowolną pozycję początkową i odczytujemy znaki w kolejności zgodnej z ruchem wskazówek zegara. Tak więc „obraz” i „turepik” są reprezentacjami tego samego cyklicznego słowa.
Otrzymujesz słowo String [], którego każdy element jest wyrazem słowa cyklicznego. Zwraca liczbę różnych reprezentowanych słów cyklicznych.
Najszybsze wygrane (Big O, gdzie n = liczba znaków w ciągu)
word-puzzle
counting
fastest-algorithm
jajowate
źródło
źródło
Odpowiedzi:
Pyton
Oto moje rozwiązanie. Myślę, że nadal może to być O (n 2 ), ale myślę, że średni przypadek jest znacznie lepszy.
Zasadniczo działa to poprzez normalizację każdego łańcucha, aby każdy obrót miał tę samą formę. Na przykład:
Normalizacja polega na szukaniu minimalnego znaku (według kodu char) i obracaniu łańcucha, aby znak znalazł się na ostatniej pozycji. Jeśli ten znak występuje więcej niż jeden raz, wówczas używane są znaki po każdym wystąpieniu. Daje to każdemu cyklicznemu słowu reprezentację kanoniczną, którą można wykorzystać jako klucz na mapie.
Normalizacja wynosi n 2 w najgorszym przypadku (gdzie np. Każdy znak w ciągu jest taki sam
aaaaaa
), ale przez większość czasu będzie tylko kilka wystąpień, a czas działania będzie bliższyn
.Na moim laptopie (dwurdzeniowy Intel Atom @ 1,66 GHz i 1 GB pamięci RAM) uruchomienie tego
/usr/share/dict/words
(234 937 słów o średniej długości 9,5 znaków) zajmuje około 7,6 sekundy.źródło
Znowu Python (3)
Metodą, którą zastosowałem, było obliczenie wartości skrótu każdego słowa, zaczynając od każdego znaku w ciągu; ponieważ jest to ciągły skrót, obliczenie wszystkich n skrótów zajmuje O (n) (gdzie n jest długością słowa). Łańcuch jest traktowany jako liczba podstawowa 1114112, co zapewnia unikalność skrótów. (Jest to podobne do rozwiązania Haskell, ale bardziej wydajne, ponieważ przechodzi przez ciąg tylko dwa razy).
Następnie dla każdego słowa wejściowego algorytm sprawdza swój najniższy skrót, aby sprawdzić, czy jest już w zestawie widzialnych skrótów (zestaw Pythona, a zatem wyszukiwanie to O (1) w rozmiarze zestawu); jeśli tak, to słowo lub jedna z jego rotacji była już widoczna. W przeciwnym razie dodaje ten skrót do zestawu.
Argumentem wiersza polecenia powinna być nazwa pliku zawierającego jedno słowo w wierszu (np
/usr/share/dict/words
.).źródło
Haskell
Nie jestem pewien co do skuteczności, najprawdopodobniej raczej źle. Chodzi o to, aby najpierw utworzyć wszystkie możliwe rotacje wszystkich słów, policzyć wartości, które jednoznacznie reprezentują ciągi, i wybrać minimum. W ten sposób otrzymujemy liczbę unikalną dla grupy cyklicznej.
Możemy pogrupować według tego numeru i sprawdzić liczbę tych grup.
Jeśli n jest liczbą słów na liście, a m jest długością słowa, wówczas obliczanie „cyklicznego numeru grupy” dla wszystkich słów to
O(n*m)
sortowanieO(n log n)
i grupowanieO(n)
.źródło
Matematyka
Postanowiłem zacząć od nowa, teraz, gdy rozumiem zasady gry (tak myślę).
Słownik o długości 10000 unikalnych, losowo skomponowanych „słów” (tylko małe litery) o długości 3. W podobny sposób utworzono inne słowniki składające się z ciągów o długości 4, 5, 6, 7 i 8.
g
pobiera bieżącą wersję słownika do sprawdzenia. Górne słowo jest połączone z cyklicznymi wariantami (jeśli istnieją). Słowo i jego dopasowania są dołączane do listyout
wyników przetworzonych słów. Słowa wyjściowe są usuwane ze słownika.f
przegląda słownik wszystkich słów.Przykład 1 : rzeczywiste słowa
Przykład 2 : Sztuczne słowa. Słownik ciągów długości 3. Po pierwsze, czas. Następnie liczba słów cyklicznych.
Czasy jako funkcja długości słowa . 10000 słów w każdym słowniku.
Nie wiem szczególnie, jak interpretować wyniki w kategoriach O. Mówiąc prosto, czas z grubsza podwaja się ze słownika z trzema znakami do słownika z czterema znakami. Czas rośnie prawie pomijalnie z 4 do 8 znaków.
źródło
Można to zrobić w O (n), unikając kwadratowego czasu. Chodzi o to, aby dwa razy wykonać pełny okrąg przemierzający łańcuch podstawowy. Konstruujemy więc „Amazingamazin” jako ciąg z pełnym kołem, aby sprawdzić wszystkie ciągi cykliczne odpowiadające „niesamowitemu”.
Poniżej znajduje się rozwiązanie Java:
źródło
Nie wiem, czy to jest bardzo wydajne, ale to mój pierwszy crack.
źródło
Perl
nie jestem pewien, czy rozumiem problem, ale odpowiada to przynajmniej przykładowi @dude opublikowanemu w komentarzach. popraw moją z pewnością niepoprawną analizę.
dla każdego słowa W w podanych N słowach z listy ciągów, musisz przejść przez wszystkie znaki W w najgorszym przypadku. muszę założyć, że operacje skrótu są wykonywane w stałym czasie.
źródło