Ścisłe partycje dodatniej liczby całkowitej

14

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 , więc wygrywa najkrótsze rozwiązanie w bajtach.

lirtosiast
źródło

Odpowiedzi:

4

Mathematica, 11 bajtów

PartitionsQ

Przypadek testowy

PartitionsQ@Range[10]
(* {1,1,2,2,3,4,5,6,8,10} *)
njpipeorgan
źródło
3

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).
PurkkaKoodari
źródło
3

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.

xnor
źródło
Znakomity! Sam szukałem zamiennika subsequences(+ import), ale jak dotąd nie udało mi się.
nimi
2

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).

Neil
źródło
2

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.

Kok
źródło
zrób to n>0, zapisz bajt i idź szybciej (wydaje mi się, że powrócisz do liczb ujemnych): P
st0le
Zapamiętywanie tego rodzaju przyspiesza go
st0le,
Nie mogę zmienić instrukcji if na:return sum(...)if n else 1
andlrc
@ randomra Oczywiście, oczywiście ...
Bob
1

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.

xnor
źródło
1

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).

xnor
źródło
n%k|q<-k-1=n%q+(n-k)%qgoli bajt poza linią 3.
Izaak Weiss
0

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.

Alex A.
źródło
0

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][[]]i suma []jest 0.

nimi
źródło
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
Kevin Cruijssen
źródło
0

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
Ponury
źródło