OEIS A000009 liczy liczbę ścisłych partycji liczb całkowitych. Ścisły podział na nieujemną liczbą całkowitą njest 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.

Mathematica, 11 bajtów

PartitionsQ

Przypadek testowy

PartitionsQ@Range[10]
(* {1,1,2,2,3,4,5,6,8,10} *)

Pyth, 7 bajtów

l{I#./Q

Wypróbuj online. Zestaw testowy.

• Weź wejście ( Q).
• Znajdź jego partycje (./ ).
• Filtruj ( #) w uniquify ({ ), nie zmieniając ( I) partycji. To usuwa partycje z duplikatami.
• Znajdź długość wyniku ( l).

Haskell, 39 bajtów

f n=sum[1|x<-mapM(:[0])[1..n],sum x==n]

Funkcja (:[0])konwertuje liczbę kna listę [k,0]. Więc,

mapM(:[0])[1..n]

oblicza iloczyn kartezjański [1,0],[2,0],...,[n,0], który daje wszystkie podzbiory [1..n]z 0 dla pominiętych elementów. Ścisłe partycje nodpowiadają takim listom z sumą n. Takie elementy są liczone na podstawie listy, która jest krótsza niż length.filter.

ES6, 64 bajty

f=(n,k=0)=>[...Array(n)].reduce((t,_,i)=>n-i>i&i>k?t+f(n-i,i):t,1)

Działa przez rekurencyjne odejmowanie próby. kjest 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).

Python, 68 bajtów

p=lambda n,d=0:sum(p(n-k,n-2*k+1)for k in range(1,n-d+1))if n else 1

Wystarczy wywołać anonimową funkcję przekazującą nieujemną liczbę całkowitą njako argument ... i poczekać na koniec wszechświata.

Python 2, 49 bajtów

f=lambda n,k=1:n/k and f(n-k,k+1)+f(n,k+1)or n==0

Gałęzie rekursji na każdym potencjalnym do składnika kz 1aby nzdecydować, czy powinien on zostać uwzględniony. Każdy dołączony summand jest odejmowany od pożądanej sumy n, a na końcu, jeśli n=0pozostanie, ścieżka jest liczona.

Haskell, 43 bajty

0%0=1
_%0=0
n%k=n%(k-1)+(n-k)%(k-1)
f n=n%n

Funkcja binarna n%k liczy liczbę ścisłych partycji nna części z maksymalną częścią k, więc pożądaną funkcją jest f n=n%n. Każda wartość kmoże być uwzględniona, która zmniejsza nsię klub wyklucza, i tak czy inaczej nowe maksimum kjest o jedną wartość niższe, co daje rekurencję n%k=n%(k-1)+(n-k)%(k-1).

Julia, 53 bajty

n->endof(collect(filter(p->p==∪(p),partitions(n))))

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, filtertylko do tych z odrębnymi sumami collect, i używamy ostatniego indeksu (tj. Długości) endof.

Haskell, 58 bajtów

import Data.List
h x=sum[1|i<-subsequences[1..x],sum i==x]

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 to x == 0również, ponieważ wszystkie podsekwencje [1..0]są [[]]i suma []jest 0.

05AB1E , 8 bajtów

ÅœʒDÙQ}g

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

Ŝ          # Get all integer partitions of the (implicit) input
            #  i.e. 5 → [[1,1,1,1,1],[1,1,1,2],[1,1,3],[1,2,2],[1,4],[2,3],[5]]
  ʒ   }     # Filter by:
   D        #  Duplicate the current partition
    Ù       #  Uniquify (removing any duplicated values from) this copied partition
            #   i.e. [1,1,1,1,1] → [1]
            #   i.e. [1,4] → [1,4]
     Q      #  Check if it's still the same
            #   i.e. [1,1,1,1,1] and [1] → 0 (falsey)
            #   i.e. [1,4] and [1,4] → 1 (truthy)
       g    # Then take the length of the filtered list (and implicitly output it)
            #  i.e. [[1,4],[2,5],[5]] → 3

05AB1E , 5 bajtów

LæOQO

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:

L         # range 1..input
 æ        # list of subsets
  O       # sum each subset
   Q      # equal? (1 for each sum that equals the input, 0 otherwise)
    O     # sum the booleans