Daftar * semua * tupel!

35

Menulis sebuah program, diberi input n , akan menghasilkan semua n-tupel yang mungkin menggunakan bilangan asli.

n=1
(1),(2),(3),(4),(5),(6)...

n=2
(1,1),(1,2),(2,1),(2,2),(1,3),(3,1),(2,3),(3,2),(3,3)...

n=6
(1,1,1,1,1,1) (1,1,1,1,2,1) (1,1,1,2,1,1)... 
  • Output mungkin dalam urutan apa pun yang tidak melanggar aturan lain.
  • Program harus ditulis untuk dijalankan selamanya dan daftar semua tuple yang berlaku tepat sekali, secara teori.
    • Pada kenyataannya, program Anda akan mencapai batas dan kerusakan tipe integer Anda. Ini dapat diterima selama program akan berjalan sangat lama jika hanya tipe integer Anda yang tidak terbatas.
    • Setiap tuple yang valid harus terdaftar dalam waktu yang terbatas, jika hanya program yang diizinkan untuk menjalankan selama itu.
  • Output dapat, sesuai pilihan Anda, termasuk nol di samping bilangan asli.
  • Anda dapat memilih format output program Anda untuk kenyamanan Anda, selama pemisahan antara tupel dan angka di dalam masing-masing tuple jelas dan konsisten. (Misalnya, satu tuple per baris.)
  • Input (n) adalah bilangan bulat dari satu hingga enam. Perilaku yang diperlukan tidak ditentukan untuk input di luar kisaran ini.
  • Aturan kode-golf berlaku, kemenangan program terpendek.

Terima kasih kepada "Artemis Fowl" untuk umpan balik selama fase kotak pasir.

billpg
sumber
Saya menganggap itu valid jika ketika program crash itu menghasilkan beberapa output tambahan selain tuple yang dicetak sejauh ini, kan?
Luis Mendo
1
Haruskah kita output saat kita pergi atau akankah fungsi yang menghasilkan daftar tak terbatas pada akhir waktu cukup?
Jonathan Allan
6
"Anda dapat memilih format output program Anda untuk kenyamanan Anda, selama pemisahan antara tupel dan angka di dalam masing-masing tuple jelas dan konsisten" - dapatkah kita mengeluarkan pemisahan yang berbeda (walaupun berbeda secara konsisten) (misalnya seperti ini )?
Jonathan Allan
@ Jonathan Allan Saya harus memasukkan output dari isi yang tak terbatas dari objek itu sebagai bagian dari program.
billpg
1
Terkait (bilangan bulat, bukan bilangan asli)
Buah Esolanging

Jawaban:

24

Sekam , 2 byte

πN

Cobalah online!

Penjelasan

Nadalah daftar bilangan asli tanpa batas [1,2,3,4,... πadalah kekuatan Cartesian. Hasilnya adalah daftar daftar yang tak terbatas. Setiap daftar panjang yang diinginkan terjadi tepat satu kali karena πkeren seperti itu. Input dan output bersifat implisit.

Zgarb
sumber
1
Wow, dan ini juga tidak [1,1, n]. Apakah ada pola untuk output yang dipesannya?
billpg
1
@ billpg Ini membangun tupel secara rekursif: n- tupel diperoleh dengan mengambil produk Cartesian dari daftar asli dan daftar n-1-tupel, dalam urutan kenaikan jumlah indeks.
Zgarb
"Urutan jumlah indeks yang naik" - Bisakah Anda mengklarifikasi ini? Saya mengalami kesulitan melihat mengapa, misalnya, 2,2,2muncul setelah 4,1,2dan 5,1,1.
Jonah
2
@Jonah Rekursi bekerja seperti ini. Anda mulai dengan 1-tupel N. Untuk 2-tupel Anda mengambil produk Cartesian dengan Ndipesan dengan jumlah indeks. Di kedua daftar, masing-masing angka nberada di indeks nsehingga untuk panjang 2 hasilnya kebetulan dipesan dengan jumlah. Untuk mendapatkan 3-tupel Anda mengambil produk Cartesian Ndan daftar 2-tupel, dipesan berdasarkan jumlah indeks elemen dalam daftar ini. Itu tidak melihat jumlah tupel, ia melihat posisinya dalam daftar tupel.
Zgarb
2
"Cari tahu berbagai dimensi tak terhingga dalam tugas ini dan temukan pola yang menguranginya hingga tak terhingga, kemudian tulis sebuah program yang beralih ke pola ini." - "Hei, aku punya bawaan untuk itu!"
Fabian Röling
10

Haskell , 62 byte

([1..]>>=).(!)
0!s=[[]|s<1]
n!s=[a:p|a<-[1..s],p<-(n-1)!(s-a)]

Cobalah online!

n!smenghasilkan semua n-tuples yang dijumlahkan s.

Maka jawabannya adalah ([1..]>>=).(!), yaitu \n -> [t | s<-[1..], t<-n!s].

Ini adalah fungsi yang memetakan bilangan bulat nke daftar malas tak terbatas tupel (daftar bilangan bulat).

Lynn
sumber
5

Haskell , 50 byte

f n=[l|k<-[0..],l<-mapM([0..k]<$f)[0..n],sum l==k]

Cobalah online!

Daftar n-tupel diurutkan berdasarkan jumlah. mapMapakah angkat berat untuk menghasilkan semua n-tupel angka dari 0 hingga k. The <$fTrik ini dijelaskan di sini .

Haskell , 51 byte

f 1=pure<$>[0..]
f n=[a-k:k:t|a:t<-f$n-1,k<-[0..a]]

Cobalah online!

Secara rekursif merentangkan semua n-1-tupel menjadi semua n-tupel dengan membagi angka pertama adari masing-masing n-1-tupel menjadi dua angka a-k,kyang menjumlahkannya, dengan segala cara yang mungkin.

Tidak
sumber
4

Pyth - 9 byte

Terima kasih kepada @FryAmTheEggman untuk golfnya

Putar semua x, dan ambil [1..x] ^ n. Ini membuat duplikat, jadi hanya menyimpan yang baru ke x itu, alias mengandung x di dalamnya. Formatnya sedikit aneh, tetapi bisa dibuat standar dengan satu byte lagi,.V1j}#b^Sb

.V1}#b^Sb

Cobalah online .

Maltysen
sumber
1
f}bT-> }#bJuga, jumlah byte Anda tampaknya salah saat ini?
FryAmTheEggman
@FryAmTheEggman tunggu, mengapa ini tidak benar? Jika Anda berbicara tentang tautan TIO, itu termasuk memformat dengan j(b). Juga, terima kasih untuk golfnya.
Maltysen
Ah, itu yang membuatku bingung, maaf!
FryAmTheEggman
3

Brachylog (v2), 9 byte

~l.ℕᵐ+≜∧≜

Cobalah online!

Ini adalah generator tanpa batas yang menghasilkan semua tupel yang mungkin. TIO link memiliki header yang menggunakan generator untuk menghasilkan 1000 elemen dan mencetaknya (tetapi generator bisa berlanjut tanpa batas waktu jika saya meminta itu sebagai gantinya; bilangan bulat Brachylog tidak terikat).

Rasanya harus ada cara terser, tetapi ada banyak kendala dan ini adalah yang tersest yang bisa saya masukkan ke dalam satu program.

Penjelasan

~l.ℕᵐ+≜∧≜
  .        Generate
        ≜  all explicit
~l         lists whose length is {the input}
    ᵐ      for which every element
   ℕ       is non-negative
     +     and whose sum
      ≜    is used to order the lists (closest to zero first)
       ∧   [remove unwanted implicit constraint]

Secara kebetulan, saya merasa sangat menarik betapa berbedanya penjelasan saya tentang keduanya , meskipun mereka melakukan hal yang persis sama dari sudut pandang Brachylog. Yang pertama adalah predikat nondeterministik pertama dalam program, sehingga menetapkan urutan hasil; dalam hal ini, ia menghitung semua nilai eksplisit yang mungkin untuk jumlah daftar dalam urutan 0, 1, 2, 3 ..., dan digunakan untuk memastikan bahwa daftar tersebut adalah output dalam urutan jumlah mereka (ini memastikan bahwa setiap kemungkinan daftar muncul setelah jumlah output yang terbatas). Yang kedua digunakan untuk menghitung semua kemungkinan eksplisit untuk daftar (daripada menghasilkan formula yang menentukan bagaimana elemen-elemen daftar saling berhubungan).

ais523
sumber
↰₁ẉ⊥juga merupakan tajuk yang bagus, untuk mencetak tanpa batas.
String Tidak Terkait
Meskipun saya merasa seperti ini mungkin bukan jawaban yang sebenarnya, karena setiap doa independen dari predikat ini hanya akan menghasilkan angka nol , dengan bagian "hasilkan semua" dilakukan oleh atau di header.
String Tidak Terkait
1
@UnrelatedString Kode Anda tidak menggunakan predikat sebagai generator. Kami memiliki aturan eksplisit yang memungkinkan daftar keluaran menggunakan generator . Apa yang Anda lakukan di tautan TIO Anda adalah memanggil predikat dalam satu lingkaran untuk mendapatkan 1.000 generator yang berbeda, kemudian mengambil output pertama dari masing-masing; itu adalah operasi yang sangat tidak wajar untuk dilakukan pada generator, dan itu tidak akan membiarkan Anda melihat elemen lain yang dapat mereka hasilkan.
ais523
Ah, jadi saya baru saja salah menafsirkan semantik dari apa predikat Brachylog selama ini - ide saya tentang "generator" macet pada Python. Sekarang itu langsung di kepala saya, saya akan mencukur tiga byte dari beberapa jawaban lama saya.
String yang tidak terkait
2

Perl 6 , 37 byte

{$++.polymod(1+$++ xx $_-1).say xx *}

Cobalah online!

Pada dasarnya berjalan polymoddengan sebanyak mungkin entri yang diperlukan, di mana modulo selalu lebih besar dari input, yaitu 0.polymod (1,1,1), 1.polymod (2,2,2) dll. Dengan begitu digit selalu berada dalam jangkauan. Perl6 tidak akan membiarkan saya modulo infinity ...

Phil H
sumber
5
Ini tidak mencantumkan setiap tuple tepat sekali (misalnya, (0, 1, 0, 0)tidak terdaftar).
bb94
2

C # (Visual C # Interactive Compiler) , 148 byte

n=>{var a=new int[n];int j=0;void g(int k){if(k<n)for(int i=0;i++<j;g(k+1))a[k]=i;else if(a.Sum()==j)WriteLine(string.Join(' ',a));}for(;;j++)g(0);}

Cobalah online!

-3 byte terima kasih kepada @ASCIIOnly!

// n: size of tuples to generate
n=>{
  // a: current tuple workspace
  var a=new int[n];
  // j: target sum value
  int j=0;
  // recursive function that works on slot k
  void g(int k){

    // tuple is not fully generated,
    if(k<n)

      // try all values from (0,j]
      for(int i=0;i++<j;
        // recursive call - generates all
        // values from (0,j] in the next slot
        g(k+1)
      )
        // update the kth slot
        a[k]=i;

    // tuple is fully generated, however
    // we should only display if the sum
    // is equal to the target sum. tuples
    // are generated many times, this
    // let's us enforce that they are only
    // displayed once.
    else if(a.Sum()==j)
      WriteLine(string.Join(' ',a));
  }
  // increment the high value forever
  // while continually starting the
  // recursive function at slot 0
  for(;;j++)
    g(0);
}
dana
sumber
bagaimana Anda melakukannya
Stackstuck
lurus-up porting ini ke .NET Core mungkin masih akan menyelamatkan saya banyak byte.
Stackstuck
Trik terbesar di sini adalah rekursi. Sebagian besar teknik yang saya lihat menghasilkan "permutasi" menggunakannya. Saya berencana menambahkan penjelasan.
dana
Writedengan misalnya '<literal tab>'atau |dengan panjang yang sama, dan mengambil garis yang jauh lebih sedikit: P
ASCII-only
1
aw , 151
ASCII
1

Jelly , 10 (9?) Byte

9 jika kita dapat menggunakan pemisahan yang tidak konsisten (yang saya tanyakan) - penghapusan .

‘ɼṗ³ċƇ®Ṅ€ß

Cobalah online!

Bagaimana?

‘ɼṗ³ċƇ®Ṅ€ß - Main Link: some argument, x (initially equal to n, but unused)
 ɼ         - recall v from the register (initially 0), then set register to, and yield, f(v)
‘          -   f = increment
           - (i.e. v=v+1)
   ³       - program's third command line argument (1st program argument) = n
  ṗ        - (implicit range of [1..v]) Cartesian power (n)
           - (i.e. all tuples of length n with items in [1..v])
     Ƈ     - filter keep those for which:
    ċ      -   count
      ®    -   recall from register
           - (i.e. keep only those containing v)
       Ṅ€  - print €ach
         ß - call this Link with the same arity
           - (i.e. call Main(theFilteredList), again the argument is not actually used)
Jonathan Allan
sumber
1
Berdasarkan " selama pemisahan antara tupel dan angka di dalam masing-masing tuple jelas dan konsisten. (Misalnya, satu tuple per baris.) " Saya berasumsi itu tidak diizinkan dan diperlukan, tapi mari kita tunggu apa yang harus OP mengatakan.
Kevin Cruijssen
1

05AB1E , 15 11 byte

[¼¾LIãvy¾å—

-4 byte dengan menciptakan pelabuhan @Maltysen 's Pyth jawabannya .

Cobalah online.

Penjelasan:

[             # Start an infinite loop:
 ¼            #  Increase the counter_variable by 1 (0 by default)
  ¾L          #  Create a list in the range [1, counter_variable]
    Iã        #  Take the cartesian power of this list with the input
      v       #  Loop over each list `y` in this list of lists:
       y¾å    #   If list `y` contains the counter_variable:
             #    Print list `y` with trailing newline
Kevin Cruijssen
sumber
2
Kapan program akan mencapai [1,2,1]? Ingat itu harus dalam waktu yang terbatas.
billpg
@ billpg Harus diperbaiki sekarang.
Kevin Cruijssen
1

MATL , 16 byte

`@:GZ^t!Xs@=Y)DT

Tuples dipesan dengan meningkatkan jumlah, dan dalam jumlah tertentu mereka dipesan secara leksikografis.

Cobalah online!

Luis Mendo
sumber
1

Python 2 , 126 112 106 101 100 83 byte

n=input()
i=1
while 1:
 b=map(len,bin(i)[3:].split('0'));i+=1
 if len(b)==n:print b

Cobalah online!

5 byte thx ke mypetlion ; 1 byte dari mata elang ArBo ; 17 byte dari xnor !

Bangun partisi yang diurutkan mmenjadi nnampan, untuk m = 0,1,2,3,...dengan memilih angka biner dengan n-1 0s dan m 1s.

Chas Brown
sumber
if i==p:i=0;p*=2dapat menjadi i%=p;p<<=i<1menghemat 5 byte.
mypetlion
Saya yakin ruang sesudahnya print btidak diperlukan: D
ArBo
Sepertinya i+phanya menghitung 1, 2, 3 ... dengan cara yang berbelit-belit dan hanya bisa menjadi variabel tunggal.
xnor
@ xnor: Doh! Begitu larut dalam konsep itu, tidak bisa melihat hutan untuk pepohonan.
Chas Brown
1

C # (.NET Core) , 608 570 567 byte

using C=System.Console;using L=System.Collections.Generic.List<int[]>;class A{static void Main(){L x=new L(),y=new L(),z=new L();int i=int.Parse(C.ReadLine()),j=0,k,l,m;x.Add(new int[i]);while(i>0){j++;for(m=0;m++<i;){foreach(var a in y)x.Add(a);y=new L();foreach(var a in x){for(k=0;k<i;){int[] t=new int[i];System.Array.Copy(a,t,i);t[k++]=j;var b=true;z.AddRange(x);z.AddRange(y);foreach(var c in z){for(l=0;l<i;l++)if(c[l]!=t[l])break;if(l==i)b=false;}if(b)y.Add(t);}}}}for(k=0;k<x.Count;k++){C.Write("[ ");for(l=0;l<i;l++)C.Write(x[k][l]+" ");C.WriteLine("]");}}}

Cobalah online!

Ya Tuhan apa yang telah saya lakukan (begitu banyak loop, itulah yang saya lakukan)

Itu harusnya bekerja!

Jika Anda memindahkan lingkaran cetak ke belakang satu braket, itu akan menampilkan daftar saat dibuat, setiap kali loop. (Saya sarankan menambahkan baris baru atau sesuatu untuk membedakan setiap loop jika Anda melakukannya.)

Jujur, banyak waktu saya dihabiskan untuk bertarung dengan bahasa ... tidak ada array yang cukup, berbagai macam perilaku == ...

Semoga versi ini lebih mudah dibaca.

using C=System.Console;
using L=System.Collections.Generic.List<int[]>;
class A{
    static void Main(){
        L x=new L(),y=new L(),z=new L();
        int i=int.Parse(C.ReadLine()),j=0,k,l,m;
        x.Add(new int[i]);
        while(i>0){
            j++;
            for(m=0;m++<i;){
                foreach(var a in y) x.Add(a);
                y=new L();
                foreach(var a in x){
                    for(k=0;k<i;){
                        int[] t=new int[i];
                        System.Array.Copy(a,t,i);
                        t[k++]=j;
                        var b=true;
                        z.AddRange(x);
                        z.AddRange(y);
                        foreach(var c in z){
                            for(l=0;l<i;l++) if(c[l]!=t[l])break;
                            if(l==i)b=false;
                        }
                        if(b)y.Add(t);
                    }
                }
            }
        }
        for(k=0;k<x.Count;k++){
            C.Write("[ ");
            for(l=0;l<i;l++)C.Write(x[k][l]+" ");
            C.WriteLine("]");
        }
    }
}
Stackstuck
sumber
Saya baru sadar saya bisa menempelkan lingkaran cetak di pernyataan if sehingga ia mencetak saat berjalan. facepalm satu saat.
Stackstuck
tunggu dulu tidak bisa melakukan itu
Stackstuck
... oh sayang, saya tidak yakin kode ini berfungsi lagi.
Stackstuck
aaaa dan tidak.
Stackstuck
1
Semoga berhasil dengan ini :) Saya mulai mengkode solusi dalam C # dan menyadari bahwa itu sedikit lebih rumit daripada yang saya harapkan. Mengapa tidak menggunakan penerjemah "Visual C # Interactive"? Itu akan menghemat banyak dengan hanya tidak harus memasukkan definisi kelas. Anyways, +1 from me :)
dana
1

Perl 6 , 50 byte

{grep $_,{S/.//.split(0)>>.chars}($++.base(2))xx*}

Cobalah online!

Blok kode anonim yang mengembalikan daftar malas tak terbatas. Ini menggunakan strategi yang sama dengan jawaban Chas Brown .

Penjelasan:

{grep $_,{S/.//.split(0)>>.chars}($++.base(2))xx*}
{                                                } # Anonymous code block
                                              xx*  # Repeat indefinitely
                                 ($++        )     # From the current index
                                     .base(2)      # Get the binary form
         {S/.//                 }   # Remove the first digit
               .split(0)            # And split by zeroes
                        >>.chars    # And get the length of each section
 grep   ,   # From this infinite list, filter:
      $_      # The groups with length the same as the input
Jo King
sumber
0

VDM-SL , 51 byte

g(i)==if i=0then{}else{[x]^y|x:nat,y in set g(i-1)}

Pemahaman mengatur rekursif dengan rangkaian urutan ..

Bukan pada TIO, Anda bisa menjalankan program (jika Anda mengaktifkan batas untuk tipe nat atau tidak akan berhenti):

functions 
g:nat->set of ?
g(i)==if i=0then{}else{[x]^y|x:nat,y in set g(i-1)}

Termasuk 0s opsional sebagai jawaban jika tidak maka akan menjadi 52 byte yang mengikat nat1

Data Kedaluwarsa
sumber
0

Bahasa Wolfram (Mathematica) , 131 byte

While[0<1,If[a~FreeQ~#,Print@#]&/@(b=Table[Select[Range@t~Tuples~{s},Tr@#==k&],{k,t,t(s=#)}]~Flatten~1);a={a}~Join~b;t++]&
t=1
a={}

Cobalah online!

J42161217
sumber
0

perl -M5.010 122 bytes

$n=shift;
$s.="for\$x$_(1..\$m){"for 1..$n;
$t.="\$x$_ "for 1..$n;
$u.='}'x$n;
eval"{\$m++;$s\$_=qq' $t';/ \$m /&&say$u;redo}"

Menambahkan beberapa baris baru demi keterbacaan (tidak dihitung dalam jumlah byte)


sumber
0

Python 2 , 120 byte

from random import*
m=n=input()
a=()
while 1:
 m+=len(a)==m**n;t=[randint(1,m)for _ in[1]*n]
 if(t in a)<1:a+=t,;print t

Cobalah online!

Sedikit lebih lama daripada kebanyakan jawaban lain, tetapi saya menyukai ide di baliknya.

ArBo
sumber
0

Stax , 6 byte

£ƒ$↔┬ï

Jalankan dan debug itu

Untuk input n, prosedurnya kira-kira

for i in [0..infinity]:
    get all the distinct n length arrays of positive integers that sum to i
    for each
        join with spaces
        implicitly output
rekursif
sumber
0

JavaScript (V8) , 98 byte

n=>{for(a=[],b=[j=1];;b.push(++j))(g=k=>k<n?b.map(i=>(a[k]=i)|g(k+1)):a.includes(j)&&print(a))(0)}

Cobalah online!

Hore! Akhirnya mendapatkannya di bawah 100 :) Pada dasarnya port jawaban C # saya .

// n: length of tuples to generate
n=>{
  // a: workspace for current tuple
  // b: range of numbers that grows
  //     - iteration 1: [1]
  //     - iteration 2: [1,2]
  //     - iteration 3: [1,2,3]
  // j: largest number in b
  for(a=[],b=[j=1];;b.push(++j))
    // g: recursive function to build tuples
    // k: index of slot for current recursive call
    (g=k=>
       // current slot less than the tuple size? 
       k<n?
         // tuple generation not complete
         // try all values in current slot and
         // recurse to the next slot
         b.map(i=>(a[k]=i)|g(k+1)):
         // tuple generation complete
         // print tuple if it contains the
         // current high value
         a.includes(j)&&print(a)
    // start recursive function at slot 0
    )(0)
}
dana
sumber