Wyświetl wszystkie uporządkowane partycje n

23

Wyzwanie polega na wyświetleniu listy wszystkich uporządkowanych partycji (kompozycji (kombinatoryki)) danej dodatniej liczby całkowitej n. Są wykazy numerów od 1do nktórych suma jest n. Na przykład przy danych wejściowych n = 4wynik powinien wynosić:

4
1, 3
3, 1
2, 2
2, 1, 1
1, 2, 1
1, 1, 2
1, 1, 1, 1

Wynik może być w dowolnej kolejności, ale musi zawierać każdą zamówioną partycję jeden raz. Oznacza to, że n = 4, [1, 1, 2], [1, 2, 1]i [2, 1, 1]wszystkie muszą być częścią wyniku.

Oto mój własny kod JavaScript, który to osiąga:

function range(n) {
    for (var range = [], i = 0; i < n; range.push(++i));
    return range;
}

function composition(n) {
    return n < 1 ? [[]] : range(n).map(function(i) {
        return composition(n - i).map(function(j) {
            return [i].concat(j);
        });
    }).reduce(function(a, b) {
        return a.concat(b);
    });
}

Gra w golfa, ES6 ( 169 167 119 109 105 89 85 bajtów ):

n=>n?[].concat(...[...Array(n)].map((x,i)=>i+1).map(b=>m(n-b).map(a=>[b,...a]))):[[]]
driima
źródło
3
Witamy na stronie! Musisz określić kryterium wygranej. Może golf golfowy? Czy też musi być w tej konkretnej kolejności? Jeśli tak, jak ogólnie określa się kolejność? Myślę, że porządek leksykograficzny byłby bardziej znaczący; lub jeszcze lepiej, zezwól na dowolne zamówienie. Możesz użyć piaskownicy do przyszłych wyzwań, zanim opublikujesz je tutaj
Luis Mendo
3
@Fatalize Here [2 1 1] różni się od [1 2 1], w przeciwieństwie do tam. Podejrzewam, że podejścia mogą się znacznie różnić
Luis Mendo
3
Do tych, którzy zamknęli się jako dupe: czy jesteś pewien, że różnica wskazana w komentarzach nie jest istotna? Nie głosuję na ponowne otwarcie, ponieważ myślę, że młot również zadziałałby w tym kierunku
Luis Mendo
3
Sugeruję, aby nie akceptować jeszcze odpowiedzi (nawet jeśli możesz ją zmienić w dowolnym momencie), ponieważ zobaczenie pytania zaakceptowanego na pierwszej stronie może sprawić, że ludzie będą myśleć, że to koniec, i nie będą brać udziału.
xnor
5
Zwykle określenie tych uporządkowanych partycji to „ kompozycje ”.
Greg Martin

Odpowiedzi:

7

Pyth, 7 6 bajtów

7 bajtowe rozwiązanie:

Pyth ma wbudowaną partycję całkowitą ./ , więc 5 z 7 bajtów otrzymuje porządek.

{s.pM./

Wypróbuj online!

Wyjaśnienie:

     ./  Integer partition (sorted by default)
  .pM    get all the orderings of each of the partitions as a nested list of lists of orderings
 s       Flatten by one layer
{        Remove duplicates

6 bajtowe rozwiązanie:

Jeśli masz listę, ./będzie obliczać z zamówieniami; wszystko, co pozostaje, to ponowne utworzenie numerów list.

lMM./m

Wypróbuj online!

Wyjaśnienie:

     m  Get lists by gathering a list of [0, 1,...input] (I could use U as well)

   ./   Partition with orderings
 MM     Map an operation across each of the orderings lists of elements
l       where that operation is the length of the sublists
Steven H.
źródło
Niesamowity. To najmniejszy, jaki do tej pory widziałem!
driima
11

Haskell, 37 bajtów

f 0=[[]]
f n=[a:x|a<-[1..n],x<-f$n-a]

xnor zapisał dwa bajty.

Lynn
źródło
1
Wygląda na to, że prostsze f n=[a:x|a<-[1..n],x<-f$n-a]jest krótsze.
xnor
nie potrzebujesz zerowego czeku ( given positive integer n ... numbers from 1 to n)
nyro_0
2
f 0=[[]]tak się składa, że ​​jest to krótszy przypadek podstawowy niż f 1=[[1]]:)
Lynn
@xyLe_ Wykorzystano rekurencyjną podstawową skrzynkę.
xnor
Ach, masz rację, mój zły
nyro_0
10

Python, 56 bajtów

f=lambda n:[x+[n-i]for i in range(n)for x in f(i)]or[[]]

Cykliczna rozwiązanie: zamawiane partycje nsą podział niektóre mniejsze iz 0<=i<n, a następnie pozostałą n-ijako ostatniego elementu. W przypadku podstawowym n=0ma tylko pustą partycję.

xnor
źródło
Prosty, mały, a mimo to niezwykle czytelny. Właśnie to uwielbiam w Pythonie.
driima
10

Python 2, 61 bajtów

f=lambda n,s='1,':1/n*[eval(s)]or f(n-1,'1+'+s)+f(n-1,'1,'+s)

To nie jest najkrótsza, ale naprawdę podoba mi się ta metoda, ponieważ jest taka dziwna.

Rekurencyjnie generuje i ocenia 2**(n-1)ciągi znaków, takie jak

1+1+1+1,
1,1+1+1,
1+1,1+1,
1,1,1+1,
1+1+1,1,
1,1+1,1,
1+1,1,1,
1,1,1,1,

dla n=4. Te ciągi są przetwarzane na krotki reprezentujące wszystkie partycje. Pomiędzy dwoma dowolnymi 1 jest albo a +, łączące je w jedną liczbę, albo a ,, dzielące sąsiednie sekcje.

xnor
źródło
Najlepsza nierekurencyjna wersja, jaką mogłem zrobić, toimport re lambda n:map(lambda n:map(len,re.finall('10*',bin(n))),range(1<<n-1,1<<n))
Neil
1
Wyjaśnienie kodu naprawdę sprawi, że będzie piękny.
Noman pouigt
8

JavaScript (Firefox 30-57), 63 bajty

f=n=>n?[for(i of Array(n).keys())for(a of f(i))[n-i,...a]]:[[]]
Neil
źródło
12
Firefox 30+ brzmi jak specjalna przeglądarka dla bardziej dojrzałych użytkowników Internetu.
Martin Ender
Prawdopodobnie nie będzie krótszy niż ten ...
ETHproductions
W jakikolwiek sposób można to odznaczyć dla JavaScript w innych przeglądarkach?
driima
Inna odpowiedź @Eternity mogę port @ XNOR za wami f=n=>n<2?[[1]]:f(n-1).map(([n,...a])=>r.push([1+n,...a],[1,n,...a]),r=[])&&r.
Neil
6

Mathematica, 40 bajtów

Join@@Permutations/@IntegerPartitions@#&

Wbudowane przez Mathematica partycje całkowite nie dają wszystkich uporządkowanych partycji, więc musimy wygenerować wszystkie możliwe permutacje każdej z nich, a następnie spłaszczyć wynik.

Martin Ender
źródło
6

CJam , 17 14 bajtów

ri"X)"m*{~]p}/

Wypróbuj online!

Wyjaśnienie

Wiem, że powiedziałem, że używanie produktu kartezjańskiego jest dłuższe, ale ostatecznie znalazłem sposób na bardziej efektywne korzystanie z niego. Myślę, że oba podejścia są interesujące same w sobie, dlatego umieszczam je w osobnych postach.

Nadal opiera się to na założeniu, że możemy wybierać nczasy między dołączeniem a 1do bieżącej partycji lub zwiększenie ostatniego elementu bieżącej partycji. W tym rozwiązaniu robimy to, generując 2 n-1 różnych programów, które odpowiadają tym różnym wyborom.

ri      e# Read input and convert to integer N.
        e# Decrement.
"X)"m*  e# Get all strings of length N which consist of 'X' and ')'. If
        e# we treat these strings as CJam code then 'X' pushes a 1 and ')'
        e# increments the top of the stack.
        e# Note that some of these strings will begin with an increment that
        e# doesn't have anything on the stack to work with. This will result in
        e# an error and terminate the program. Luckily, the programs are ordered
        e# such that all programs starting with 'X' are first in the list, so
        e# we get to print all the 2^(N-1) permutations before erroring out.
{       e# For each of these programs (well for the first half of them)...
  ~     e#   Evaluate the string as CJam code. This leaves the partition as
        e#   individual integers on the stack.
  ]p    e#   Wrap the stack in a list and pretty-print it.
}/
Martin Ender
źródło
Spojrzałem na to i pomyślałem: „ To nie może być poprawne, dałoby błąd, gdy ocenia pierwszy ciąg znaków, który zaczyna się od) ”. Więc dodałem edi przetestowałem. +1 za kreatywne nadużycie błędu.
Peter Taylor
6

Galaretka , 7 6 bajtów

-1 bajt dzięki @Dennis (konwertuj z unary ḅ1, zamiast sumy dla każdego dla każdego S€€)

1ẋŒṖḅ1

TryItOnline

W jaki sposób?

1ẋŒṖḅ1 - Main link: n          e.g. 4
1ẋ     - repeat 1 n times          [1,1,1,1]
  ŒṖ   - partitions of a list     [[[1],[1],[1],[1]], [[1],[1],[1,1]], [[1],[1,1],[1]],
                                   [[1],[1,1,1]],     [[1,1],[1],[1]], [[1,1],[1,1]],
                                   [[1,1,1],[1]],     [[1,1,1,1]]]
    ḅ1 - from base 1 (vectorises)  [[1,1,1,1],        [1,1,2],         [1,2,1],
                                   [1,3],             [2,1,1],         [2,2],
                                   [3,1],             [4]]
Jonathan Allan
źródło
5

Pure Bash, 51

To jest część doskonałej odpowiedzi @ xnor , wykorzystującej wiele poziomów rozszerzeń bash, aby osiągnąć pożądany rezultat:

a=$[10**($1-1)]
eval echo \$[${a//0/{+,']\ $[}1'}],

Ideone.

  • Pierwszy wiersz jest po prostu rozszerzeniem arytmetycznym w celu utworzenia zmiennej $azawierającej 1następujące po nim n-1zera.
  • Pierwsze rozszerzenie ${a//0/{+,']\ $[}1'}zamienia każde 0na $akopie ciągu {+,']\ $[}1'. Zatem n = 4 otrzymujemy ciąg1{+,']\ $[}1'{+,']\ $[}1'{+,']\ $[}1'
  • Jest to poprzedzone $[i po tym, ],aby dać$[1{+,']\ $[}1'{+,']\ $[}1'{+,']\ $[}1]
  • To rozszerzenie nawiasu klamrowego, które się rozwija $[1+1+1+1], $[1+1+1] 1, $[1+1] $[1+1], $[1+1] 1 1,...
  • Jest to wreszcie rozszerzane arytmetycznie, aby dać wymagany wynik.

Ostrożne stosowanie cudzysłowów, ucieczka przed odwrotnym ukośnikiem i evalzapewnienie, że rozszerzenia występują we właściwej kolejności.

Cyfrowa trauma
źródło
4

Rubin, 61 bajtów

f=->n{n<1?[[]]:(1..n).map{|i|f[n-i].map{|x|x<<i}}.flatten(1)}

bez golfa

f=->n{
  n < 1 ?
    [[]]
  :
    (1..n).map { |i|
      f[n-i].map { |x|
        x << i
      }
    }.flatten(1)
}

stosowanie

p f[4]
# => [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]]
cia_rana
źródło
2
Cześć! Czy mógłbyś dodać trochę wyjaśnień dla ludzi (takich jak ja), którzy nie znają Ruby?
AdmBorkBork
x<<ijest krótszy niż [i]+x.
m-chrzan
@ TimmyD Dodałem nieoznakowany kod i sposób użycia.
cia_rana
@ m-chrzan Dzięki za radę! Zredagowałem to.
cia_rana
Każdy powód .flatten(1)nie jest .flatten 1?
Cyoce,
3

Brachylog , 20 bajtów

~lL#++?,L:=f:{:0x}ad

Wypróbuj online!

Wyjaśnienie

Jest to sytuacja, w której można by pomyśleć, że języki deklaratywne byłyby dobre, ale z powodu przeciążenia +i trudności w pisaniu predykatu sumującego, który odpowiednio propaguje ograniczenia, nie robią tego.

~lL                     L is a list of length Input
  L#+                   L is a list of non-negative integers
  L  +?,                The sum of the elements of L results in the Input
        L:=f            Find all values for the elements of L which satisfy those constraints
            :{:0x}a     Remove all 0s from each sublist of the result of Findall
                   d    Remove all duplicate sublists
Fatalizować
źródło
Myślę, że to będzie rozprzestrzeniać się o wiele szybciej, jeśli skupić się na pozytywnych całkowitymi, niech długość Lbyć pomiędzy 1 i wejścia.
mat
@mat Tak właśnie zrobiłem, ale jest to dłuższe . Ponieważ +działa również na pojedynczej liczbie całkowitej, muszę wymusić, .aby być listą ##, a ponieważ +działa również na liście list, muszę narzucić, że elementami .są liczby całkowite :#$a.
Fatalize
Tak więc kluczową kwestią jest wadliwość struktur danych: kiedy zmienna pojawia się jako argument operacji wektoryzujących, nie można stwierdzić, czy zmienna oznacza pojedynczą liczbę całkowitą, czy listę (ewentualnie zagnieżdżoną). Jest to trudny problem i może istnieć elegancki sposób na rozwiązanie tego, zaczynając od oryginalnej wersji i szukając odpowiednich konstrukcji językowych, które mogłyby to uprościć. Dobra robota w każdym razie!
mat
3

CJam , 19 bajtów

Lari{_1af.+1@f+|}*p

Wypróbuj online!

Wyjaśnienie

CJam nie ma użytecznego wbudowanego kombinatora dla partycji całkowitych. Zrobimy to ręcznie. Aby znaleźć wszystkie uporządkowane partycje liczb całkowitych n, możemy spojrzeć na ich listę ni rozważyć każdy możliwy sposób wstawienia separatorów. Następnie zsumujemy 1s w każdej sekcji. Przykład dla n = 3:

1 1 1 => 3
1 1|1 => 2|1
1|1 1 => 1|2
1|1|1 => 1|1|1

Próbowałem użyć produktu kartezjańskiego do wygenerowania wszystkich tych separatorów, ale skończyło się to na 21 bajtach. Zamiast tego wróciłem do tej starej techniki generowania zestawów mocy (jest to oparte na starej odpowiedzi Dennisa, ale nie mogę jej teraz znaleźć). Pomysł jest następujący: aby wygenerować wszystkie partycje, możemy zacząć od pustej listy. Potem nmożemy podjąć decyzję binarną: albo dołączamy a 1(odpowiada separatorowi w powyższym przykładzie), albo zwiększamy ostatnią wartość listy (odpowiada to brakowi separatora). Aby wygenerować wszystkie partycje, po prostu wykonujemy obie operacje na każdym kroku i zachowujemy wszystkie możliwe dane wyjściowe na następny krok. Okazuje się, że w CJam przyspieszenie i zwiększenie pierwszego elementu jest krótsze, ale zasada pozostaje taka sama:

La       e# Push [[]] onto the stack. The outer list will be the list of
         e# all possible partitions at the current iteration, and we initialise
         e# it to one empty partition (basically all partitions of 0).
ri       e# Read input and convert to integer N.
{        e# Repeat this N times...
  _      e#   Duplicate the list of partitions of i-1.
  1af.+  e#   Increment the first element in each of these. This is done
         e#   by performing a pairwise addition between the partition and [1].
         e#   There is the catch that in the first iteration this will turn
         e#   the empty array into [1], so it's equivalent to the next step.
  1@f+   e#   Pull up the other copy of the list of partitions of i-1 and
         e#   prepend a 1 to each of them.
  |      e#   Set union. This gets rid of the duplicate result from the first
         e#   iteration (in all other iterations this is equivalent to concatenating
         e#   the two lists).
         e#   Voilà, a list of all partitions of i.
}*
p        e# Pretty-print the result.
Martin Ender
źródło
3

T-SQL, 203 bajty

Gra w golfa:

USE master
DECLARE @ INT=12

;WITH z as( SELECT top(@)cast(number+1as varchar(max))a FROM spt_values WHERE'P'=type),c as(SELECT a*1a,a b FROM z UNION ALL SELECT c.a+z.a,b+','+z.a FROM c,z WHERE c.a+z.a*1<=@)SELECT b FROM c WHERE a=@

Nie golfowany:

USE master --needed to make sure it is executed from the correct database
DECLARE @ INT=12

;WITH z as
(
  SELECT top(@)cast(number+1as varchar(max))a
  FROM spt_values
  WHERE'P'=type
),c as
(
  SELECT a*1a,a b
  FROM z
  UNION ALL
  SELECT c.a+z.a,b+','+z.a
  FROM c,z
  WHERE c.a+z.a*1<=@
)
SELECT b 
FROM c
WHERE a=@

Skrzypce

t-clausen.dk
źródło
3

Mathematica 10.0, 44 bajty

Próba bez użycia wbudowanych funkcji partycji. Z każdej uporządkowanej partycji o rozmiarze k generowane są dwie kolejne partycje k + 1 : jedna przez dodanie 1, a druga przez zwiększenie pierwszej wartości.

Nest[##&[{1,##},{#+1,##2}]&@@@#&,{{1}},#-1]&

Zabawniejszy, ale niestety o 2 bajty dłuższy sposób realizacji tego samego pomysłu:

#@{1}&/@Tuples[Prepend[1]@*MapAt[#+1&,1],#-1]&
feersum
źródło
@alephalpha Nie, to by nie pomogło, ponieważ musiałbym wtedy zmienić MapAtindeks na -1.
feersum
3

05AB1E , 14 12 bajtów

Zaoszczędzono 2 bajty dzięki Adnan

>G¹LNãvyO¹Q—

Wyjaśnienie

>G              # for N in range(1..input)
  ¹L            # range(1, input)
    Nã          # cartesian product with N (all combinations of length N)
      v         # for each resulting list
       yO¹Q—    # if it's sum equals the input print it

Wypróbuj online!

Odpowiednie rozwiązanie jest o 2 bajty krótsze w 2sable .

2sable , 10 bajtów

>GLNãvyOQ—

Wypróbuj online!

Emigna
źródło
Możesz użyć zamiast iy,:).
Adnan
@Adnan: Dzięki! Zapomniałem o tym.
Emigna
3

Haskell, 41 bajtów

f 1=[[1]]
f n=do a:b<-f$n-1;[1:a:b,a+1:b]

Nie najkrótsze rozwiązanie Haskell, ale podoba mi się, że nie używa [..]zakresów. Zamiast tego rekurencyjnie oblicza partycjen jako partycje n-1z nową 1 na początku lub pierwszą wartością o jedną wyższą. To wyjaśnia, dlaczego istnieje 2^(n-1).

xnor
źródło
3

Mathematica, 53 bajty

Nie bije odpowiedzi Martina Endera, która korzysta z wbudowanego IntegerPartitions funkcji (a wbudowane są dla mnie całkowicie w porządku). (Nie jest to także odpowiedź na feersum, którego nie widziałem aż do późna.) Chciałem jednak ćwiczyć funkcję rekurencyjną w golfa.

If[#<1,{{}},Join@@Table[#~Append~j&/@#0[#-j],{j,#}]]&

Rekurencyjnie generuje wszystkie kompozycje, generując wszystkie możliwe liczby końcowe, ja następnie wywołując, #-jgdzie #jest dane wejściowe.

Greg Martin
źródło
Możesz zaoszczędzić kilka bajtów, definiując operatora używającego Arrayzamiast Tablei unikającego Append, używając listy i Apply:±0={{}};±n_:=Join@@Array[{##,n-+##}&@@@±#&,n,0]
Martin Ender
Co ma @@zrobić?
Cyoce,
Zastępuje „głowę” wyrażenia. Na przykład f@@g[a,b]ocenia na f[a,b]. Wykorzystujemy tutaj fakt, że lista taka jak { { {1,1,1}, {2,1} } , { {1,2} }, { {3} } }niewidzialna ma głowę List; więc Join@@{ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } }ocenia do Join@@List[ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } ]oceny do Join[ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } ]oceny { {1,1,1}, {2,1}, {1,2}, {3} }.
Greg Martin
3

Siatkówka , 32 bajty

Liczba bajtów zakłada kodowanie ISO 8859-1.

.+
$*
+%1`1
!$'¶$`,!
!+
$.&
A`^,

Wypróbuj online!

Wyjaśnienie

Działa to podobnie do mojej odpowiedzi CJam . Przeglądamy listę Ni na każdej pozycji podejmujemy obie gałęzie decyzji binarnej a) zwiększamy ostatnią wartość lub b) rozpoczynamy nową wartość od 1.

Scena 1

.+
$*

Przekształć dane wejściowe w jednoargumentowe.

Etap 2

+%1`1
!$'¶$`,!

+Mówi Retina aby wykonać ten etap w pętli aż wyjście przestaje się zmieniać. %Mówi to, aby podzielić wejście do linii przed nałożeniem na scenę i połączyć je z powrotem razem później. Umieszczając %po+ , Retina dzieli się i ponownie dołącza po każdej iteracji. Jedna iteracja etapu podejmuje jedną z tych decyzji, o których wspomniałem, i tym samym rozwidla obecny zestaw partycji.

To, jak to naprawdę działa, polega na tym, że pasuje do 1(ale tylko pierwszego, jak wskazano 1przed tyłem) i zamienia go na !(który użyjemy jako jednoznacznej cyfry naszego wyjścia), a następnie pozostałe 1s w tym wierszu (zwiększa ostatnią wartość). Następnie w innym wierszu ( ) wypisuje przedrostek bieżącej linii, a następnie ,!wstawia separator, a następnie rozpoczyna następną wartość od 1.

Etap 3

!+
$.&

Konwertuje to liczby !całkowite na dziesiętne, zastępując je ich długością.

Etap 4

A`^,

I w końcu zauważamy, że wygenerowaliśmy dwa razy więcej wierszy, niż chcieliśmy, a połowa z nich zaczyna się od ,(tych, w których początkowo podjęliśmy decyzję o podziale, chociaż nie było już nic do podzielenia). Dlatego odrzucamy wszystkie linie zaczynające się od ,.

Martin Ender
źródło
3

Perl, 44 bajty

Zawiera +3 za -n(używa kodu $'i $0dlatego nie mogą być uruchamiane jako -epoleceń)

Podaj numer do partycji na STDIN:

partitions.pl <<< 4

partitions.pl

#!/usr/bin/perl -n
$_=$&-$_.",$_$'",do$0for/\d+/..$&-1;print

Jeśli nie przeszkadza ci dodatkowe spacje na końcu wiersza i dodatkowa nowa linia, to 42 bajtowe rozwiązanie również działa (działa jako perl -M5.010 partitions.pl):

#!/usr/bin/perl -n
$_=$`-$_." $_ $'",do$0for/\s/..$_-1;say
Ton Hospel
źródło
3

Julia, 113 bajtów

f(N)=unique(reduce(vcat,(map(x->[permutations(x)...],[vcat([1 for _=i+1:N],sum([1 for _=N-i:N-1])) for i=1:N]))))

Rozwiązanie nierekurencyjne

Wyjaśnił:

  1. [vcat([1 for _=i+1:N],sum([1 for _=N-i:N-1])) for i=1:N] zbuduj zestaw list, które sumują się do N, których permutacje będą przypominały rozwiązanie (np. dla N = 4: [[1,1,1,1], [1,1,2], [1,3], [4 ]])
  2. map(x->[permutations(x)...],) Oblicz wszystkie permutacje
  3. reduce(vcat,) połącz je w listę list
  4. unique() filtruj duplikaty
nyro_0
źródło
Wymagamy, aby zgłoszenia były pełnymi programami lub funkcjami, więc w takim przypadku musisz wziąć Njako dane wejściowe. Możesz zrobić funkcję lambda, przygotowując N->ją kosztem 3 bajtów.
Alex A.
@AlexA. ah, przepraszam, że f(N)=zgubiłem się podczas kopiowania, miałem to podczas liczenia bajtów
nyro_0,
2

MATL , 15 bajtów

:"G:@Z^t!XsG=Y)

Wypróbuj online!

Wyjaśnienie

Biorąc pod uwagę dane wejściowe n, oblicza to moc kartezjańską z rosnącymi wykładnikami kod 1do n; i dla każdego wykładnika kwybiera krotki o sumie równej wejściowej.

:       % Take input n implicitly and push range [1 2 ... n]
"       % For each k in that range
  G:    %   Push [1 2 ... n] again
  @     %   Push k
  Z^    %   Cartesian power. Gives 2D array, say A, with each k-tuple in a row.
  t     %   Duplicate
  !     %   Transpose
  Xs    %   Sum of each column. Gives a row vector
  G=    %   True for entries that equal the input
  Y)    %   Use as logical vector into the rows of array A
        % End implicitly
        % Display stack implicitly
Luis Mendo
źródło
1

Lua 214 203 182 bajtów

function g(m, l, n,c)for i=1,m do if i+n < m then l[#l+1]=i;g(m,l,n+i,c+1)elseif i+n == m then l[#l+1]=i;print(unpack(l))end end for k=c,#l do l[k]=nil end end g(io.read()*1,{},0,0)

Wersja nierozdzielona.

function g(m, l, n,c)
    for i=1,m do 
        if i+n < m then 
            l[#l+1]=i
            g(m,l,n+i,c+1)
        elseif i+n == m then 
            l[#l+1]=i
            print(unpack(l))
        end 
    end 
    for k=c,#l do 
        l[k]=nil 
    end 
end 
g(io.read()*1,{},0,0)

Znaleziono zbłąkane białe znaki i usunęliśmy niepotrzebną zmienną do bezpiecznych 11 bajtów. jak się okazuje, table.insert () jest bajtem nieefektywnym

soczewki
źródło
1

PHP, 125 bajtów

for($i=$n=$argv[1];$i<=str_repeat(1,$n);$i++)if(array_sum($a=str_split($i))==$n&!strpos($i,"0"))$r[]=$a;echo json_encode($r);

-4 bajtów print_r($r);zamiastecho json_encode($r); na wyjście

rozwiązanie rekurencyjne z 250 bajtami

function f($n){global$a;foreach($a as$x)foreach(range(1,$n)as$y)$a[]=array_merge((array)$x,[$y]);if(--$n)f($n);}$a=range(1,$w=$argv[1]);f($w-1);foreach($a as$z)if(array_sum((array)$z)==$w)$c[join("-",(array)$z)]=$z;echo json_encode(array_values($c));
Jörg Hülsermann
źródło
1

Prolog, 81 bajtów + 6 bajtów do wywołania

L*L.
[H|T]*L:-H>1,M is H-1,[M,1|T]*L.
[H,K|T]*L:-H>1,M is H-1,N is K+1,[M,N|T]*L.

Wypróbuj online!
Zadzwoń za pomocą [4]*L., powtórz za pomocą; aż wszystkie rozwiązania zostaną przedstawione.

Alternatywnie, jeśli wielokrotne naciskanie ;nie jest w porządku (lub powinno zostać dodane do liczby bajtów), połączenie, z bagof(L,[4]*L,M).którym dodaje 17 bajtów dla połączenia.

SQB
źródło
1

J , 30 26 bajtów

#&1<@(+/;.1)~2#:@(+i.)@^<:

Działa poprzez podzielenie listy jednych n przy użyciu wartości binarnych 2 n .

Wypróbuj online!

Wyjaśnienie

#&1<@(+/;.1)~2#:@(+i.)@^<:  Input: n
                        <:  Decrement n
             2         ^    Compute 2^(n-1)
                 (   )@     Operate on that
                   i.         Make the range [0, 1, ..., 2^(n-1)-1]
                  +           Add 2^(n-1) to each in that range
              #:@           Convert each in that range to binary
#&1                         Make n copies of 1 (n in unary)
     (     )~               Operate over each row on RHS and unary n on LHS
        ;.1                   Chop unary n starting at each 1
      +/                        Reduce by addition on each chop
   <@                           Box the sums of each chop
mile
źródło
0

Właściwie 17 16 bajtów

Ta odpowiedź jest częściowo oparta na odpowiedzi MATL Luisa Mendo . Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!

;╗R`╜R∙i`M`Σ╜=`░

Ungolfing

         Implicit input n.
;╗       Duplicate n and save a copy of n to register 0.
R        Take the range of [1..n].
`...`M   Map the following function over the range. Variable k.
  ╛R       Push n from register 0 and take the range [1..n] again.
  ∙        Take the k-th Cartesian power of the range.
  i        Flatten that product.
`...`░   Push values of the previous map where the following function returns a truthy value.
          Variable L.
  Σ        Push sum(L).
  ╜        Push n from register 0.
  =        Check if sum(L) == n.
         Implicit return.
Sherlock9
źródło
0

Właściwie 17 16 15 bajtów

Jest to interesujący widelec odpowiedzi Martina Endera na CJam (ten z kartezjańskim produktem), z tą różnicą we wdrożeniu, która moim zdaniem była interesująca. Gdy jeden z ciągów Martina zaczyna się od przyrostu, błędy uniemożliwiają ocenę tego ciągu. W rzeczywistości błąd jest pomijany, a łańcuch jest mimo to oceniany. Ostatecznie daje to kompozycje każdego kw zakresie [1..n].

Zamiast próbować usunąć dodatkowe kompozycje, wziąłem n-1th kartezjańską moc "1u"dołączonego"1" na początku każdego ciągu. Ta sztuczka daje tylko kompozycjen . Jest niestety dłuższy niż odpowiedź Martina.

Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!

D"1u"∙`1@Σ£ƒk`M

Ungolfing

         Implicit input n.
D        Decrement n.
"1u"∙    Take the (n-1)th Cartesian power of the string "1u".
          In Actually, 1 pushes 1 to the stack and u is increment.
`...`M   Map the following function over the Cartesian power. Variable s.
  1@       Push a 1 to be used later.
  Σ        Summing a list of chars joins the chars into one string.
  £ƒ       Turn s into a function and call it immediately on the 1 in the stack.
  k        Take the whole stack and wrap in a list. This is a composition of n.
         Implicit return.
Sherlock9
źródło