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 4ma następujące części:

[[1, 1, 1, 1], [1, 1, 2], [1, 3], [2, 2], [4]]

Dlatego ma 5przegrody. 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

Pyth , 3 bajty

l./

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.

l. / Pełny program z niejawnym wejściem.

 ./ Partycje całkowite. Zwraca wszystkie posortowane listy dodatnich liczb całkowitych, które dodają do danych wejściowych.
l Długość.
      Wynik niejawnie wyprowadza wynik.

Mathematica, 11 bajtów

PartitionsP

Wyjaśnienie

¯\_(ツ)_/¯

Python 2 , 85 83 bajtów

-2 bajty dzięki @notjagan

lambda n:n<1or sum(sum(i*((n-k)%i<1)for i in range(1,n+1))*p(k)for k in range(n))/n

Wypróbuj online!

Korzystanie z formuły rekurencyjnej z OEIS A000041 .

Emojicode 0,5, 204 201 bajtów

🐋🚂🍇🐖🅰️➡🚂🍇🍊⬅🐕1🍇🍎1🍉🍮s 0🔂k⏩0🐕🍇🍦t➖🐕k🍮r t🔂i⏩1 t🍇🍊😛🚮t i 0🍇🍮➕r i🍉🍉🍮➕s✖r🅰️k🍉🍎➗s🐕🍉🍉

Wypró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ł tteż 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:

🏁🍇
 🍦str🔷🔡😯🔤Please enter a number🔤
 🍊🍦num🚂str 10🍇
  😀🔡🅰️num 10
 🍉🍓🍇
  😀🔤Learn what a number is, you moron!🔤
 🍉
🍉

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ł

🐋🚂🍇
 🐖🅰️➡🚂🍇
  🍊◀️🐕2🍇
   🍎1
  🍉
  🍮sum 0
  🔂k⏩0🐕🍇
   🍦nmk➖🐕k
   🍮sig nmk
   🔂i⏩1 nmk🍇
    🍊😛🚮nmk i 0🍇
     🍮➕sig i
    🍉
   🍉
   🍮➕sum✖sig🅰️k
  🍉
  🍎➗sum🐕
 🍉
🍉

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.

🍦str🔷🔡😯🔤Please enter a number🔤

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.

🍊🍦num🚂str 10

Rozwalmy to. 🚂str 10wywoł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 expressionoznacza: oceń wyrażenie. Jeśli opcjonalne zawiera nicość, warunek jest oceniany na 👎 (fałsz). W przeciwnym razie zamrożona nazwavariable🍇 ... 🍉

😀🔡🅰️num 10

🅰️ to metoda, którą główny kod dodaje do 🚂 za pomocą 🐋, która oblicza liczbę partycji. To wywołuje 🅰️ numzamroż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.

😀🔤Learn what a number is, you moron!🔤

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łya(n) = (1/n) * Sum_{k=0..n-1} sigma(n-k)*a(k)

🍊⬅🐕1🍇
 🍎1
🍉

🐕 jest podobny do innych języków thislub selfz 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.

🍮sum 0

Utwórz nową zmienną sumi ustaw ją na 0. Domyślnie zakłada się, że wpisz 🚂.

🔂k⏩0🐕

🔂 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 < stopprzeciwnym 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żne for k in range(n)lub Sum_{k=0..n-1}w formule.

🍦nmk➖🐕k

Musimy obliczyć sigma (n - k), czyli sumę dzielników, n - kinnymi słowy, a argument jest potrzebny kilka razy, więc zapisuje się n - kw zmiennej, nmkaby zapisać niektóre bajty.

🍮sig nmk
🔂i⏩1 nmk

To ustawia sigzmienną na argument sigma i iteruje wszystkie liczby od 1 do nmk - 1. Mógłbym zainicjować zmienną na 0 i iterować po 1..nmk, ale robienie tego w ten sposób jest krótsze.

🍊😛🚮nmk i 0

🚮 oblicza resztę, moduł i 😛 sprawdza równość, więc warunkiem będzie 👍, jeśli ijest dzielnikiem nmk.

🍮➕sig i

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ętrznej sigbędzie zawierać sumę dzielników n - klubsigma(n - k)

🍮➕sum✖sig🅰️k

Kolejne zadanie przez połączenie, więc dodaje sigma(n - k) * A(k)się do całości, tak jak w formule.

🍎➗sum🐕

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

Pari / GP , 8 bajtów

numbpart

Wypróbuj online!

Oktawa, 18 bajtów

partcnt(input(''))

Korzysta z wbudowanej funkcji partcnt.

Nie można tego zrobić poprawnie za pomocą anonimowej funkcji przy użyciu @, pomoc byłaby mile widziana.

Retina , 34 bajty

.+
$*
+%1`\B
;$'¶$`,
,

%O`1+
@`.+

Wypróbuj online!

Wyjaśnienie

.+
$*

Przekształć dane wejściowe w jednoargumentowe.

+%1`\B
;$'¶$`,

To oblicza wszystkie 2 partycje ^n-1 na liście jednoargumentowej. Robimy to poprzez wielokrotne ( +) dopasowywanie pierwszej ( 1) granicy niebędącej słowem ( \Btj. Pozycji między dwoma 1s) w każdej linii ( %) i zastępowanie go ;, wszystko po nim ( $'), linefeed ( ¶), wszystko przed it ( $`) i ,. Przykład:

1;1,111

Staje się

      vv
1;1,1;11
1;1,1,11
^^^^^

Gdzie voznacza 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 \Bdopasowanie. Więc dalej ...

,

... usuwamy przecinki. To daje nam wszystkie partycje. Na przykład dla danych wejściowych 4otrzymujemy:

1;1;1;1
1;1;11
1;11;1
1;111
11;1;1
11;11
111;1
1111

Jednak nie dbamy o zamówienie:

%O`1+

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ą wierszy D`.

Python 2 , 54 53 bajtów

f=lambda n,k=1:1+sum(f(n-j,j)for j in range(k,n/2+1))

Wypróbuj online!

Jak to działa

Każda partycja n może być reprezentowana jako lista x = [x ₁ , ⋯, x _m ] tak, że x ₁ + ⋯ + x _m = n . Ta reprezentacja staje się wyjątkowa, jeśli wymagamy, aby x ₁ ≤ ⋯ ≤ x _m .

Definiujemy funkcję pomocniczą f (n, k), która zlicza partycje o dolnej granicy k , tj. Listy x takie, że x ₁ + ⋯ + x _m = n i k ≤ x ₁ ≤ ⋯ ≤ 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 ₁ , ⋯, x _m ] = [j, y ₁ , ⋯, y _m-1 ] . Mamy to x ₁ + ⋯ + x _m = n wtedy i tylko wtedy, gdy y ₁ + ⋯ + y _m-1 = n - j . Ponadto x ₁ ≤ ⋯ ≤ x _m wtedy i tylko wtedy, gdy j ≤ y ₁ ≤ ⋯ ≤ 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 .

J , 37 35 bajtów

0{]1&((#.]*>:@#.~/.~&.q:@#\%#),])1:

Wypróbuj online!

Wyjaśnienie

0{]1&((#.]*>:@#.~/.~&.q:@#\%#),])1:  Input: n
                                 1:  Constant 1
  ]                                  Get n
   1&(                          )    Repeat n times on x = [1]
                          \            For each prefix
                         #               Length
                      q:@                Prime factors
                 /.~&                    Group equal factors
              #.~                        Compute p+p^2+...+p^k for each group
           >:@                           Increment
                    &.q:                 Product
                           %           Divide
                            #          Length
         ]                             Get x
          *                            Times
   1   #.                              Sum
                              ,        Joim
                               ]       Get x
                                       Set this as next value of x
0{                                   Select value at index 0

JavaScript, 125 121 bajtów

n=>(z=(a,b)=>[...Array(a)].map(b))(++n**n,(_,a)=>z[F=z(n,_=>a%(a/=n,n)|0).sort().join`+`]=b+=eval(F)==n-1&!z[F],b=0)|b||1

Wypróbuj online!

Ostrzeżenie: złożoność czasu i przestrzeni ma charakter wykładniczy. Działa bardzo wolno w przypadku dużych liczb.

Python 2 , 89 bajtów

-9 bajtów Mr.Xcoder -1 bajtów notjagan

lambda n:len(p(n))
p=lambda n,I=1:{(n,)}|{y+(x,)for x in range(I,n/2+1)for y in p(n-x,x)}

Wypróbuj online!

Galaretka , 13 bajtów

JÆsæ.:L;
1Ç¡Ḣ

Wypróbuj online!

Rozwiązanie n = 1000 w TIO zajmuje 5 sekund.

Java 8 (229 bajtów)

import java.util.function.*;class A{static int j=0;static BiConsumer<Integer,Integer>f=(n,m)->{if(n==0)j++;else for(int i=Math.min(m,n);i>=1;i--)A.f.accept(n-i,i);};static Function<Integer,Integer>g=n->{f.accept(n,n);return j;};}

Nie golfowany:

import java.util.function.*;

class A {
    static int j = 0;
    static BiConsumer<Integer, Integer> f = (n, m) -> {
        if (n == 0)
            j++;
        else
            for (int i = Math.min(m, n); i >= 1; i--)
                A.f.accept(n - i, i);
    };
    static Function<Integer, Integer> g = n -> {
        f.accept(n, n);
        return j;
    };
}

Galaretka , 3 bajty

ŒṗAtom został niedawno dodany, a to oznacza „partycje całkowitej liczby”.

ŒṗL

Wypróbuj online!

ŒṗL - Pełny program.

Œṗ - Partycje całkowite.
  L - długość.
      - Wynik niejawny.

Pyt , 2 bajty

←ᵱ

Wyjaśnienie:

←          Get input
 ᵱ         Number of partitions

JavaScript ES7, 69 bajtów

n=>(f=(i,s)=>i?[for(c of Array(1+n))f(i-1,s,s-=i)]:c+=!s)(n,n,c=0)&&c

JavaScript ES6, 71 bajtów

n=>(f=(i,s)=>i?[...Array(1+n)].map(_=>f(i-1,s,s-=i)):c+=!s)(n,n,c=0)&&c

Złożoność czasu O (n ^ n), więc bądź ostrożny (na moim komputerze pojawia się oczywiste opóźnienie F(6))