Daftar semua partisi n

23

Tantangannya adalah untuk membuat daftar semua partisi yang dipesan (komposisi (kombinatorik)) dari bilangan bulat positif yang diberikan n. Ini adalah daftar nomor dari 1ke nyang jumlahnya adalah n. Misalnya, diberi masukan n = 4, hasilnya harus:

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

Hasilnya bisa dalam urutan apa pun, tetapi harus berisi setiap partisi yang dipesan satu kali. Ini berarti bahwa untuk n = 4, [1, 1, 2], [1, 2, 1]dan [2, 1, 1]semua harus menjadi bagian dari hasilnya.

Ini kode JavaScript saya sendiri yang mencapai ini:

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);
    });
}

Golfed, ES6 ( 169 167 119 109 105 89 85 bytes ):

n=>n?[].concat(...[...Array(n)].map((x,i)=>i+1).map(b=>m(n-b).map(a=>[b,...a]))):[[]]
driima
sumber
3
Selamat datang di situs ini! Anda perlu menentukan kriteria kemenangan. Golf kode mungkin? Juga, apakah harus dalam urutan tertentu? Jika demikian, bagaimana urutan didefinisikan secara umum? Saya pikir tatanan leksikografis akan lebih bermakna; atau lebih baik lagi, izinkan pesanan apa pun. Anda mungkin ingin menggunakan kotak pasir untuk tantangan di masa depan sebelum mempostingnya di sini
Luis Mendo
3
@Fatalize Here [2 1 1] berbeda dari [1 2 1], tidak seperti di sana. Saya curiga pendekatannya mungkin sangat berbeda
Luis Mendo
3
Bagi mereka yang ditutup sebagai penipu: apakah Anda yakin perbedaan yang ditunjukkan dalam komentar tidak relevan? Saya tidak memilih untuk membuka kembali, karena saya pikir palu akan bekerja ke arah itu juga
Luis Mendo
3
Saya sarankan belum menerima jawaban (meskipun Anda dapat mengubahnya kapan saja) karena melihat pertanyaan yang diterima di halaman depan mungkin membuat orang berpikir itu sudah berakhir dan tidak berpartisipasi.
xnor
5
Istilah biasa untuk partisi yang dipesan ini adalah " komposisi ".
Greg Martin

Jawaban:

7

Pyth, 7 6 byte

Solusi 7 byte:

Pyth memiliki built-in partisi integer ./, jadi 5 dari 7 byte mendapatkan urutan.

{s.pM./

Cobalah online!

Penjelasan:

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

Solusi 6 byte:

Jika Anda memiliki daftar, ./akan dihitung dengan pemesanan; yang tersisa hanyalah membuat daftar angka lagi.

lMM./m

Cobalah online!

Penjelasan:

     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.
sumber
Luar biasa. Ini yang terkecil yang pernah saya lihat sejauh ini!
driima
11

Haskell, 37 byte

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

xnatau menyimpan dua byte.

Lynn
sumber
1
Sepertinya lebih mudah f n=[a:x|a<-[1..n],x<-f$n-a]lebih pendek.
xnor
Anda tidak perlu cek nol ( given positive integer n ... numbers from 1 to n)
nyro_0
2
f 0=[[]]kebetulan merupakan alas yang lebih pendek dari f 1=[[1]]:)
Lynn
@xyLe_ Ini menggunakan kasus dasar rekursif.
xnor
ah yakin, Anda benar, salah saya
nyro_0
10

Python, 56 byte

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

Solusi rekursif: Partisi yang diurutkan nadalah partisi idengan yang lebih kecil 0<=i<n, diikuti oleh sisanya n-isebagai elemen terakhir. Untuk kasus dasar, n=0hanya memiliki partisi kosong.

Tidak
sumber
Sederhana, kecil, namun masih bisa dibaca. Itulah yang saya sukai tentang Python.
driima
10

Python 2, 61 byte

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

Ini bukan yang terpendek, tapi saya sangat suka metode ini karena sangat aneh.

Secara rekursif menghasilkan dan mengevaluasi 2**(n-1)string, seperti

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,

untuk n=4. String ini mengevaluasi tupel yang mewakili semua partisi. Antara dua 1 adalah salah satu +, bergabung dengan mereka menjadi satu nomor, atau a ,, membelah bagian yang berdekatan.

Tidak
sumber
Versi non-rekursif terbaik yang bisa saya lakukan adalahimport re lambda n:map(lambda n:map(len,re.finall('10*',bin(n))),range(1<<n-1,1<<n))
Neil
1
Penjelasan dengan kode itu akan membuatnya indah.
noman pouigt
8

JavaScript (Firefox 30-57), 63 byte

f=n=>n?[for(i of Array(n).keys())for(a of f(i))[n-i,...a]]:[[]]
Neil
sumber
12
Firefox 30+ terdengar seperti browser khusus untuk pengguna internet yang lebih dewasa.
Martin Ender
Mungkin tidak lebih pendek dari ini ...
ETHproduksi
Adakah cara ini dapat dicabut untuk JavaScript di browser lain?
driima
@Eternity Saya dapat port @ jawaban lain xnor untuk Anda: 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 byte

Join@@Permutations/@IntegerPartitions@#&

Built-in untuk partisi integer Mathematica tidak memberikan semua partisi yang dipesan , jadi kami harus membuat semua permutasi yang mungkin dari masing-masing partisi tersebut , dan kemudian meratakan hasilnya.

Martin Ender
sumber
6

CJam , 17 14 byte

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

Cobalah online!

Penjelasan

Saya tahu saya mengatakan bahwa menggunakan produk Cartesian lebih lama, tetapi saya akhirnya menemukan cara untuk menggunakannya dengan lebih efisien. Saya pikir kedua pendekatan itu menarik dengan caranya sendiri, jadi saya menempatkannya di pos terpisah.

Ini masih didasarkan pada gagasan bahwa, kita dapat memilih nwaktu antara menambahkan a 1ke partisi saat ini atau untuk menambah elemen terakhir dari partisi saat ini. Dalam solusi ini, kami melakukan ini dengan menghasilkan 2 n-1 program berbeda yang sesuai dengan pilihan yang berbeda ini.

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
sumber
Saya melihat ini dan berpikir " Itu tidak benar, itu akan memberikan kesalahan ketika mengevaluasi string pertama yang dimulai dengan) ". Jadi saya menambah eddan menguji. +1 untuk penyalahgunaan kesalahan kreatif.
Peter Taylor
6

Jelly , 7 6 byte

-1 byte terima kasih kepada @Dennis (konversi dari unary ḅ1, bukan penjumlahan untuk masing-masing S€€)

1ẋŒṖḅ1

TryItOnline

Bagaimana?

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
sumber
5

Pure Bash, 51

Ini adalah port jawaban brilian @ xnor , menggunakan beberapa level ekspansi bash untuk mencapai hasil yang diinginkan:

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

Ideone.

  • Baris pertama hanyalah ekspansi aritmatika untuk membuat variabel yang $aberisi 1diikuti oleh n-1nol.
  • Ekspansi pertama ${a//0/{+,']\ $[}1'}menggantikan masing-masing 0di $adengan salinan string {+,']\ $[}1'. Jadi n = 4 kita mendapatkan string1{+,']\ $[}1'{+,']\ $[}1'{+,']\ $[}1'
  • Ini diawali dengan $[dan postfixed dengan ],memberi$[1{+,']\ $[}1'{+,']\ $[}1'{+,']\ $[}1]
  • Ini adalah ekspansi penjepit yang diperluas ke $[1+1+1+1], $[1+1+1] 1, $[1+1] $[1+1], $[1+1] 1 1,...
  • Ini akhirnya diperluas secara aritmatika untuk memberikan hasil yang diperlukan.

Hati-hati menggunakan tanda kutip, garis miring terbalik dan evalmemastikan bahwa ekspansi terjadi dalam urutan yang benar.

Trauma Digital
sumber
4

Ruby, 61 byte

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

ungolfed

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

pemakaian

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
sumber
2
Hai! Bisakah Anda menambahkan sedikit penjelasan untuk orang-orang (seperti saya) yang tidak terbiasa dengan Ruby?
AdmBorkBork
x<<ilebih pendek dari [i]+x.
m-chrzan
@TimmyD Saya menambahkan kode yang tidak dipisahkan dan penggunaannya.
cia_rana
@ m-chrzan Terima kasih atas saran Anda! Saya mengeditnya.
cia_rana
Apa alasannya .flatten(1)bukan .flatten 1?
Cyoce
3

Brachylog , 20 byte

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

Cobalah online!

Penjelasan

Ini adalah situasi di mana Anda akan berpikir bahasa deklaratif akan bekerja dengan baik, tetapi karena kelebihan beban +dan kesulitan dalam menulis predikat penjumlahan yang menyebarkan kendala dengan benar, mereka tidak melakukannya.

~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
Fatalisasi
sumber
Saya pikir ini akan menyebarkan jauh lebih cepat jika Anda berfokus pada yang positif bilangan bulat, dan membiarkan panjang Lmenjadi antara 1 dan masukan.
mat
@ ah Inilah yang awalnya saya lakukan tetapi ini lebih lama . Karena +juga bekerja pada bilangan bulat tunggal, saya perlu memaksakan .untuk menjadi daftar ##, dan karena +juga bekerja pada daftar daftar, saya perlu memaksakan bahwa elemen-elemen .adalah bilangan bulat dengan :#$a.
Fatalkan
Jadi masalah utama adalah ketidakteraturan dari struktur data: Ketika sebuah variabel muncul sebagai argumen operasi yang membuat vektor, Anda tidak bisa mengatakan apakah variabel tersebut merupakan singkatan dari integer tunggal atau daftar (mungkin bersarang). Ini adalah masalah yang sulit, dan mungkin ada cara yang elegan untuk menyelesaikan ini, mulai dari versi asli Anda dan mencari konstruksi bahasa yang sesuai yang dapat menyederhanakan ini. Bagaimanapun, kerja bagus!
mat
3

CJam , 19 byte

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

Cobalah online!

Penjelasan

CJam tidak memiliki kombinatorik yang berguna untuk partisi integer. Jadi kami akan melakukan ini secara manual. Untuk menemukan semua partisi memerintahkan bilangan bulat n, kita dapat melihat daftar nyang dan mempertimbangkan segala cara yang mungkin untuk memasukkan pemisah. Kemudian kita akan menjumlahkan 1di setiap bagian. Contoh untuk n = 3:

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

Saya mencoba menggunakan produk Cartesian untuk menghasilkan semua pemisah ini, tetapi itu berakhir pada 21 byte. Sebaliknya saya kembali ke teknik lama ini untuk menghasilkan set daya (ini didasarkan pada jawaban tua Dennis tapi saya tidak dapat menemukannya sekarang). Idenya adalah ini: untuk menghasilkan semua partisi kita bisa mulai dari daftar kosong. Maka nkali kita dapat membuat keputusan biner: kita menambahkan a 1(sesuai dengan pemisah pada contoh di atas) atau kita menambah nilai terakhir dari daftar (sesuai dengan tidak memiliki pemisah). Untuk menghasilkan semua partisi, kami cukup melakukan kedua operasi di setiap langkah dan menjaga semua output yang mungkin untuk langkah berikutnya. Ternyata di CJam, menambahkan dan menambah elemen pertama lebih pendek, tetapi prinsipnya tetap 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
sumber
3

T-SQL, 203 byte

Golf:

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=@

Tidak Disatukan:

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=@

Biola

t-clausen.dk
sumber
3

Mathematica 10.0, 44 byte

Upaya tanpa menggunakan bawaan yang terkait dengan partisi. Dari setiap partisi ukuran k yang diurutkan , dua partisi pengganti k + 1 dihasilkan: satu dengan menambahkan sebelumnya 1, dan yang lainnya dengan menambah nilai pertama.

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

Cara yang lebih lucu, tetapi sayangnya 2 byte lebih lama dalam mengimplementasikan ide yang sama:

#@{1}&/@Tuples[Prepend[1]@*MapAt[#+1&,1],#-1]&
feersum
sumber
@alephalpha Tidak, itu tidak membantu karena saya harus mengubah MapAtindeks ke -1.
feersum
3

05AB1E , 14 12 byte

Disimpan 2 byte berkat Adnan

>G¹LNãvyO¹Q—

Penjelasan

>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

Cobalah online!

Solusi yang sesuai adalah 2 byte lebih pendek dalam 2sable .

2sable , 10 byte

>GLNãvyOQ—

Cobalah online!

Emigna
sumber
Anda bisa menggunakan bukannya iy,:).
Adnan
@ Adnan: Terima kasih! Lupa tentang itu.
Emigna
3

Haskell, 41 byte

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

Bukan solusi Haskell terpendek, tapi saya suka itu tidak menggunakan [..]rentang. Sebaliknya, ia secara rekursif menghitung partisi nsebagai partisi n-1dengan 1 baru di awal atau nilai pertama yang lebih tinggi. Ini menjelaskan mengapa ada 2^(n-1)dari mereka.

Tidak
sumber
3

Mathematica, 53 byte

Tidak mengalahkan jawaban Martin Ender, yang menggunakan IntegerPartitionsfungsi bawaan (dan built-in benar-benar baik-baik saja bagi saya). (Juga tidak mengalahkan jawaban feersum, yang tidak saya lihat sampai terlambat.) Tetapi saya ingin mempraktikkan fungsi rekursif golf.

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

Secara rekursif menghasilkan semua komposisi, dengan menghasilkan semua angka akhir yang mungkin jdan kemudian menyebut dirinya di #-jmana #input.

Greg Martin
sumber
Anda dapat menyimpan beberapa byte dengan mendefinisikan operator menggunakan Arraybukan Tabledan menghindari Appenddengan menggunakan daftar dan Apply:±0={{}};±n_:=Join@@Array[{##,n-+##}&@@@±#&,n,0]
Martin Ender
Apa yang @@harus dilakukan
Cyoce
Ini menggantikan "kepala" dari suatu ekspresi. Misalnya, f@@g[a,b]evaluasi ke f[a,b]. Di sini kita menggunakan fakta bahwa daftar seperti { { {1,1,1}, {2,1} } , { {1,2} }, { {3} } }kasat mata memiliki kepala List; jadi Join@@{ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } }mengevaluasi untuk Join@@List[ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } ]mengevaluasi untuk Join[ { {1,1,1}, {2,1} } , { {1,2} }, { {3} } ]mengevaluasi { {1,1,1}, {2,1}, {1,2}, {3} }.
Greg Martin
3

Retina , 32 byte

Hitungan byte mengasumsikan penyandian ISO 8859-1.

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

Cobalah online!

Penjelasan

Ini bekerja mirip dengan jawaban CJam saya . Kami melewati daftar Nyang dan pada setiap posisi kami mengambil kedua cabang dari keputusan biner a) menambah nilai terakhir atau b) memulai nilai baru pada 1.

Tahap 1

.+
$*

Konversikan input ke unary.

Tahap 2

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

The +memberitahu Retina untuk melaksanakan tahap ini dalam satu lingkaran sampai output berhenti berubah. The %mengatakan itu untuk membagi masukan ke garis sebelum menerapkan panggung dan bergabung dengan mereka kembali bersama-sama setelah itu. Dengan menempatkan %setelah +, Retina membelah dan bergabung kembali setelah setiap iterasi. Satu iterasi panggung membuat salah satu keputusan yang saya sebutkan dan dengan demikian membagi dua set partisi saat ini.

Cara benar-benar bekerja adalah bahwa hal itu cocok dengan 1(tapi hanya yang pertama yang ditunjukkan dengan 1di depan backtick), dan menggantinya dengan !(yang akan kita gunakan sebagai digit unary output kami), diikuti oleh sisa 1s pada baris ini (ini menambah nilai terakhir). Kemudian pada baris lain ( ) ia mencetak awalan dari baris saat ini, diikuti oleh ,!, yang menyisipkan pemisah dan kemudian mulai nilai berikutnya di 1.

Tahap 3

!+
$.&

Ini mengubah proses dari !ke bilangan bulat desimal dengan menggantinya dengan panjangnya.

Tahap 4

A`^,

Dan akhirnya, kami perhatikan bahwa kami telah menghasilkan dua kali lebih banyak garis yang kami inginkan, dan setengah dari mereka mulai dengan ,(yang di mana kami awalnya membuat keputusan pemisahan, meskipun belum ada apa pun untuk dipisah setelah). Karenanya, kami membuang semua baris yang dimulai dengan a ,.

Martin Ender
sumber
3

Perl, 44 byte

Termasuk 3 untuk -n(menggunakan kode $'dan $0sehingga tidak dapat dijalankan sebagai -ecommandline)

Berikan nomor pada partisi di STDIN:

partitions.pl <<< 4

partitions.pl

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

Jika Anda tidak keberatan dengan ruang ekstra di akhir baris dan baris baru ekstra, solusi 42 byte ini juga berfungsi (jalankan sebagai perl -M5.010 partitions.pl):

#!/usr/bin/perl -n
$_=$`-$_." $_ $'",do$0for/\s/..$_-1;say
Ton Hospel
sumber
3

Julia, 113 Bytes

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

Solusi non-rekursif

Dijelaskan:

  1. [vcat([1 for _=i+1:N],sum([1 for _=N-i:N-1])) for i=1:N] buat serangkaian daftar yang menjumlahkan ke N, yang permutasi akan menyerupai solusi (misalnya untuk N = 4: [[1,1,1,1], [1,1,2], [1,3], [4 ]])
  2. map(x->[permutations(x)...],) Hitung semua permutasi
  3. reduce(vcat,) menggabungkannya ke dalam daftar daftar
  4. unique() filter duplikat
nyro_0
sumber
Kami meminta pengiriman untuk menjadi program atau fungsi lengkap, jadi dalam hal ini Anda harus mengambil Nsebagai masukan. Anda dapat membuat fungsi lambda dengan N->membebani dengan biaya 3 byte.
Alex A.
@AlexA. ah, maaf f(N)=hilang dalam menyalin, saya sudah memilikinya ketika menghitung byte
nyro_0
2

MATL , 15 byte

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

Cobalah online!

Penjelasan

Masukan yang diberikan n, ini menghitung kekuatan Cartesian dengan eksponen yang meningkat kdari 1ke n; dan untuk setiap eksponen kmemilih tupel yang memiliki jumlah yang sama dengan input.

:       % 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
sumber
1

Lua 214 203 182 byte

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)

Versi tidak terpecahkan.

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)

Menemukan spasi kosong dan menghapus variabel yang tidak perlu ke safe 11 byte. ternyata, table.insert () tidak efisien byte

lenscas
sumber
1

PHP, 125 Bytes

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 Bytes print_r($r);bukan echo json_encode($r);untuk output

solusi rekursif dengan 250 Bytes

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
sumber
1

Prolog, 81 byte + 6 byte untuk dipanggil

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.

Cobalah online!
Hubungi dengan [4]*L., ulangi dengan ;sampai semua solusi telah disajikan.

Atau, jika berulang kali menekan ;tidak oke (atau harus ditambahkan ke jumlah byte), panggil dengan bagof(L,[4]*L,M).yang menambahkan 17 byte untuk panggilan.

SQB
sumber
1

J , 30 26 byte

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

Bekerja dengan memisahkan daftar unary n dengan menggunakan nilai biner 2 n .

Cobalah online!

Penjelasan

#&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
mil
sumber
0

Sebenarnya, 17 16 byte

Jawaban ini sebagian didasarkan pada jawaban MATL Luis Mendo . Saran bermain golf diterima. Cobalah online!

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

Tidak melakukanolf

         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
sumber
0

Sebenarnya, 17 16 15 byte

Ini adalah pertanda menarik dari jawaban CJam Martin Ender (yang dengan produk Cartesian), dengan perbedaan dalam implementasi yang saya pikir menarik. Ketika salah satu string Martin mulai dengan kenaikan, kesalahan mencegah string yang dievaluasi. Dalam Sebenarnya, kesalahan ditekan dan string tetap dievaluasi. Ini akhirnya memberikan komposisi setiap kdalam kisaran [1..n].

Alih-alih mencoba untuk menghapus komposisi tambahan, saya mengambil n-1kekuatan Cartesian dari "1u"ditambahkan "1"ke awal setiap string. Trik ini hanya memberikan komposisi n. Sayangnya, ini lebih panjang dari jawaban Martin.

Saran bermain golf diterima. Cobalah online!

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

Tidak melakukanolf

         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
sumber