OEIS A000009 liczy liczbę ścisłych partycji liczb całkowitych. Ścisły podział na nieujemną liczbą całkowitą n
jest zbiorem liczb całkowitych dodatnich (a więc nie dopuszcza powtarzanie i kolejność nie ma znaczenia) tej kwoty n
.
Na przykład, 5 ma trzy surowe partycje: 5
, 4,1
, i 3,2
.
10 ma dziesięć partycji:
10
9,1
8,2
7,3
6,4
7,2,1
6,3,1
5,4,1
5,3,2
4,3,2,1
Wyzwanie
Biorąc pod uwagę nieujemną liczbę całkowitą n
<1000, wypisz liczbę ściśle określonych partycji.
Przypadki testowe:
0 -> 1
42 -> 1426
Oto lista ścisłych numerów partycji od 0 do 55 z OEIS:
[1,1,1,2,2,3,4,5,6,8,10,12,15,18,22,27,32,38,46,54,64,76,89,104,122,142,165,192,222,256,296,340,390,448,512,585,668,760,864,982,1113,1260,1426,1610,1816,2048,2304,2590,2910,3264,3658,4097,4582,5120,5718,6378]
To jest golf golfowy , więc wygrywa najkrótsze rozwiązanie w bajtach.
źródło
subsequences
(+import
), ale jak dotąd nie udało mi się.ES6, 64 bajty
Działa przez rekurencyjne odejmowanie próby.
k
jest liczbą, która została ostatnio odjęta, a następna liczba do odjęcia musi być większa (ale nie tak duża, aby nie można było odjąć jeszcze większej liczby). Dodano 1, ponieważ zawsze możesz się odjąćn
. (Również ponieważ jest to rekurencyjne, muszę uważać, aby wszystkie moje zmienne były lokalne).źródło
Python, 68 bajtów
Wystarczy wywołać anonimową funkcję przekazującą nieujemną liczbę całkowitą
n
jako argument ... i poczekać na koniec wszechświata.źródło
n>0
, zapisz bajt i idź szybciej (wydaje mi się, że powrócisz do liczb ujemnych): Preturn sum(...)if n else 1
Python 2, 49 bajtów
Gałęzie rekursji na każdym potencjalnym do składnika
k
z1
abyn
zdecydować, czy powinien on zostać uwzględniony. Każdy dołączony summand jest odejmowany od pożądanej sumyn
, a na końcu, jeślin=0
pozostanie, ścieżka jest liczona.źródło
Haskell, 43 bajty
Funkcja binarna
n%k
liczy liczbę ścisłych partycjin
na części z maksymalną częściąk
, więc pożądaną funkcją jestf n=n%n
. Każda wartośćk
może być uwzględniona, która zmniejszan
sięk
lub wyklucza, i tak czy inaczej nowe maksimumk
jest o jedną wartość niższe, co daje rekurencjęn%k=n%(k-1)+(n-k)%(k-1)
.źródło
n%k|q<-k-1=n%q+(n-k)%q
goli bajt poza linią 3.Julia, 53 bajty
Jest to anonimowa funkcja, która przyjmuje liczbę całkowitą i zwraca liczbę całkowitą. Aby go wywołać, przypisz go do zmiennej.
Dostajemy do tablicy partycje całkowite
partitions
,filter
tylko do tych z odrębnymi sumamicollect
, i używamy ostatniego indeksu (tj. Długości)endof
.źródło
Haskell, 58 bajtów
Przykład użycia:
map h [0..10]
->[1,1,1,2,2,3,4,5,6,8,10]
.To proste podejście z użyciem siły brutalnej. Sprawdź sumy wszystkich podsekwencji
1..x
. Działa tox == 0
również, ponieważ wszystkie podsekwencje[1..0]
są[[]]
i suma[]
jest0
.źródło
05AB1E , 8 bajtów
Wypróbuj online lub sprawdź wszystkie przypadki testowe .
Wyjaśnienie:
źródło
05AB1E , 5 bajtów
Wypróbuj online!
Uwaga: jest to bardzo wolne i powoduje przekroczenie limitu czasu dla danych wejściowych większych niż około 20.
Wyjaśnienie:
źródło