Generate combinations with replacement

Question

List all of the combinations with replacement (or combinations with repetition) of size k from a set of n elements.

A combination with replacement is an unordered multiset that every element in it are also in the set of n elements. Note that:

• It is unordered. So a previously printed set with a different order shouldn't be printed again.
• It is a multiset. The same element can (but isn't required to) appear more than once. This is the only difference between a combination with replacement and a normal combination.
• The set should have exactly k elements.

Alternatively, it is also a size-k subset of the multiset which contains each of the n elements k times.

The input should be either n and k, where the elements are the first n positive or non-negative integers, or the n elements and k, where you can assume the n elements are all different from each other.

The output should be a list of all the combinations with replacement with size k from the given set. You can print them and the elements in each of them in any order.

You may not use builtins generating combinations with replacement. But you can use builtins to generate normal combinations, permutations, tuples, etc.

This is code-golf, shortest code wins.

Example

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

Answer 1

Jelly, 4 bytes

Thanks to Sp3000 for saving 2 bytes.

ṗṢ€Q

Input is n and k as command-line arguments in that order. Uses elements 1 to n.

Try it online!

Explanation

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

Answer 2

CJam (8 bytes)

{m*:$_&}

Online demo

Dissection

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

Answer 3

Mathematica, 31 29 bytes

Thanks to A Simmons for saving 2 bytes.

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

An unnamed function taking n and k as integer arguments in that order and returning a list of lists. The elements will be 1 to n. Works the same as Peter's CJam answer.

Answer 4

MATL, 11 bytes

(There's a 9-byte solution based on Cartesian power, but Peter Taylor already did that. Let's try something different).

Combinations with replacement can be reduced to combinations without replacement as follows. We want n Cr k, for example with n=3, k=2:

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

We can compute n+k-1 C k:

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

and then subtract 0 1 ... k-1 from each row:

+q:2GXn2G:-

Explanation:

+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

The code works in release 13.1.0 of the language/compiler, which is earlier than the challenge.

You can try it online! Note that the online compiler has been updated to release 14.0.0, so Xn needs to be changed to XN.

Answer 5

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]]:[[]]

I get to use keys() for once.

Answer 6

Ruby, 56 55 bytes

Two solutions, surprisingly both the same length:

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

Hey, you did say we could use permutation builtins...

This simply generates all repeated permutations (the second one generates repeated Cartesian products) and removes ones that aren't in sorted order.

Thanks to Martin for saving a byte with 0...n -> 1..n!

Answer 7

Pyth, 7 bytes

{SM^UQE

Uses the same algorithm as Peter's answer.

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

Answer 8

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

A recursive method. To make a multiset of k elements, 1 to n, we choose to either:

• Include another instance of n, and it remains to make a multiset of k-1 elements from 1 to n
• Don't include another instance of n, and it remains to make a multiset of k elements from to 1 to n-1

We terminate when either k or n reaches 0, and if it k reached 0, we give a base case of the empty list. If not, we have the wrong number of elements, and so give the empty list.

Answer 9

Python 3, 81 80

Recursive solution:

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

The function t(n, k, b) returns the list of all k-element multi-subsets of the range from b to n. This list is empty if k <= 0. Otherwise, we break the problem down based on the smallest element of the multi-subset, which we denote by i.

For each i in the range from b to n, we generate all of the k-multi-subsets with smallest element i by starting with [i] and then appending each (k-1)-multi-subset of the range from i to n, which we obtain by recursively calling t(n, k-1, i).

Answer 10

Dyalog APL, 22 bytes

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

Requires ⎕IO←0, which is default in many APL systems. Takes k as left argument, n as right argument.

⍳⍺*⍵ 0 1 2 ... kⁿ
⍺⊥⍣¯1 convert to base k
⍉ transpose
↓ make matrix into list of lists
{⍵[⍋⍵]}¨ sort each...
∪ the unique

Answer 11

J, 18 bytes

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

Similar approach used in @Adám's solution.

Another approach using Cartesian product { for 24 bytes. Takes k on the LHS and n on the RHS.

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

Usage

   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│
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

Explanation

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

Answer 12

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

Note the changed parameter order: 1st is k and 2nd is n. This saved 1 byte in (f(dec k)n).

Answer 13

Mathematica, 36 bytes

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

Please tell me there's a 1/6 bonus for using no []s...Or maybe for the many uses of ##?