Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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]
share|improve this question

12 Answers 12

up vote 8 down vote accepted

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.
share|improve this answer

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
}
share|improve this answer

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.

share|improve this answer
    
@jimmy23013 Not one I'm aware of. – Martin Ender Mar 2 at 9:34
    
I think you can save two bytes with {}∪Sort/@Range@#~Tuples~#2& – A Simmons Mar 3 at 16:02
    
@ASimmons Nice idea, thank you! – Martin Ender Mar 3 at 18:03

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.

share|improve this answer

JavaScript (ES7 proposed), 71 bytes

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

Firefox 30 or later supports [for(...of...)...]. And I get to use keys() for once.

share|improve this answer

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!

share|improve this answer

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
share|improve this answer

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.

share|improve this answer

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

share|improve this answer
    
Welcome to Programming Puzzles & Code Golf! This is a nice first answer. Could you provide an explanation of how the code works? – Alex A. Mar 3 at 4:35
    
Thanks! I've added a brief explanation. – Andrew Gainer-Dewar Mar 4 at 13:06
    
Looks great. Nice solution! – Alex A. Mar 4 at 18:51

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

share|improve this answer

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 ##?

share|improve this answer

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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