¡Lista * todas * las tuplas!

35

Escribir un programa, dada una entrada n , generará todas las n-tuplas posibles usando números naturales.

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)... 
  • La salida puede estar en cualquier orden que no rompa ninguna otra regla.
  • El programa debe escribirse para ejecutarse para siempre y enumerar todas las tuplas aplicables exactamente una vez, en teoría.
    • En realidad, su programa alcanzará el límite y el bloqueo de su tipo entero. Esto es aceptable siempre y cuando el programa se ejecute infinitamente si su tipo entero fuera ilimitado.
    • Cada tupla válida se debe enumerar dentro de un tiempo finito, si solo se permitiera que el programa se ejecutara tanto tiempo.
  • La salida puede, a su elección, incluir ceros además de los números naturales.
  • Puede elegir el formato de salida de su programa para su conveniencia, siempre que la separación entre tuplas y números dentro de cada tupla sea clara y consistente. (Por ejemplo, una tupla por línea).
  • La entrada (n) es un número entero de uno a seis. El comportamiento requerido no está definido para entradas fuera de este rango.
  • Se aplican las reglas del código de golf, gana el programa más corto.

Gracias a "Artemis Fowl" por sus comentarios durante la fase de sandbox.

billpg
fuente
Supongo que es válido si cuando el programa se bloquea produce una salida extraña además de las tuplas impresas hasta ahora, ¿verdad?
Luis Mendo
1
¿Debemos generar a medida que avanzamos o sería suficiente una función que produzca una lista infinita al final del tiempo?
Jonathan Allan
66
"Puede elegir el formato de salida de su programa para su conveniencia, siempre y cuando la separación entre tuplas y números dentro de cada tupla sea clara y consistente". ¿Podemos generar una separación diferente (aunque constantemente diferente) (p. Ej. Así )?
Jonathan Allan
@ JonathanAllan Tendría que incluir la salida del contenido infinito de ese objeto como parte del programa.
billpg
1
Relacionado (enteros en lugar de números naturales)
Esolanging Fruit

Respuestas:

24

Casco , 2 bytes

πN

Pruébalo en línea!

Explicación

Nes la lista infinita de números naturales [1,2,3,4,... πEs el poder cartesiano. El resultado es una lista infinita de listas. Cada lista de la longitud deseada ocurre exactamente una vez porque πes genial así. La entrada y la salida son implícitas.

Zgarb
fuente
1
Wow, y esto tampoco funciona [1,1, n]. ¿Hay un patrón en el orden que genera?
billpg
1
@billpg Construye las tuplas de forma recursiva: n- las tuplas se obtienen tomando el producto cartesiano de la lista original y la lista de n-1-tuplas, en orden ascendente de suma de índices.
Zgarb
"orden ascendente de suma de índices" - ¿Puedes aclarar esto? Tengo problemas para ver por qué, por ejemplo, 2,2,2viene después 4,1,2y 5,1,1.
Jonás
2
@ Jonás La recursión funciona así. Empiezas con 1-tuplas encima N. Para 2-tuplas, toma un producto cartesiano Nordenado por suma de índices. En ambas listas, cada número nestá en el índice, npor lo que para la longitud 2 el resultado se ordena por suma. Para obtener 3 tuplas, tome el producto cartesiano Ny la lista de 2 tuplas, ordenadas por la suma de los índices de los elementos en estas listas. No mira la suma de las tuplas, mira su posición en la lista de tuplas.
Zgarb
2
"Descubra las diferentes dimensiones del infinito en esta tarea y encuentre un patrón que lo reduzca a infinito contable, luego escriba un programa que repita este patrón". - "¡Oye, tengo algo para eso!"
Fabian Röling
10

Haskell , 62 bytes

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

Pruébalo en línea!

n!sgenera todas las ntuplas que suman s.

Entonces la respuesta es ([1..]>>=).(!), es decir \n -> [t | s<-[1..], t<-n!s].

Esta es una función que asigna un entero na una infinita lista perezosa de tuplas (listas de enteros).

Lynn
fuente
5

Haskell , 50 bytes

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

Pruébalo en línea!

Listas n-tuplas ordenadas por suma. mapMrealiza el trabajo pesado para generar todas las ntuplas de números del 0 al k. El <$ftruco es explica aquí .

Haskell , 51 bytes

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

Pruébalo en línea!

n-1Extiende recursivamente todos los -tuples en todos n-tuples dividiendo el primer número ade cada n-1-tupla en dos números a-k,kque suman, de todas las formas posibles.

xnor
fuente
4

Pyth - 9 bytes

Gracias a @FryAmTheEggman por el golf

Recorre todo x, y toma [1..x] ^ n. Esto hace duplicados, por lo que solo mantiene los que son nuevos para esa x, es decir, contienen x en ellos. El formato es un poco extraño, pero puede hacerse estándar con un byte más,.V1j}#b^Sb

.V1}#b^Sb

Pruébalo en línea .

Maltysen
fuente
1
f}bT-> }#bAdemás, ¿tu conteo de bytes parece ser incorrecto en este momento?
FryAmTheEggman
@FryAmTheEggman espera, ¿por qué es incorrecto? Si está hablando del enlace TIO, eso incluye formatear con j(b). Además, gracias por el golf.
Maltysen
Ah, eso es lo que me confundió, lo siento!
FryAmTheEggman
3

Brachylog (v2), 9 bytes

~l.ℕᵐ+≜∧≜

Pruébalo en línea!

Este es un generador infinito que genera todas las tuplas posibles. El enlace TIO tiene un encabezado que usa el generador para generar 1000 elementos y los imprime (pero el generador podría continuar indefinidamente si lo pidiera en su lugar; los enteros de Brachylog son ilimitados).

Parece que debería haber una manera más terser, pero hay muchas restricciones y esta es la mejor prueba que puedo incluir en un solo programa.

Explicación

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

Por cierto, me parece interesante cuán diferentes son mis explicaciones de los dos , a pesar de que hacen exactamente lo mismo desde el punto de vista de Brachylog. El primero es el primer predicado no determinista en el programa, por lo que establece el orden de los resultados; en este caso, calcula todos los valores explícitos posibles para la suma de la lista en el orden 0, 1, 2, 3 ..., y se está utilizando para garantizar que las listas se emitan en orden de su suma (esto asegura que cada posible la lista aparece después de una cantidad finita de salida). El segundo se utiliza para calcular todas las posibilidades explícitas de la lista (en lugar de generar una fórmula que especifique cómo se relacionan entre sí los elementos de la lista).

ais523
fuente
↰₁ẉ⊥También es un buen encabezado, para imprimir infinitamente.
Cadena no relacionada
Aunque creo que esto puede no ser una respuesta completa, ya que cualquier invocación independiente de este predicado solo generará ceros , con la parte "generar todo" realizada por el o el encabezado.
Cadena no relacionada
1
@UnrelatedString Sin embargo, su código no usa el predicado como generador. Tenemos reglas explícitas que permiten la salida de la lista usando un generador . Lo que está haciendo en su enlace TIO es llamar al predicado en un bucle para obtener 1000 generadores diferentes, luego tomar la primera salida de cada uno de ellos; Esa es una operación realmente poco natural para hacer en los generadores, y no le permitirá ver los otros elementos que pueden generar.
ais523
Ah, así que he estado malinterpretando la semántica de lo que es un predicado de Brachylog todo este tiempo: mi idea de "generador" está atrapada en Python. Ahora que eso está en mi cabeza, supongo que voy a eliminar tres bytes de algunas de mis respuestas anteriores.
Cadena no relacionada
2

Perl 6 , 37 bytes

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

Pruébalo en línea!

Esencialmente se ejecuta polymodcon tantas entradas como sea necesario, donde el módulo siempre es mayor que la entrada, es decir, 0.polymod (1,1,1), 1.polymod (2,2,2) etc. De esa manera el dígito siempre está dentro de el rango. Perl6 no me deja modulo infinito ...

Phil H
fuente
55
Esto no enumera todas las tuplas exactamente una vez (por ejemplo, (0, 1, 0, 0)no aparece en la lista).
bb94
2

C # (compilador interactivo de Visual C #) , 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);}

Pruébalo en línea!

-3 bytes gracias a @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
fuente
¿Cómo hiciste esto?
Stackstuck
portar esto directamente a .NET Core probablemente aún me ahorraría muchos bytes.
Stackstuck
El mayor truco aquí es la recursividad. La mayoría de las técnicas que he visto para generar "permutaciones" lo usan. Planeo agregar una explicación.
dana
Writecon, por ejemplo, '<literal tab>'o |tiene la misma longitud y ocupa muchas menos líneas: P
Solo ASCII
1
aw , 151
Solo ASCII
1

Gelatina , 10 (9?) Bytes

9 si podemos generar una separación no consistente (sobre la que he preguntado) - eliminación de .

‘ɼṗ³ċƇ®Ṅ€ß

Pruébalo en línea!

¿Cómo?

‘ɼṗ³ċƇ®Ṅ€ß - 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
fuente
1
Basado en " siempre y cuando la separación entre tuplas y números dentro de cada tupla sea clara y consistente. (Por ejemplo, una tupla por línea) ". Supuse que no estaba permitido y es obligatorio, pero esperemos lo que OP tiene que hacer. decir.
Kevin Cruijssen
1

05AB1E , 15 11 bytes

[¼¾LIãvy¾å—

-4 bytes creando un puerto de @Maltysen Pyth respuesta 's .

Pruébalo en línea.

Explicación:

[             # 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
fuente
2
¿Cuándo llegará el programa a [1,2,1]? Recuerde que tiene que ser dentro de un tiempo finito.
billpg
@billpg Debería arreglarse ahora.
Kevin Cruijssen
1

MATL , 16 bytes

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

Las tuplas se ordenan por suma creciente, y dentro de una suma dada se ordenan lexicográficamente.

Pruébalo en línea!

Luis Mendo
fuente
1

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.

Chas Brown
fuente
if i==p:i=0;p*=2 can become i%=p;p<<=i<1 to save 5 bytes.
mypetlion
I'm pretty sure the space after print b is not needed :D
ArBo
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.
xnor
@xnor: D'oh! Estaba tan absorto en el concepto, no podía ver el bosque por los árboles.
Chas Brown
1

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

Pruébalo en línea!

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

¡Debería funcionar, sin embargo!

Si mueve el bucle de impresión hacia atrás un soporte, le mostrará la lista a medida que se construye, cada vez que se repite. (Recomiendo agregar una nueva línea o algo para distinguir cada ciclo si lo hace).

Honestamente, pasé gran parte de mi tiempo luchando con el lenguaje ... sin matrices bonitas, comportamientos variados de == ...

Esperemos que esta versión sea más fácil de leer.

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
fuente
Me acabo de dar cuenta de que puedo pegar el bucle de impresión en la instrucción if para que se imprima a medida que avanza. Facepalm un momento.
Stackstuck
wait nope can't do that
Stackstuck
...oh dear, I'm not sure this code works anymore.
Stackstuck
aaaaand it doesn't.
Stackstuck
1
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 :)
dana
1

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
Jo King
fuente
0

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

Expired Data
fuente
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}"

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


fuente
0

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.

ArBo
fuente
0

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
recursive
fuente
0

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