Generate combinations with replacement
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
}
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.
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
.