Liste todas as combinações com substituição (ou combinações com repetição) do tamanho k de um conjunto de n elementos.

Uma combinação com substituição é um conjunto múltiplo não ordenado de que todos os elementos também estão no conjunto de n elementos. Observe que:

• Não é ordenado. Portanto, um conjunto impresso anteriormente com um pedido diferente não deve ser impresso novamente.
• É um multiset. O mesmo elemento pode (mas não é necessário) aparecer mais de uma vez. Essa é a única diferença entre uma combinação com substituição e uma combinação normal.
• O conjunto deve ter exatamente k elementos.

Como alternativa, também é um subconjunto tamanho- k do multiset que contém cada um dos n elementos k vezes.

A entrada deve ser n e k , onde os elementos são os primeiros n números inteiros positivos ou não negativos, ou os n elementos e k , onde você pode assumir que os n elementos são todos diferentes um do outro.

A saída deve ser uma lista de todas as combinações com substituição com tamanho k do conjunto fornecido. Você pode imprimi-los e os elementos em cada um deles em qualquer ordem.

Você não pode usar os componentes internos gerando combinações com substituição. Mas você pode usar builtins para gerar combinações normais, permutações, tuplas, etc.

Este é o código-golfe, o código mais curto vence.

Exemplo

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

Gelatina, 4 bytes

Agradecimentos ao Sp3000 por salvar 2 bytes.

ṗṢ€Q

A entrada é ne kcomo argumentos da linha de comando nessa ordem. Usa elementos 1para n.

Experimente online!

Explicação

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

CJam (8 bytes)

{m*:$_&}

Demonstração online

Dissecação

{    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

Agradecimentos a A Simmons por salvar 2 bytes.

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

Uma função sem nome, recebendo ne kcomo argumentos inteiros nessa ordem e retornando uma lista de listas. Os elementos serão 1para n. Funciona da mesma forma que a resposta CJam de Peter.

MATL , 11 bytes

(Existe uma solução de 9 bytes baseada no poder cartesiano, mas Peter Taylor já fez isso . Vamos tentar algo diferente).

Combinações com substituição podem ser reduzidas a combinações sem substituição, como a seguir. Queremos n Cr k, por exemplo n=3, com 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

e subtraia 0 1 ... k-1de cada linha:

+q:2GXn2G:-

Explicação:

+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

O código funciona na versão 13.1.0 do idioma / compilador, anterior ao desafio.

Você pode experimentá-lo online! Observe que o compilador online foi atualizado para a versão 14.0.0, portanto, Xnprecisa ser alterado para 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]]:[[]]

Eu uso keys()pela primeira vez.

Ruby, 56 55 bytes

Duas soluções, surpreendentemente ambas do mesmo comprimento:

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

Ei, você se dizer que poderíamos usar builtins permutação ...

Isso simplesmente gera todas as permutações repetidas (a segunda gera produtos cartesianos repetidos) e remove aquelas que não estão na ordem de classificação.

Agradecemos a Martin por salvar um byte com 0...n-> 1..n!

Pitão, 7 bytes

{SM^UQE

Usa o mesmo algoritmo que a resposta 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:]

Um método recursivo. Para criar um conjunto múltiplo de kelementos, 1para n, escolhemos:

• Inclua outra instância de n, e resta criar um multiset de k-1elementos de 1paran
• Não inclua outra instância de n, e resta criar um conjunto múltiplo de kelementos de 1paran-1

Terminamos quando um deles chega kou , e se chegou , fornecemos um caso base da lista vazia. Caso contrário, temos o número errado de elementos e, portanto, forneça a lista vazia.n0k0

Python 3, 81 80

Solução 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)]

A função t(n, k, b)retorna a lista de todos kos subconjuntos de todos os elementos do intervalo de ba n. Esta lista está vazia se k <= 0. Caso contrário, decompomos o problema com base no menor elemento do multi-subconjunto, que denotamos por i.

Para cada um ino intervalo de ba n, geramos todos os k-multi-subconjuntos com o menor elemento iiniciando com [i]e depois anexando cada (k-1)-multi-subconjunto do intervalo de ia n, que obtemos chamando recursivamente t(n, k-1, i).

Dyalog APL , 22 bytes

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

Requer ⎕IO←0, que é o padrão em muitos sistemas APL. Leva k como argumento à esquerda, n como argumento à direita.

⍳⍺*⍵0 1 2 ... kⁿ
⍺⊥⍣¯1converte na base k
⍉transposição
↓transforma a matriz em lista de listas,
{⍵[⍋⍵]}¨classifique cada ...
∪a única

J, 18 bytes

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

Abordagem semelhante usada na solução da @ Adám .

Outra abordagem usando o produto cartesiano {por 24 bytes. Assume ko LHS e no 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│
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

Explicação

[:~.#~<@/:~@#: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))))))

Observe a ordem dos parâmetros alterados: 1º ke 2º n. Isso economizou 1 byte em (f(dec k)n).

Mathematica, 36 bytes

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

Por favor, diga-me que há um bônus de 1/6 por não usar [...] ... Ou talvez pelos muitos usos de ##?