Numer podziału dodatniej liczby całkowitej jest definiowany jako liczba sposobów, które można wyrazić jako sumę liczb całkowitych dodatnich. Innymi słowy, liczba partycji całkowitych, jakie posiada. Na przykład liczba 4
ma następujące części:
[[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]]
Dlatego ma 5
przegrody. To jest OEIS A000041 .
Zadanie
Biorąc pod uwagę dodatnią liczbę całkowitą N, określ jej numer podziału.
Obowiązują wszystkie standardowe zasady.
Dane wejściowe i wyjściowe można przetwarzać dowolnymi rozsądnymi środkami.
To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach.
Przypadki testowe
Wejście | Wynik 1 | 1 2 | 2) 3 | 3) 4 | 5 5 | 7 6 | 11 7 | 15 8 | 22 9 | 30 10 | 42
code-golf
math
number-theory
combinatorics
integer-partitions
Martin Ender
źródło
źródło
Odpowiedzi:
Pyth , 3 bajty
Wypróbuj tutaj!lub Wypróbuj pakiet testowy.
Odpowiedź zajęła znacznie więcej czasu niż samo napisanie kodu: P.
W jaki sposób?
Pyth jest właściwym narzędziem do pracy.
źródło
Mathematica, 11 bajtów
Wyjaśnienie
źródło
Python 2 ,
8583 bajtów-2 bajty dzięki @notjagan
Wypróbuj online!
Korzystanie z formuły rekurencyjnej z OEIS A000041 .
źródło
==0
jest równoważne<1
w tym przypadku. EDYCJA: Użyj podejścia<1
zamiast==0
, ale kod TIO nie.Emojicode 0,5,
204201 bajtówWypróbuj online!
-3 bajty przy użyciu „mniejszej lub równej 1” zamiast „mniejszej niż 2”, ponieważ emoji „mniej niż” ma dość długie kodowanie UTF-8. Zrobił
t
też zamrożenie, aby wyciszyć ostrzeżenie bez wpływu na liczbę bajtów.Rozszerza klasę 🚂 (liczbę całkowitą) o metodę o nazwie 🅰️. Możesz napisać prosty program, który pobiera liczbę z wejścia, wywołuje numer 🅰️ i wypisuje wynik w następujący sposób:
Ta część może być bardzo golfa, pomijając komunikaty i obsługę błędów, ale nie jest uwzględniona w partyturze, więc wolę zamiast tego wyświetlać więcej funkcji Emojicode, jednocześnie poprawiając czytelność po drodze.
Nie golfił
Wyjaśnienie
Uwaga: duży wybór emoji nie ma większego sensu w emojicode 0.5. W końcu to 0.x. 0.6 to naprawi.
Emojicode jest zorientowanym obiektowo językiem programowania obejmującym elementy generyczne, protokoły, opcje i zamknięcia, ale ten program nie używa żadnych zamknięć, a wszystkie rodzaje ogólne i protokoły można uznać za niejawne, a jedyna opcja pojawia się w kodzie I / O.
Program działa tylko na kilku typach: 🚂 jest typem całkowitym, 🔡 jest typem ciągu, a ⏩ jest typem zakresu. Pojawia się również kilka booleanów (👌), ale są one używane tylko w określonych warunkach. Wartości logiczne mogą przyjmować wartość 👍 lub 👎, które odpowiadają odpowiednio prawdzie i fałszowi.
Obecnie w Emojicode nie ma żadnych operatorów, więc dodawanie, porównywanie i inne operacje, które normalnie są operatorami, są implementowane jako funkcje, dzięki czemu wyrażenia używają notacji z prefiksem . Operatorzy są również planowani w wersji 0.6.
Najpierw zajmiemy się programem testowym.
To jest blok 🏁, który można porównać do głównego z innych języków.
Winogrona i arbuzy deklarują bloki kodu w emojicode.
To deklaruje nazwę „zamrożoną”
str
i ustawia jej wartość na nowy ciąg utworzony za pomocą inicjatora (konstruktora) 😯, który przyjmuje monit jako ciąg, a następnie wprowadza wiersz od użytkownika. Po co używać zamrożonego zamiast zmiennej? Nie zmieni się, więc zmienna wyemituje ostrzeżenie.Rozwalmy to.
🚂str 10
wywołuje metodę 🚂 na obiekcie jest tworzona z nieopakowaną wartością opcjonalną, a warunek jest oceniany na 👍, (prawda). Dlatego w normalnym użyciu wprowadzany jest blok następujący po warunkowym.str
zamrożonym argumentem 10. Zgodnie z konwencją metody nazwane nazwą typu konwertują obiekt na ten typ. 10 jest podstawą do konwersji liczb całkowitych. Ta metoda zwraca opcjonalny,🍬🚂
. Opcjonalne mogą zawierać wartość typu podstawowego lub nicość, ⚡. Gdy ciąg nie zawiera liczby, zwracane jest ⚡. Aby użyć wartości, należy rozpakować opcjonalne za pomocą 🍺, co powoduje błąd w czasie wykonywania, jeśli wartość wynosi ⚡. Dlatego dobrą praktyką jest sprawdzanie nicości przed rozpakowaniem opcjonalnego. W rzeczywistości jest tak powszechne, że Emojicode ma na to skrót. Zwykle🍊
jest „jeśli”.🍊🍦 variable expression
oznacza: oceń wyrażenie. Jeśli opcjonalne zawiera nicość, warunek jest oceniany na 👎 (fałsz). W przeciwnym razie zamrożona nazwavariable
🍇 ... 🍉
🅰️ to metoda, którą główny kod dodaje do 🚂 za pomocą 🐋, która oblicza liczbę partycji. To wywołuje 🅰️
num
zamrożonego, który zadeklarowaliśmy w warunkowej, i konwertuje wynik na ciąg znaków przy użyciu podstawy 10 metodą 🔡. Następnie 😀 drukuje wynik.🍓 oznacza „else”, więc ten blok jest wprowadzany, gdy użytkownik nie wprowadził poprawnie liczby.
Drukuje literał ciągu.
Teraz spójrzmy na program główny. Wyjaśnię wersję bez golfa; w wersji golfowej właśnie usunięto białe spacje i zmieniono nazwy zmiennych na nazwy jednoliterowe.
Rozszerz klasę 🚂. Jest to funkcja, która nie jest powszechnie spotykana w językach programowania. Zamiast tworzyć nową klasę z 🚂 jako nadklasą, 🐋 bezpośrednio modyfikuje 🚂.
Tworzy nową metodę o nazwie 🅰️, która zwraca 🚂. Zwraca liczbę partycji obliczoną za pomocą formuły
a(n) = (1/n) * Sum_{k=0..n-1} sigma(n-k)*a(k)
🐕 jest podobny do innych języków
this
lubself
z innych języków i odnosi się do obiektu, dla którego metoda została wywołana. Ta implementacja jest rekurencyjna, więc jest to warunek końcowy: jeśli liczba, na którą wywołano metodę, jest mniejsza lub równa 1, zwraca 1.Utwórz nową zmienną
sum
i ustaw ją na 0. Domyślnie zakłada się, że wpisz 🚂.🔂 iteruje nad wszystkim, co implementuje protokół,, podczas gdy ⏩ to dosłowny zakres, który zdarza się implementować 🔂🐚🚂. Zakres ma wartość początkową, wartość zatrzymania i wartość kroku, która przyjmuje się, że wynosi 1, jeśli w
start < stop
przeciwnym razie -1. Można również określić wartość kroku za pomocą ⏭, aby utworzyć literał zakresu. Wartość początkowa jest włącznie, natomiast wartość przystanek jest wyłączna, więc jest to równoważnefor k in range(n)
lubSum_{k=0..n-1}
w formule.Musimy obliczyć sigma (n - k), czyli sumę dzielników,
n - k
innymi słowy, a argument jest potrzebny kilka razy, więc zapisuje sięn - k
w zmiennej,nmk
aby zapisać niektóre bajty.To ustawia
sig
zmienną na argument sigma i iteruje wszystkie liczby od 1 donmk - 1
. Mógłbym zainicjować zmienną na 0 i iterować po 1..nmk, ale robienie tego w ten sposób jest krótsze.🚮 oblicza resztę, moduł i 😛 sprawdza równość, więc warunkiem będzie 👍, jeśli
i
jest dzielnikiemnmk
.Jest to zadanie na telefon, podobne do
+= -= >>=
rodziny operatorów w niektórych gorszych językach wolnych od emoji. Ten wiersz można również zapisać jako🍮 sig ➕ sig i
. Dlatego po zakończeniu pętli wewnętrznejsig
będzie zawierać sumę dzielnikówn - k
lubsigma(n - k)
Kolejne zadanie przez połączenie, więc dodaje
sigma(n - k) * A(k)
się do całości, tak jak w formule.Na koniec suma jest dzielona przez n i zwracany jest iloraz. To wyjaśnienie prawdopodobnie zajęło trzy razy tyle samo czasu, co napisanie samego kodu ...
źródło
Pari / GP , 8 bajtów
Wypróbuj online!
źródło
Oktawa, 18 bajtów
Korzysta z wbudowanej funkcji partcnt.
Nie można tego zrobić poprawnie za pomocą anonimowej funkcji przy użyciu @, pomoc byłaby mile widziana.
źródło
Retina , 34 bajty
Wypróbuj online!
Wyjaśnienie
Przekształć dane wejściowe w jednoargumentowe.
To oblicza wszystkie 2 partycje n-1 na liście jednoargumentowej. Robimy to poprzez wielokrotne (
+
) dopasowywanie pierwszej (1
) granicy niebędącej słowem (\B
tj. Pozycji między dwoma1
s) w każdej linii (%
) i zastępowanie go;
, wszystko po nim ($'
), linefeed (¶
), wszystko przed it ($`
) i,
. Przykład:Staje się
Gdzie
v
oznacza wynik$'
i^
oznacza wynik$`
. Jest to powszechny idiom polegający na uzyskiwaniu wyniku dwóch różnych zamian jednocześnie (w zasadzie wstawiamy zarówno;
i,
zamiennik, jak i brakujące „połówki” łańcucha, aby ukończyć dwa pełne podstawienia).Będziemy leczyć
;
jak rzeczywiste partycje i,
po prostu jako symbole zastępcze, które uniemożliwiają późniejsze ich\B
dopasowanie. Więc dalej ...... usuwamy przecinki. To daje nam wszystkie partycje. Na przykład dla danych wejściowych
4
otrzymujemy:Jednak nie dbamy o zamówienie:
To sortuje przebiegi
1
s w każdej linii, więc otrzymujemy nieuporządkowane partycje.Na koniec zliczamy unikalne (
@
) dopasowania.+
, tj. Ile różnych linii / partycji uzyskaliśmy. Dodałem tę@
opcję wieki temu, a potem zupełnie o niej zapomniałem i dopiero niedawno ją odkryłem . W takim przypadku zapisuje bajt przed pierwszą deduplikacją wierszyD`
.źródło
Python 2 ,
5453 bajtówWypróbuj online!
Jak to działa
Każda partycja n może być reprezentowana jako lista x = [x 1 , ⋯, x m ] tak, że x 1 + ⋯ + x m = n . Ta reprezentacja staje się wyjątkowa, jeśli wymagamy, aby x 1 ≤ ⋯ ≤ x m .
Definiujemy funkcję pomocniczą f (n, k), która zlicza partycje o dolnej granicy k , tj. Listy x takie, że x 1 + ⋯ + x m = n i k ≤ x 1 ≤ ⋯ ≤ x m . W przypadku wejścia n wyzwanie prosi zatem o wynik f (n, 1) .
Dla dodatnich liczb całkowitych n i k takich, że k ≤ n , istnieje co najmniej jedna partycja z dolną granicą k : lista singletonów [n] . Jeśli n = k (w szczególności, jeśli n = 1 ), jest to jedyna dopuszczalna partycja. Z drugiej strony, jeśli k> n , w ogóle nie ma rozwiązań.
Jeśli k <n , możemy rekurencyjnie liczyć pozostałe partycje, budując je od lewej do prawej, w następujący sposób. Dla każdego j takiego, że k ≤ j ≤ n / 2 , możemy budować partycje [x 1 , ⋯, x m ] = [j, y 1 , ⋯, y m-1 ] . Mamy to x 1 + ⋯ + x m = n wtedy i tylko wtedy, gdy y 1 + ⋯ + y m-1 = n - j . Ponadto x 1 ≤ ⋯ ≤ x m wtedy i tylko wtedy, gdy j ≤ y 1 ≤ ⋯ ≤ y m-1 .
W związku z tym, strefy x o n , które zaczynają się j może być obliczona jako f (n - j, j) , który zlicza prawidłowych partycji y . Wymagając, aby j ≤ n / 2 , zapewniamy, że j ≤ n - j , więc jest co najmniej jedno y . Możemy zatem policzyć wszystkie partycje n , sumując 1 (dla [n] ) i f (n - j, j) dla wszystkich prawidłowych wartości j .
Kod jest prostą implementacją funkcji matematycznej f . Ponadto powoduje, że k ma wartość domyślną 1 , więc
f(n)
oblicza wartość f (n, 1) dla wejścia n .źródło
J ,
3735 bajtówWypróbuj online!
Wyjaśnienie
źródło
p(n) = sum(sigma(n-k) * p(k) for k = 0 to n-1) / n
. Dodam wyjaśnienie kodu później, gdy uważam, że nie można go znacznie skrócić.JavaScript,
125121 bajtówWypróbuj online!
Ostrzeżenie: złożoność czasu i przestrzeni ma charakter wykładniczy. Działa bardzo wolno w przypadku dużych liczb.
źródło
Python 2 , 89 bajtów
-9 bajtów Mr.Xcoder -1 bajtów notjagan
Wypróbuj online!
źródło
¯\_(ツ)_/¯
- BTW, jeśli chcesz zachować pełną funkcję, nie potrzebujesz zmiennej, 94 bajtyGalaretka , 13 bajtów
Wypróbuj online!
Rozwiązanie n = 1000 w TIO zajmuje 5 sekund.
źródło
Java 8 (229 bajtów)
Nie golfowany:
źródło
Galaretka , 3 bajty
Œṗ
Atom został niedawno dodany, a to oznacza „partycje całkowitej liczby”.Wypróbuj online!
źródło
Pyt , 2 bajty
Wyjaśnienie:
źródło
JavaScript ES7, 69 bajtów
JavaScript ES6, 71 bajtów
Złożoność czasu O (n ^ n), więc bądź ostrożny (na moim komputerze pojawia się oczywiste opóźnienie
F(6)
)źródło