Wyobraźmy sobie, że mamy skończony zestaw dodatnich liczb całkowitych. Ten zestaw może być reprezentowany jako linia kropek, w której każda liczba całkowita występująca w zestawie jest wypełniona jak karta scantron lub poncz . Na przykład zestaw {1,3,4,6}można przedstawić jako:
*.**.*
*reprezentuje członka naszego zestawu i .reprezentuje liczbę całkowitą, która nie jest członkiem zestawu.
Te zestawy mają „czynniki”. Luźno x jest współczynnikiem y, jeśli y można zbudować z kopii x. Bardziej rygorystycznie nasza definicja czynnika jest następująca:
- x jest współczynnikiem y wtedy i tylko wtedy, gdy y jest sumą szeregu rozłącznych zbiorów, z których wszystkie są x z przesunięciem.
Nazwalibyśmy *.*to czynnik o *.**.*ponieważ jest ona dość wyraźnie składa się z dwóch egzemplarzy *.*put końca do końca.
*.**.*
------
*.*...
...*.*
Czynniki nie muszą być od końca do końca, powiedzielibyśmy również, że *.*jest to czynnik*.*.*.*
*.*.*.*
-------
*.*....
....*.*
Czynniki mogą się również nakładać. Oznacza *.*to również, że****
****
----
*.*.
.*.*
Jednak liczby nie można objąć czynnikiem więcej niż jeden raz. Na przykład *.*to nie czynnik *.*.*.
Oto bardziej skomplikowany przykład:
*..*.**..***.*.*
Ma to *..*.*jako czynnik. Możesz zobaczyć to poniżej, gdzie ustawiłem trzy wystąpienia *..*.*.
*..*.**..***.*.*
----------------
*..*.*..........
......*..*.*....
..........*..*.*
Zadanie
Biorąc pod uwagę zbiór dowolnej rozsądnej reprezentacji, wypisywane są wszystkie zbiory będące czynnikami wejściowymi.
Możesz indeksować według dowolnej wartości (tzn. Możesz wybrać najmniejszą liczbę, która może być obecna na wejściu). Możesz również założyć, że zestaw wejściowy zawsze będzie zawierał najmniejszą wartość.
To jest pytanie w golfa kodu, więc powinieneś starać się to zrobić w jak najmniejszej liczbie bajtów.
Przypadki testowe
Te przypadki testowe zostały wykonane ręcznie, może być błąd lub dwa na większych
* -> *
*.*.* -> *, *.*.*
*.*.*.* -> *, *.*, *...*, *.*.*.*
****** -> *, **, *..*, ***, *.*.*, ******
*..*.**..***.*.* -> *, *..*.*, *.....*...*, *..*.**..***.*.*
*...*****.**.** -> *, *...**.**, *.....*, *...*****.**.**
źródło
[1,3,5,7]Dla*.*.*.*), czy możemy założyć, że jest on posortowany?*.*.*=x+x^2+x^4, to1+x+x^2=***byłoby dzielnikiem, prawda?x+x^2+x^4 = (1-x+x^2)(1+x+x^2)*wymieniony jest jako czynnik reprezentujący ten sam podzbiór co*.lub*...Odpowiedzi:
Mathematica,
7168 bajtówWprowadź jako
{1,3,5,7}(posortowane) i wyślij jako{{1, 3, 5, 7}, {1, 3}, {1, 5}, {1}}. Funkcja wyrzuci kilka wiadomości.Jest to O (2 2 Nie ) (gdzie N jest długością wejścia, a o = p = e = 1 ...). Generuje wszystkie podzbiory podzbiorów, a następnie wybiera te, które skutkują wysyłaniem danych wejściowych po połączeniu (upewniając się, że rozważamy tylko partycje) i gdzie wszystkie elementy są takie same, jeśli odejmiemy najmniejszą wartość każdego podzbioru).
źródło
Galaretka , 12 bajtów
Wykorzystanie danych wejściowych i wyjściowych
1oraz0zamiast*i..Wypróbuj online!
Jak to działa
źródło