11
\$\begingroup\$

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]
\$\endgroup\$

13 Answers 13

8
\$\begingroup\$

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.
\$\endgroup\$
0
8
\$\begingroup\$

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
}
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ @jimmy23013 Not one I'm aware of. \$\endgroup\$ Mar 2, 2016 at 9:34
  • \$\begingroup\$ I think you can save two bytes with {}∪Sort/@Range@#~Tuples~#2& \$\endgroup\$
    – A Simmons
    Mar 3, 2016 at 16:02
  • \$\begingroup\$ @ASimmons Nice idea, thank you! \$\endgroup\$ Mar 3, 2016 at 18:03
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
0
1
\$\begingroup\$

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
\$\endgroup\$
0
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ Welcome to Programming Puzzles & Code Golf! This is a nice first answer. Could you provide an explanation of how the code works? \$\endgroup\$
    – Alex A.
    Mar 3, 2016 at 4:35
  • \$\begingroup\$ Looks great. Nice solution! \$\endgroup\$
    – Alex A.
    Mar 4, 2016 at 18:51
1
\$\begingroup\$

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

\$\endgroup\$
0
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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