Liste todas las combinaciones con reemplazo (o combinaciones con repetición) de tamaño k de un conjunto de n elementos.

Una combinación con reemplazo es un conjunto múltiple desordenado en el que cada elemento también está en el conjunto de n elementos. Tenga en cuenta que:

• No está ordenado Por lo tanto, un conjunto previamente impreso con un orden diferente no debe imprimirse nuevamente.
• Es un conjunto múltiple. El mismo elemento puede (pero no es obligatorio) aparecer más de una vez. Esta es la única diferencia entre una combinación con reemplazo y una combinación normal.
• El conjunto debe tener exactamente k elementos.

Alternativamente, también es un subconjunto de tamaño k del conjunto múltiple que contiene cada uno de los n elementos k veces.

La entrada debe ser o bien n y k , donde los elementos son los primeros n positivos o no negativos números enteros, o los n elementos y k , en las que pueden asumir los n elementos son todos diferentes unos de otros.

El resultado debe ser una lista de todas las combinaciones con reemplazo con el tamaño k del conjunto dado. Puede imprimirlos y los elementos en cada uno de ellos en cualquier orden.

No puede usar combinaciones integradas que generen reemplazos. Pero puede usar builtins para generar combinaciones normales, permutaciones, tuplas, etc.

Este es el código de golf, el código más corto gana.

Ejemplo

Input: 4 2
Output: [0 0] [0 1] [0 2] [0 3] [1 1] [1 2] [1 3] [2 2] [2 3] [3 3]

Jalea, 4 bytes

Gracias a Sp3000 por guardar 2 bytes.

ṗṢ€Q

La entrada es ny kcomo argumentos de línea de comandos en ese orden. Utiliza elementos 1para n.

Pruébalo en línea!

Explicación

ṗ     # Get k-th Cartesion power of n.
 Ṣ€   # Sort each tuple.
   Q  # Remove duplicates.

CJam (8 bytes)

{m*:$_&}

Demostración en línea

Disección

{    e# Declare block (anonymous function); parameters are n k
  m* e# Cartesian product, which implicitly lifts n to [0 1 ... n-1]
  :$ e# Sort each element of the Cartesian product, to give them canonical forms
  _& e# Deduplicate
}

Mathematica, 31 29 bytes

Gracias a A Simmons por guardar 2 bytes.

{}⋃Sort/@Range@#~Tuples~#2&

Una función sin nombre que toma ny kcomo argumentos enteros en ese orden y devuelve una lista de listas. Los elementos serán 1para n. Funciona igual que la respuesta de Peter CJam.

MATL , 11 bytes

(Hay una solución de 9 bytes basada en el poder cartesiano, pero Peter Taylor ya lo hizo . Probemos algo diferente).

Las combinaciones con reemplazo se pueden reducir a combinaciones sin reemplazo de la siguiente manera. Queremos n Cr k, por ejemplo n=3, con k=2:

0 0
0 1
0 2
1 1
1 2
2 2

Podemos calcular n+k-1 C k:

0 1
0 2
0 3
1 2
1 3
2 3

y luego restar 0 1 ... k-1de cada fila:

+q:2GXn2G:-

Explicación:

+q     % take two inputs n, k and compute n+k-1
:      % range [1,2...,n+k-1]
2G     % push second input, k
Xn     % combinations without replacement
2G:    % range [1,2,...,k]
-      % subtract with broadcast. Display

El código funciona en la versión 13.1.0 del lenguaje / compilador, que es anterior al desafío.

¡Puedes probarlo en línea! Tenga en cuenta que el compilador en línea se ha actualizado a la versión 14.0.0, por lo Xnque debe cambiarse a XN.

JavaScript (Firefox 30-57), 71 bytes

f=(n,k)=>k?[for(m of Array(n).keys())for(a of f(m+1,k-1))[...a,m]]:[[]]

Puedo usar keys()por una vez.

Ruby, 56 55 bytes

Dos soluciones, sorprendentemente ambas de la misma longitud:

->n,k{[*1..n].repeated_permutation(k).map(&:sort).uniq}
->n,k{(a=[*1..n]).product(*[a]*(k-1)).map(&:sort).uniq}

Oye, ¿ qué dice que podríamos utilizar órdenes internas de permutación ...

Esto simplemente genera todas las permutaciones repetidas (la segunda genera productos cartesianos repetidos) y elimina las que no están ordenadas.

¡Gracias a Martin por guardar un byte con 0...n-> 1..n!

Pyth, 7 bytes

{SM^UQE

Utiliza el mismo algoritmo que la respuesta de Peter.

    UQ   range(input())
      E  input()
   ^     repeated Cartesian product of ^^, ^ times
 SM      map(sort)
{        uniq

Python, 63 bytes

f=lambda n,k:n*k and[l+[n]for l in f(n,k-1)]+f(n-1,k)or[[]][k:]

Un método recursivo. Para hacer un conjunto múltiple de kelementos, 1a n, elegimos:

• Incluya otra instancia de n, y queda por hacer un conjunto múltiple de k-1elementos desde 1hastan
• No incluya otra instancia de n, y queda por hacer un conjunto múltiple de kelementos desde 1hastan-1

Terminamos cuando ko nalcanza 0, y si kllegó 0, damos un caso base de la lista vacía. Si no es así, tenemos el número incorrecto de elementos, por lo que damos la lista vacía.

Pitón 3, 81 80

Solución recursiva:

t=lambda n,k,b=0:[[]]if k<=0 else [[i]+l for i in range(b,n)for l in t(n,k-1,i)]

La función t(n, k, b)devuelve la lista de todos los ksubconjuntos múltiples de elementos del rango de ba n. Esta lista está vacía si k <= 0. De lo contrario, desglosamos el problema en función del elemento más pequeño del subconjunto múltiple, que denotamos por i.

Para cada uno ien el rango de ba n, generamos todos los ksubconjuntos múltiples con el elemento más pequeño ial comenzar [i]y luego (k-1)agregar cada subconjunto múltiple del rango de ia n, que obtenemos llamando de forma recursiva t(n, k-1, i).

Dyalog APL , 22 bytes

{∪{⍵[⍋⍵]}¨↓⍉⍺⊥⍣¯1⍳⍺*⍵}

Requiere ⎕IO←0, que es el predeterminado en muchos sistemas APL. Toma k como argumento izquierdo, n como argumento derecho.

⍳⍺*⍵0 1 2 ... kⁿ
⍺⊥⍣¯1convertir a base k
⍉transponer
↓hacer matriz en una lista de listas
{⍵[⍋⍵]}¨ordenar cada ...
∪la única

J, 18 bytes

[:~.#~<@/:~@#:i.@^

Enfoque similar utilizado en la solución de @ Adám .

Otro enfoque utilizando el producto cartesiano {para 24 bytes. Toma kel LHS y nel RHS.

~.@:(/:~&.>)@,@{@(#<@i.)

Uso

   f =: [:~.#~<@/:~@#:i.@^
   4 f 2
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│0 0│0 1│0 2│0 3│1 1│1 2│1 3│2 2│2 3│3 3│
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

Explicación

[:~.#~<@/:~@#:i.@^ Input: n on LHS and k on RHS
                 ^ Compute n^k
              i.@  Create a range [0, 1, ... n^k-1]
    #~             Create k copies on n
            #:     On each value in the range above, convert each digit to base-n
                   and take the last k digits of it
        /:~@       For each array of digits, sort it in ascending order
      <@           Box each array of digits
[:~.               Take the distinct values in the array of boxes and return it

Clojure, 94 bytes

(defn f[k n](if(= 1 k)(for[i(range n)][i])(sort(set(for[i(f(dec k)n)j(range n)](conj i j))))))

Tenga en cuenta el orden de los parámetros modificados: 1st is ky 2nd is n. Esto ahorró 1 byte en (f(dec k)n).

Mathematica, 36 bytes

{##}&~Array~Table@##~Flatten~(#2-1)&

Por favor, dime que hay una bonificación de 1/6 por no usar [] s ... ¿O tal vez por los muchos usos de ##?