35
\$\begingroup\$

Write a program, given an input n, will generate all possible n-tuples using natural numbers.

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)... 
  • The output may be in any order that does not break any other rules.
  • The program must be written to run forever and list all applicable tuples exactly once, in theory.
    • In reality, your program will reach your integer type's limit and crash. This is acceptable as long the program would run infinitely long if only your integer type was unlimited.
    • Each valid tuple must be listed within finite time, if only the program were allowed to run that long.
  • The output may, at your option, include zeroes in addition to the natural numbers.
  • You may choose your program's output format for your convenience, as long as the separation between tuples and numbers inside each tuple is clear and consistent. (For example, one tuple per line.)
  • The input (n) is an integer from one to six. Required behavior is undefined for inputs outside of this range.
  • Code-golf rules apply, shortest program wins.

Thanks to "Artemis Fowl" for feedback during the sandbox phase.

\$\endgroup\$
  • \$\begingroup\$ I assume it is valid if when the program crashes it produces some extraneous output in addition to the tuples printed so far, right? \$\endgroup\$ – Luis Mendo Apr 15 at 16:32
  • 1
    \$\begingroup\$ Must we output as we go or would a function which yields an infinite list at the end of time sufficient? \$\endgroup\$ – Jonathan Allan Apr 15 at 17:15
  • 6
    \$\begingroup\$ "You may choose your program's output format for your convenience, as long as the separation between tuples and numbers inside each tuple is clear and consistent" - may we output differing (albeit consistently differing) separation (e.g. like this)? \$\endgroup\$ – Jonathan Allan Apr 15 at 18:04
  • \$\begingroup\$ @JonathanAllan I would have to include the output of that object's infinite contents as part of the program. \$\endgroup\$ – billpg Apr 15 at 19:18
  • 1
    \$\begingroup\$ Related (integers instead of natural numbers) \$\endgroup\$ – Esolanging Fruit Apr 16 at 5:16

20 Answers 20

24
\$\begingroup\$

Husk, 2 bytes

πN

Try it online!

Explanation

N is the infinite list of natural numbers [1,2,3,4,... π is Cartesian power. Result is an infinite list of lists. Each list of the desired length occurs exactly once because π is cool like that. Input and output are implicit.

\$\endgroup\$
  • 1
    \$\begingroup\$ Wow, and this doesn't do [1,1,n] either. Is there a pattern to the order it outputs? \$\endgroup\$ – billpg Apr 15 at 20:04
  • 1
    \$\begingroup\$ @billpg It builds the tuples recursively: n- tuples are obtained by taking the Cartesian product of the original list and the list of n-1-tuples, in ascending order of sum of indices. \$\endgroup\$ – Zgarb Apr 16 at 4:30
  • \$\begingroup\$ "ascending order of sum of indices" -- Can you clarify this? I'm having trouble seeing why, eg, 2,2,2 comes after 4,1,2 and 5,1,1. \$\endgroup\$ – Jonah Apr 16 at 12:52
  • 2
    \$\begingroup\$ @Jonah The recursion works like this. You start with 1-tuples over N. For 2-tuples you take Cartesian product with N ordered by sum of indices. In both lists, each number n is at index n so for length 2 the result happens to be ordered by sum. To get 3-tuples you take Cartesian product of N and the list of 2-tuples, ordered by sum of the elements' indices in these lists. It doesn't look at the tuple's sum, it looks at its position in the list of tuples. \$\endgroup\$ – Zgarb Apr 16 at 14:29
  • 2
    \$\begingroup\$ "Figure out the different dimensions of infinity in this task and find a pattern that reduces it to countable infinity, then write a program that iterates over this pattern." - "Hey, I have a builtin for that!" \$\endgroup\$ – Fabian Röling Apr 17 at 11:00
10
\$\begingroup\$

Haskell, 62 bytes

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

Try it online!

n!s generates all the n-tuples that sum to s.

Then the answer is ([1..]>>=).(!), i.e. \n -> [t | s<-[1..], t<-n!s].

This is a function mapping an integer n to an infinite lazy list of tuples (lists of integers).

\$\endgroup\$
5
\$\begingroup\$

Haskell, 50 bytes

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

Try it online!

Lists n-tuples sorted by sum. mapM does the heavy lifting to generate all n-tuples of numbers from 0 to k. The <$f trick is explained here.

Haskell, 51 bytes

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

Try it online!

Recursively stretches all n-1-tuples into all n-tuples by splitting the first number a of each n-1-tuple into two numbers a-k,k that sum to it, in every possible way.

\$\endgroup\$
4
\$\begingroup\$

Pyth - 9 bytes

Thanks to @FryAmTheEggman for the golf

Loops through all x, and takes [1..x]^n. This makes duplicates, so only keeps ones that are new to that x, aka contain x in them. The formatting is a little weird, but it can be made standard with one more byte, .V1j}#b^Sb

.V1}#b^Sb

Try it online.

\$\endgroup\$
  • 1
    \$\begingroup\$ f}bT -> }#b Also, your byte count seems to be incorrect at the moment? \$\endgroup\$ – FryAmTheEggman Apr 16 at 4:33
  • \$\begingroup\$ @FryAmTheEggman wait, why is it incorrect? If you're talking about the TIO link, that includes formatting with j(b). Also, thanks for the golf. \$\endgroup\$ – Maltysen Apr 17 at 19:11
  • \$\begingroup\$ Ah, that's what confused me, sorry! \$\endgroup\$ – FryAmTheEggman Apr 17 at 20:48
3
\$\begingroup\$

Brachylog (v2), 9 bytes

~l.ℕᵐ+≜∧≜

Try it online!

This is an infinite generator that generates all possible tuples. The TIO link has a header that uses the generator to generate 1000 elements and prints them (but the generator could continue indefinitely if I asked for that instead; Brachylog's integers are unbounded).

It feels like there should be a terser way, but there are a lot of constraints and this is the tersest I can fit them into a single program.

Explanation

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

Incidentally, it strikes me as interesting just how different my explanations of the two are, despite them doing the exact same thing from Brachylog's point of view. The first is the first nondeterministic predicate in the program, so it sets the order of results; in this case, it calculates all possible explicit values for the sum of the list in the order 0, 1, 2, 3…, and is being used to ensure that the lists are output in order of their sum (this ensures that each possible list appears after a finite amount of output). The second is used to calculate all the explicit possibilities for the list (rather than outputting a formula specifying how the elements of the list relate to each other).

\$\endgroup\$
  • \$\begingroup\$ ↰₁ẉ⊥ is also a good header, for printing infinitely. \$\endgroup\$ – Unrelated String Apr 15 at 20:32
  • \$\begingroup\$ Although I do feel like this may not actually be a full answer, since any single independent invocation of this predicate will just generate zeroes, with the "generate all" part being done by the or the in the header. \$\endgroup\$ – Unrelated String Apr 15 at 20:38
  • 1
    \$\begingroup\$ @UnrelatedString Your code doesn't use the predicate as a generator, though. We have explicit rules allowing list output using a generator. What you're doing in your TIO link is calling the predicate in a loop to get 1000 different generators, then taking the first output from each of them; that's a really unnatural operation to do on generators, and it won't let you see the other elements that they can generate. \$\endgroup\$ – ais523 Apr 15 at 23:40
  • \$\begingroup\$ Ah, so I've just been misinterpreting the semantics of what a Brachylog predicate is this whole time--my idea of "generator" is stuck on Python. Now that that's straight in my head I guess I'll go shave three bytes off of some of my old answers. \$\endgroup\$ – Unrelated String Apr 16 at 1:41
2
\$\begingroup\$

Perl 6, 37 bytes

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

Try it online!

Essentially runs polymod with as many entries as needed, where the modulo is always greater than the input, i.e. 0.polymod( 1,1,1 ), 1.polymod( 2,2,2 ) etc. That way the digit is always within the range. Perl6 won't let me modulo infinity...

\$\endgroup\$
  • 5
    \$\begingroup\$ This doesn't list every tuple exactly once (for instance, (0, 1, 0, 0) is not listed). \$\endgroup\$ – bb94 Apr 15 at 20:03
2
\$\begingroup\$

Wolfram Language (Mathematica), 62 bytes

Do[Print/@Permutations@#&/@n~IntegerPartitions~{#},{n,#,∞}]&

Try it online!


-3 bytes with inconsistent separation (delete @#&)

Try it online!

\$\endgroup\$
2
\$\begingroup\$

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

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

Try it online!

-3 bytes thanks to @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);
}
\$\endgroup\$
  • \$\begingroup\$ how even did you do this \$\endgroup\$ – Stackstuck Apr 18 at 3:11
  • \$\begingroup\$ straight-up porting this to .NET Core would probably still save me a lot of bytes. \$\endgroup\$ – Stackstuck Apr 18 at 3:14
  • \$\begingroup\$ The biggest trick here is recursion. Most of the techniques I've seen to generate "permutations" use it. I plan on adding an explanation. \$\endgroup\$ – dana Apr 18 at 3:23
  • \$\begingroup\$ Write with e.g. '<literal tab>' or | is the same length, and takes up a lot fewer lines :P \$\endgroup\$ – ASCII-only Apr 18 at 10:52
  • 1
    \$\begingroup\$ aw, 151 \$\endgroup\$ – ASCII-only Apr 18 at 11:01
1
\$\begingroup\$

Jelly, 10 (9?) bytes

9 if we may output using non-consistent separation (which I have enquired about) -- removal of the .

‘ɼṗ³ċƇ®Ṅ€ß

Try it online!

How?

‘ɼṗ³ċƇ®Ṅ€ß - 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)
\$\endgroup\$
  • 1
    \$\begingroup\$ Based on "as long as the separation between tuples and numbers inside each tuple is clear and consistent. (For example, one tuple per line.)" I assumed it wasn't allowed and the is required, but let's wait what OP has to say. \$\endgroup\$ – Kevin Cruijssen Apr 15 at 18:55
1
\$\begingroup\$

05AB1E, 15 11 bytes

[¼¾LIãvy¾å—

-4 bytes by creating a port of @Maltysen's Pyth answer.

Try it online.

Explanation:

[             # 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
\$\endgroup\$
  • 2
    \$\begingroup\$ When will the program get to [1,2,1]? Remember it has to be within finite time. \$\endgroup\$ – billpg Apr 15 at 13:39
  • \$\begingroup\$ @billpg Should be fixed now. \$\endgroup\$ – Kevin Cruijssen Apr 15 at 15:24
1
\$\begingroup\$

MATL, 16 bytes

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

Tuples are ordered by increasing sum, and within a given sum they are ordered lexicographically.

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Python 2, 126 112 106 101 100 83 bytes

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

Try it online!

5 bytes thx to mypetlion; 1 byte from the eagle eye of ArBo; 17 bytes from xnor!

Construct the ordered partitions of m into n bins, for m = 0,1,2,3,... by selecting for binary numbers with n-1 0s and m 1s.

\$\endgroup\$
  • \$\begingroup\$ if i==p:i=0;p*=2 can become i%=p;p<<=i<1 to save 5 bytes. \$\endgroup\$ – mypetlion Apr 15 at 22:21
  • \$\begingroup\$ I'm pretty sure the space after print b is not needed :D \$\endgroup\$ – ArBo Apr 16 at 9:01
  • \$\begingroup\$ It looks like the i+p is just counting up 1, 2, 3... in a convoluted way and so can just be a single variable. \$\endgroup\$ – xnor Apr 16 at 16:36
  • \$\begingroup\$ @xnor: D'oh! Got so wrapped up in the concept, couldn't see the forest for the trees. \$\endgroup\$ – Chas Brown Apr 16 at 19:22
1
\$\begingroup\$

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

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("]");}}}

Try it online!

my god what have I done (so many loops, that's what I've done)

It should work, though!

If you move the print loop back one bracket, it will show you the list as it's built, every time it loops. (I recommend adding a newline or something to distinguish each loop if you do.)

Honestly, a lot of my time was spent fighting with the language...no pretty-printing arrays, assorted behaviors of ==...

Hopefully this version is easier to read.

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("]");
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ I just realized I can stick the print loop in the if statement so it prints as it goes. facepalm one moment. \$\endgroup\$ – Stackstuck Apr 17 at 17:54
  • \$\begingroup\$ wait nope can't do that \$\endgroup\$ – Stackstuck Apr 17 at 17:58
  • \$\begingroup\$ ...oh dear, I'm not sure this code works anymore. \$\endgroup\$ – Stackstuck Apr 17 at 17:59
  • \$\begingroup\$ aaaaand it doesn't. \$\endgroup\$ – Stackstuck Apr 17 at 18:00
  • 1
    \$\begingroup\$ Good luck with this :) I started coding a solution in C# and realized it was quite a bit trickier than I was hoping. Why not use the "Visual C# Interactive" interpreter? That would save a bunch by simply not having to include the class definition. Anyways, +1 from me :) \$\endgroup\$ – dana Apr 17 at 21:44
1
\$\begingroup\$

Perl 6, 50 bytes

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

Try it online!

Anonymous code block that returns a lazy infinite list. This uses the same strategy as Chas Brown's answer.

Explanation:

{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
\$\endgroup\$
0
\$\begingroup\$

VDM-SL, 51 bytes

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

Recursive set comprehension with sequence concatenation..

Not on TIO, you could run in a program (if you turn on limits for nat type or it wont terminate):

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

Includes the optional 0s in answer otherwise it would be 52 bytes binding on nat1

\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 131 bytes

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={}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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}"

Added some newlines for readabilities sake (not counted in the byte count)

\$\endgroup\$
0
\$\begingroup\$

Python 2, 120 bytes

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

Try it online!

A bit longer than most other answers, but I liked the idea behind it.

\$\endgroup\$
0
\$\begingroup\$

Stax, 6 bytes

£ƒ$↔┬ï

Run and debug it

For input n the procedure is roughly

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
\$\endgroup\$
0
\$\begingroup\$

JavaScript (V8), 98 bytes

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

Try it online!

Hooray! Finally got it under 100 :) Basically a port of my C# answer.

// 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)
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.