Interesująca jest sekwencja De Bruijna: jest to najkrótsza, cykliczna sekwencja, która zawiera wszystkie możliwe sekwencje danego alfabetu o danej długości. Na przykład, jeśli rozważamy alfabet A, B, C i długość 3, możliwe wyniki to:
AAABBBCCCABCACCBBAACBCBABAC
Można zauważyć, że każda możliwa sekwencja 3-znakowy pomocą liter A
, B
i C
są tam.
Twoim zadaniem jest wygenerowanie sekwencji De Bruijn w jak najmniejszej liczbie znaków. Twoja funkcja powinna przyjąć dwa parametry, liczbę całkowitą reprezentującą długość sekwencji oraz listę zawierającą alfabet. Twój wynik powinien być sekwencją w formie listy.
Możesz założyć, że każdy element w alfabecie jest inny.
Przykładowy generator można znaleźć tutaj
Standardowe luki zastosowanie
code-golf
combinatorics
Nathan Merrill
źródło
źródło
Odpowiedzi:
Pyth, 31 bajtów
Jest to bezpośrednia konwersja algorytmu zastosowanego w mojej odpowiedzi CJam . Wskazówki dotyczące gry w golfa mile widziane!
Ten kod definiuje funkcję,
g
która pobiera dwa argumenty, ciąg listy znaków i liczbę.Przykładowe użycie:
Wydajność:
Rozszerzenie kodu:
Wypróbuj tutaj
źródło
CJam,
52 4948 bajtówTo jest zaskakująco długie. Można w to dużo grać w golfa, biorąc pod uwagę wskazówki z tłumaczenia Pyth.
Wejście idzie jak
tj. - Ciąg listy znaków i długości.
a wyjściem jest ciąg De Bruijn
Wypróbuj online tutaj
źródło
CJam,
5249 bajtówOto inne podejście w CJam:
Pobiera takie dane wejściowe:
i produkuje dzieło Lyndona
Wypróbuj tutaj.
Wykorzystuje to relację ze słowami Lyndona . Generuje wszystkie słowa Lyndona o długości n w porządku leksykograficznym (jak opisano w tym artykule w Wikipedii), a następnie upuszcza te, których długości się nie dzielą n . To już daje sekwencję De Bruijn, ale ponieważ generuję słowa Lyndona jako ciągi cyfr, muszę również zastąpić je odpowiednimi literami na końcu.
Z powodów golfowych uważam, że późniejsze litery alfabetu mają niższy porządek leksykograficzny.
źródło
JavaScript (ES6) 143
Używając słów Lyndona, takich jak odpowiedź Martina, zaledwie 3 razy ...
Testuj w konsoli FireFox / FireBug
Wydajność
źródło
Python 2, 114 bajtów
Nie jestem pewien, jak bardziej grać w golfa, ze względu na moje podejście.
Wypróbuj online
Nie golfowany:
Ten kod jest trywialną modyfikacją mojego rozwiązania do nowszego wyzwania.
Jedynym powodem
[:1-n]
jest to, że sekwencja obejmuje zawijanie.źródło
PowerShell,
16496 bajtów-68 bajtów z -match
O($n*2^n)
zamiast generatora rekurencyjnegoO(n*log(n))
Skrypt niepoznany i testowy:
Wydajność:
Zobacz także: Jeden pierścień, aby rządzić nimi wszystkimi. Jeden ciąg zawierający je wszystkie
źródło