Combinations with repetitions
The set of combinations with repetitions is computed from a set, (of cardinality ), and a size of resulting selection, , by reporting the sets of cardinality where each member of those sets is chosen from . In the real world, it is about choosing sets where there is a “large” supply of each type of element and where the order of choice does not matter. For example:
You are encouraged to solve this task according to the task description, using any language you may know.
- Q: How many ways can a person choose two doughnuts from a store selling three types of doughnut: iced, jam, and plain? (i.e., is , , and .)
- A: 6: {iced, iced}; {iced, jam}; {iced, plain}; {jam, jam}; {jam, plain}; {plain, plain}.
Note that both the order of items within a pair, and the order of the pairs given in the answer is not significant; the pairs represent multisets.
Task description
- Write a function/program/routine/.. to generate all the combinations with repetitions of types of things taken at a time and use it to show an answer to the doughnut example above.
- For extra credit, use the function to compute and show just the number of ways of choosing three doughnuts from a choice of ten types of doughnut. Do not show the individual choices for this part.
References:
Ada
Should work for any discrete type: integer, modular, or enumeration.
combinations.adb: <lang Ada>with Ada.Text_IO; procedure Combinations is
generic
type Set is (<>);
function Combinations
(Count : Positive;
Output : Boolean := False)
return Natural;
function Combinations
(Count : Positive;
Output : Boolean := False)
return Natural
is
package Set_IO is new Ada.Text_IO.Enumeration_IO (Set);
type Set_Array is array (Positive range <>) of Set;
Empty_Array : Set_Array (1 .. 0);
function Recurse_Combinations
(Number : Positive;
First : Set;
Prefix : Set_Array)
return Natural
is
Combination_Count : Natural := 0;
begin
for Next in First .. Set'Last loop
if Number = 1 then
Combination_Count := Combination_Count + 1;
if Output then
for Element in Prefix'Range loop
Set_IO.Put (Prefix (Element));
Ada.Text_IO.Put ('+');
end loop;
Set_IO.Put (Next);
Ada.Text_IO.New_Line;
end if;
else
Combination_Count := Combination_Count +
Recurse_Combinations
(Number - 1,
Next,
Prefix & (1 => Next));
end if;
end loop;
return Combination_Count;
end Recurse_Combinations;
begin
return Recurse_Combinations (Count, Set'First, Empty_Array);
end Combinations;
type Donuts is (Iced, Jam, Plain); function Donut_Combinations is new Combinations (Donuts);
subtype Ten is Positive range 1 .. 10; function Ten_Combinations is new Combinations (Ten);
Donut_Count : constant Natural :=
Donut_Combinations (Count => 2, Output => True);
Ten_Count : constant Natural := Ten_Combinations (Count => 3);
begin
Ada.Text_IO.Put_Line ("Total Donuts:" & Natural'Image (Donut_Count));
Ada.Text_IO.Put_Line ("Total Tens:" & Natural'Image (Ten_Count));
end Combinations;</lang>
Output:
ICED+ICED ICED+JAM ICED+PLAIN JAM+JAM JAM+PLAIN PLAIN+PLAIN Total Donuts: 6 Total Tens: 220
Clojure
<lang clojure> (defn combinations [coll k]
(when-let [[x & xs] coll]
(if (= k 1)
(map list coll)
(concat (map (partial cons x) (combinations coll (dec k)))
(combinations xs k)))))
</lang>
Example output:
<lang clojure> user> (combinations '[iced jam plain] 2) ((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain)) </lang>
C
<lang C>#include <stdio.h>
const char * donuts[] = { "iced", "jam", "plain", "something completely different" }; long choose(int * got, int n_chosen, int len, int at, int max_types) {
int i;
long count = 0;
if (n_chosen == len) {
if (!got) return 1;
for (i = 0; i < len; i++)
printf("%s\t", donuts[got[i]]);
printf("\n");
return 1;
}
for (i = at; i < max_types; i++) {
if (got) got[n_chosen] = i;
count += choose(got, n_chosen + 1, len, i, max_types);
}
return count;
}
int main() {
int chosen[3];
choose(chosen, 0, 2, 0, 3);
printf("\nWere there ten donuts, we'd have had %ld choices of three\n",
choose(0, 0, 3, 0, 10));
return 0;
}
</lang>Output:
iced iced iced jam iced plain jam jam jam plain plain plain Were there ten donuts, we'd have had 220 choices of three
CoffeeScript
<lang coffeescript> combos = (arr, k) ->
if k == 1 return ([elem] for elem in arr)
head = arr[0] if arr.length == 1 return [ (head for i in [0...k]) ] combos_with_head = ([head].concat combo for combo in combos arr, k-1) combos_sans_head = combos arr[1...], k combos_with_head.concat combos_sans_head
arr = ['iced', 'jam', 'plain'] console.log "valid pairs from #{arr.join ','}:" console.log combos arr, 2 console.log "#{combos([1..10], 3).length} ways to order 3 donuts given 10 types" </lang>
output <lang> jam,plain: [ [ 'iced', 'iced' ],
[ 'iced', 'jam' ], [ 'iced', 'plain' ], [ 'jam', 'jam' ], [ 'jam', 'plain' ], [ 'plain', 'plain' ] ]
220 ways to order 3 donuts given 10 types </lang>
D
Using lexicographic next bit permutation to generate combinations with repetitions. <lang d>import std.stdio, std.range;
/*immutable*/ const struct CombRep {
immutable uint nt, nc; private /*immutable*/ ulong[] combVal;
this(in uint numType, in uint numChoice) pure nothrow {
assert(0 < numType && numType + numChoice <= 64,
"valid only for nt + nc <= 64 (ulong bit size)");
nt = numType;
nc = numChoice;
if (nc == 0)
return;
auto v = (1UL << (nt - 1)) - 1;
// init to smallest number that has nt-1 bit set
// a set bit is metaphored as a _type_ seperator
immutable limit = v << nc;
// limit is the largest nt-1 bit set number that has nc
// zero-bit a zero-bit means a _choice_ between _type_
// seperators
while (v <= limit) {
combVal ~= v;
if (v == 0)
break;
// get next nt-1 bit number
immutable t = (v | (v - 1)) + 1;
v = t | ((((t & -t) / (v & -v)) >> 1) - 1);
}
}
uint length() @property const pure nothrow {
return combVal.length;
}
uint[] opIndex(in uint idx) const pure nothrow {
return val2set(combVal[idx]);
}
int opApply(int delegate(ref uint[]) dg) {
foreach (v; combVal) {
auto set = val2set(v);
if (dg(set))
break;
}
return 1;
}
private uint[] val2set(in ulong v) const pure nothrow {
// convert bit pattern to selection set
immutable uint bitLimit = nt + nc - 1;
uint typeIdx = 0;
uint[] set;
foreach (bitNum; 0 .. bitLimit)
if (v & (1 << (bitLimit - bitNum - 1)))
typeIdx++;
else
set ~= typeIdx;
return set;
}
}
// For finite Random Access Range auto combRep(R)(R types, in uint numChoice) /*pure nothrow*/ if (hasLength!R && isRandomAccessRange!R) {
ElementType!R[][] result;
foreach (s; CombRep(types.length, numChoice)) {
ElementType!R[] r;
foreach (i; s)
r ~= types[i];
result ~= r;
}
return result;
}
void main() {
foreach (e; combRep(["iced", "jam", "plain"], 2))
// writefln("%5s", e);
writeln(e);
writeln("Ways to select 3 from 10 types is ",
CombRep(10, 3).length);
}</lang> output:
["iced", "iced"] ["iced", "jam"] ["iced", "plain"] ["jam", "jam"] ["jam", "plain"] ["plain", "plain"] Ways to select 3 from 10 types is 220
Go
Concise recursive
<lang go>package main
import "fmt"
func combrep(n int, lst []string) [][]string {
if n == 0 {
return [][]string{nil}
}
if len(lst) == 0 {
return nil
}
r := combrep(n, lst[1:])
for _, x := range combrep(n-1, lst) {
r = append(r, append(x, lst[0]))
}
return r
}
func main() {
fmt.Println(combrep(2, []string{"iced", "jam", "plain"}))
fmt.Println(len(combrep(3,
[]string{"1", "2", "3", "4", "5", "6", "7", "8", "9", "10"})))
}</lang> Output:
[[plain plain] [plain jam] [jam jam] [plain iced] [jam iced] [iced iced]] 220
Channel
Using channel and goroutine, showing how to use synced or unsynced communication. <lang go>package main
import "fmt"
func picks(picked []int, pos, need int, c chan[]int, do_wait bool) { if need == 0 { if do_wait { c <- picked <-c } else { // if we want only the count, there's no need to // sync between coroutines; let it clobber the array c <- []int {} } return }
if pos <= 0 { if need == len(picked) { c <- nil } return }
picked[len(picked) - need] = pos - 1 picks(picked, pos, need - 1, c, do_wait) // choose the current donut picks(picked, pos - 1, need, c, do_wait) // or don't }
func main() { donuts := []string {"iced", "jam", "plain" }
picked := make([]int, 2) ch := make(chan []int)
// true: tell the channel to wait for each sending, because // otherwise the picked array may get clobbered before we can do // anything to it go picks(picked, len(donuts), len(picked), ch, true)
var cc []int for { if cc = <-ch; cc == nil { break } for _, i := range cc { fmt.Printf("%s ", donuts[i]) } fmt.Println() ch <- nil // sync }
picked = make([]int, 3) // this time we only want the count, so tell goroutine to keep going // and work the channel buffer go picks(picked, 10, len(picked), ch, false) count := 0 for { if cc = <-ch; cc == nil { break } count++ } fmt.Printf("\npicking 3 of 10: %d\n", count) }</lang> Output:
plain plain plain jam plain iced jam jam jam iced iced iced picking 3 of 10: 220
Multiset
This version has proper representation of sets and multisets. <lang go>package main
import (
"fmt" "sort" "strconv"
)
// Go maps are an easy representation for sets as long as the element type // of the set is valid as a key type for maps. Strings are easy. We follow // the convention of always storing true for the value. type set map[string]bool
// Multisets of strings are easy in the same way. We store the multiplicity // of the element as the value. type multiset map[string]int
// But multisets are not valid as a map key type so we must do something // more involved to make a set of multisets, which is the desired return // type for the combrep function required by the task. We can store the // multiset as the value, but we derive a unique string to use as a key. type msSet map[string]multiset
// The key method returns this string. The string will simply be a text // representation of the contents of the multiset. The standard // printable representation of the multiset cannot be used however, because // Go maps are not ordered. Instead, the contents are copied to a slice, // which is sorted to produce something with a printable representation // that will compare == for mathematically equal multisets. // // Of course there is overhead for this and if performance were important, // a different representation would be used for multisets, one that didn’t // require sorting to produce a key... func (m multiset) key() string {
pl := make(pairList, len(m))
i := 0
for k, v := range m {
pl[i] = msPair{k, v}
i++
}
sort.Sort(pl)
return fmt.Sprintf("%v", pl)
}
// Types and methods needed for sorting inside of mulitset.key() type msPair struct {
string int
} type pairList []msPair func (p pairList) Len() int { return len(p) } func (p pairList) Swap(i, j int) { p[i], p[j] = p[j], p[i] } func (p pairList) Less(i, j int) bool { return p[i].string < p[j].string }
// Function required by task. func combrep(n int, lst set) msSet {
if n == 0 {
var ms multiset
return msSet{ms.key(): ms}
}
if len(lst) == 0 {
return msSet{}
}
var car string
var cdr set
for ele := range lst {
if cdr == nil {
car = ele
cdr = make(set)
} else {
cdr[ele] = true
}
}
r := combrep(n, cdr)
for _, x := range combrep(n-1, lst) {
c := multiset{car: 1}
for k, v := range x {
c[k] += v
}
r[c.key()] = c
}
return r
}
// Driver for examples required by task. func main() {
// Input is a set.
three := set{"iced": true, "jam": true, "plain": true}
// Output is a set of multisets. The set is a Go map:
// The key is a string representation that compares equal
// for equal multisets. We ignore this here. The value
// is the multiset. We print this.
for _, ms := range combrep(2, three) {
fmt.Println(ms)
}
ten := make(set)
for i := 1; i <= 10; i++ {
ten[strconv.Itoa(i)] = true
}
fmt.Println(len(combrep(3, ten)))
}</lang> Output:
map[plain:1 jam:1] map[plain:2] map[iced:1 jam:1] map[jam:2] map[iced:1 plain:1] map[iced:2] 220
Haskell
<lang haskell> import Data.List
-- Return the combinations, with replacement, of k items from the -- list. We ignore the case where k is greater than the length of -- the list. combsWithRep 0 _ = [[]] combsWithRep _ [] = [] combsWithRep k xxs@(x:xs) = map (x:) (combsWithRep (k-1) xxs) ++ combsWithRep k xs
countCombsWithRep k = length . combsWithRep k
main = do
print $ combsWithRep 2 ["iced","jam","plain"] print $ countCombsWithRep 3 [1..10]
</lang>
Example output:
<lang haskell> [["iced","iced"],["iced","jam"],["iced","plain"],["jam","jam"],["jam","plain"],["plain","plain"]] 220 </lang>
Icon and Unicon
Following procedure is a generator, which generates each combination of length n in turn: <lang Icon>
- generate all combinations of length n from list L,
- including repetitions
procedure combinations_repetitions (L, n)
if n = 0
then suspend [] # if reach 0, then return an empty list
else if *L > 0
then {
# keep the first element
item := L[1]
# get all of length n in remaining list
every suspend (combinations_repetitions (L[2:0], n))
# get all of length n-1 in remaining list
# and add kept element to make list of size n
every i := combinations_repetitions (L, n-1) do
suspend [item] ||| i
}
end </lang>
Test procedure:
<lang Icon>
- convenience function
procedure write_list (l)
every (writes (!l || " ")) write ()
end
- testing routine
procedure main ()
# display all combinations for 2 of iced/jam/plain
every write_list (combinations_repetitions(["iced", "jam", "plain"], 2))
# get a count for number of ways to select 3 items from 10
every push(num_list := [], 1 to 10)
count := 0
every combinations_repetitions(num_list, 3) do count +:= 1
write ("There are " || count || " possible combinations of 3 from 10")
end </lang>
Output:
plain plain jam plain jam jam iced plain iced jam iced iced There are 220 possible combinations of 3 from 10
J
<lang j>rcomb=: >@~.@:(/:~&.>)@,@{@# <</lang>
Example use:
<lang j> 2 rcomb ;:'iced jam plain' ┌─────┬─────┐ │iced │iced │ ├─────┼─────┤ │iced │jam │ ├─────┼─────┤ │iced │plain│ ├─────┼─────┤ │jam │jam │ ├─────┼─────┤ │jam │plain│ ├─────┼─────┤ │plain│plain│ └─────┴─────┘
#3 rcomb i.10 NB. ways to choose 3 items from 10 with replacement
220</lang>
Java
MultiCombinationsTester.java <lang java> import com.objectwave.utility.*;
public class MultiCombinationsTester {
public MultiCombinationsTester() throws CombinatoricException {
Object[] objects = {"iced", "jam", "plain"};
//Object[] objects = {"abba", "baba", "ab"};
//Object[] objects = {"aaa", "aa", "a"};
//Object[] objects = {(Integer)1, (Integer)2, (Integer)3, (Integer)4};
MultiCombinations mc = new MultiCombinations(objects, 2);
while (mc.hasMoreElements()) {
for (int i = 0; i < mc.nextElement().length; i++) {
System.out.print(mc.nextElement()[i].toString() + " ");
}
System.out.println();
}
// Extra credit:
System.out.println("----------");
System.out.println("The ways to choose 3 items from 10 with replacement = " + MultiCombinations.c(10, 3));
} // constructor
public static void main(String[] args) throws CombinatoricException {
new MultiCombinationsTester();
}
} // class </lang>
MultiCombinations.java <lang java> import com.objectwave.utility.*; import java.util.*;
public class MultiCombinations {
private HashSet<String> set = new HashSet<String>(); private Combinations comb = null; private Object[] nextElem = null;
public MultiCombinations(Object[] objects, int k) throws CombinatoricException {
k = Math.max(0, k);
Object[] myObjects = new Object[objects.length * k];
for (int i = 0; i < objects.length; i++) {
for (int j = 0; j < k; j++) {
myObjects[i * k + j] = objects[i];
}
}
comb = new Combinations(myObjects, k);
} // constructor
boolean hasMoreElements() {
boolean ret = false;
nextElem = null;
int oldCount = set.size();
while (comb.hasMoreElements()) {
Object[] elem = (Object[]) comb.nextElement();
String str = "";
for (int i = 0; i < elem.length; i++) {
str += ("%" + elem[i].toString() + "~");
}
set.add(str);
if (set.size() > oldCount) {
nextElem = elem;
ret = true;
break;
}
}
return ret;
} // hasMoreElements()
Object[] nextElement() {
return nextElem;
}
static java.math.BigInteger c(int n, int k) throws CombinatoricException {
return Combinatoric.c(n + k - 1, k);
}
} // class </lang>
Output:
iced iced iced jam iced plain jam jam jam plain plain plain ---------- The ways to choose 3 items from 10 with replacement = 220
JavaScript
<lang javascript><html><head><title>Donuts</title></head>
<body>
<script type="application/javascript">
function disp(x) { var e = document.createTextNode(x + '\n'); document.getElementById('x').appendChild(e); }
function pick(n, got, pos, from, show) { var cnt = 0; if (got.length == n) { if (show) disp(got.join(' ')); return 1; } for (var i = pos; i < from.length; i++) { got.push(from[i]); cnt += pick(n, got, i, from, show); got.pop(); } return cnt; }
disp(pick(2, [], 0, ["iced", "jam", "plain"], true) + " combos"); disp("pick 3 out of 10: " + pick(3, [], 0, "a123456789".split(), false) + " combos"); </script></body></html></lang>output<lang>iced iced iced jam iced plain jam jam jam plain plain plain 6 combos pick 3 out of 10: 220 combos</lang>
Mathematica
<lang Mathematica>DeleteDuplicates[Tuples[{"iced", "jam", "plain"}, 2],Sort[#1] == Sort[#2] &] ->{{"iced", "iced"}, {"iced", "jam"}, {"iced", "plain"}, {"jam", "jam"}, {"jam", "plain"}, {"plain", "plain"}}
Combi[x_, y_] := Binomial[(x + y) - 1, y] Combi[3, 2] -> 6 Combi[10, 3] ->220 </lang>
Mercury
comb.choose uses a nondeterministic list.member/2 to pick values from the list, and just puts them into a bag (a multiset). comb.choose_all gathers all of the possible bags that comb.choose would produce for a given list and number of picked values, and turns them into lists (for readability).
comb.count_choices shows off solutions.aggregate (which allows you to fold over solutions as they're found) rather than list.length and the factorial function.
<lang Mercury>:- module comb.
- - interface.
- - import_module list, int, bag.
- - pred choose(list(T)::in, int::in, bag(T)::out) is nondet.
- - pred choose_all(list(T)::in, int::in, list(list(T))::out) is det.
- - pred count_choices(list(T)::in, int::in, int::out) is det.
- - implementation.
- - import_module solutions.
choose(L, N, R) :- choose(L, N, bag.init, R).
- - pred choose(list(T)::in, int::in, bag(T)::in, bag(T)::out) is nondet.
choose(L, N, !R) :-
( N = 0 ->
true
;
member(X, L),
bag.insert(!.R, X, !:R),
choose(L, N - 1, !R)
).
choose_all(L, N, R) :-
solutions(choose(L, N), R0),
list.map(bag.to_list, R0, R).
count_choices(L, N, Count) :-
aggregate(choose(L, N), count, 0, Count).
- - pred count(T::in, int::in, int::out) is det.
count(_, N0, N) :- N0 + 1 = N.</lang>
Usage:
<lang Mercury>:- module comb_ex.
- - interface.
- - import_module io.
- - pred main(io::di, io::uo) is det.
- - implementation.
- - import_module comb, list, string.
- - type doughtnuts
---> iced ; jam ; plain
; glazed ; chocolate ; cream_filled ; mystery
; cubed ; cream_covered ; explosive.
main(!IO) :-
choose_all([iced, jam, plain], 2, L),
count_choices([iced, jam, plain, glazed, chocolate, cream_filled,
mystery, cubed, cream_covered, explosive], 3, N),
io.write(L, !IO), io.nl(!IO),
io.write_string(from_int(N) ++ " choices.\n", !IO).</lang>
Output:
[[iced, iced], [jam, jam], [plain, plain], [iced, jam], [iced, plain], [jam, plain]] 220 choices.
PARI/GP
<lang parigp>ways(k,v,s=[])={ if(k==0,return([])); if(k==1,return(vector(#v,i,concat(s,[v[i]])))); if(#v==1,return(ways(k-1,v,concat(s,v)))); my(u=vecextract(v,2^#v-2)); concat(ways(k-1,v,concat(s,[v[1]])),ways(k,u,s)) }; xc(k,v)=binomial(#v+k-1,k); ways(2, ["iced","jam","plain"])</lang>
Perl
The highly readable version: <lang perl>sub p { $_[0] ? map p($_[0] - 1, [@{$_[1]}, $_[$_]], @_[$_ .. $#_]), 2 .. $#_ : $_[1] } sub f { $_[0] ? $_[0] * f($_[0] - 1) : 1 } sub pn{ f($_[0] + $_[1] - 1) / f($_[0]) / f($_[1] - 1) }
for (p(2, [], qw(iced jam plain))) {
print "@$_\n";
}
printf "\nThere are %d ways to pick 7 out of 10\n", pn(7,10); </lang>
Prints:
iced iced iced jam iced plain jam jam jam plain plain plain There are 11440 ways to pick 7 out of 10
Perl 6
<lang perl6>proto combs_with_rep (Int, @) {*}
multi combs_with_rep (0, @) { [] } multi combs_with_rep ($, []) { () } multi combs_with_rep ($n, [$head, *@tail]) {
map( { [$head, @^others] },
combs_with_rep($n - 1, [$head, @tail]) ),
combs_with_rep($n, @tail);
}
.perl.say for combs_with_rep( 2, [< iced jam plain >] );
- Extra credit:
sub postfix:<!> { [*] 1..$^n } sub combs_with_rep_count ($k, $n) { ($n + $k - 1)! / $k! / ($n - 1)! }
say combs_with_rep_count( 3, 10 );</lang>
Output:
["iced", "iced"] ["iced", "jam"] ["iced", "plain"] ["jam", "jam"] ["jam", "plain"] ["plain", "plain"] 220
PHP
<lang PHP> <?php
function combos($arr, $k) {
if ($k == 0) {
return array(array());
}
$head = $arr[0];
if (count($arr) == 1) {
$result = array();
for ($i = 0; $i < $k; $i += 1) {
array_push($result, $head);
}
return array($result);
}
$combos = array();
$subcombos = combos($arr, $k-1);
foreach ($subcombos as $subcombo) {
$combo = array($head);
$combo = array_merge($combo, $subcombo);
array_push($combos, $combo);
}
array_shift($arr);
$combos = array_merge($combos, combos($arr, $k));
return $combos;
}
$arr = array("iced", "jam", "plain");
$result = combos($arr, 2);
foreach($result as $combo) {
foreach($combo as $elem) {
echo $elem, " ";
}
echo "
";
}
$donuts = range(1, 10);
$num_donut_combos = count(combos($donuts, 3));
echo "$num_donut_combos ways to order 3 donuts given 10 types";
?> </lang> output in the browser: <lang> iced iced iced jam iced plain jam jam jam plain plain plain 220 ways to order 3 donuts given 10 types </lang>
PicoLisp
<lang PicoLisp>(de combrep (N Lst)
(cond
((=0 N) '(NIL))
((not Lst))
(T
(conc
(mapcar
'((X) (cons (car Lst) X))
(combrep (dec N) Lst) )
(combrep N (cdr Lst)) ) ) ) )</lang>
Output:
: (combrep 2 '(iced jam plain)) -> ((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain)) : (length (combrep 3 (range 1 10))) -> 220
PureBasic
<lang PureBasic>Procedure nextCombination(Array combIndex(1), elementCount)
;combIndex() must be dimensioned to 'k' - 1, elementCount equals 'n' - 1
;combination produced includes repetition of elements and is represented by the array combIndex()
Protected i, indexValue, combSize = ArraySize(combIndex()), curIndex
;update indexes
curIndex = combSize
Repeat
combIndex(curIndex) + 1
If combIndex(curIndex) > elementCount
curIndex - 1
If curIndex < 0
For i = 0 To combSize
combIndex(i) = 0
Next
ProcedureReturn #False ;array reset to first combination
EndIf
ElseIf curIndex < combSize
indexValue = combIndex(curIndex)
Repeat
curIndex + 1
combIndex(curIndex) = indexValue
Until curIndex = combSize
EndIf
Until curIndex = combSize
ProcedureReturn #True ;array contains next combination
EndProcedure
Procedure.s display(Array combIndex(1), Array dougnut.s(1))
Protected i, elementCount = ArraySize(combIndex()), output.s = " " For i = 0 To elementCount output + dougnut(combIndex(i)) + " + " Next ProcedureReturn Left(output, Len(output) - 3)
EndProcedure
DataSection
Data.s "iced", "jam", "plain"
EndDataSection
If OpenConsole()
Define n = 3, k = 2, i, combinationCount
Dim combIndex(k - 1)
Dim dougnut.s(n - 1)
For i = 0 To n - 1: Read.s dougnut(i): Next
PrintN("Combinations of " + Str(k) + " dougnuts taken " + Str(n) + " at a time with repetitions.")
combinationCount = 0
Repeat
PrintN(display(combIndex(), dougnut()))
combinationCount + 1
Until Not nextCombination(combIndex(), n - 1)
PrintN("Total combination count: " + Str(combinationCount))
;extra credit
n = 10: k = 3
Dim combIndex(k - 1)
combinationCount = 0
Repeat: combinationCount + 1: Until Not nextCombination(combIndex(), n - 1)
PrintN(#CRLF$ + "Ways to select " + Str(k) + " items from " + Str(n) + " types: " + Str(combinationCount))
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()
EndIf </lang>The nextCombination() procedure operates on an array of indexes to produce the next combination. This generalization allows producing a combination from any collection of elements. nextCombination() returns the value #False when the indexes have reach their maximum values and are then reset.
Sample output:
Combinations of 2 dougnuts taken 3 at a time with repetitions. iced + iced iced + jam iced + plain jam + jam jam + plain plain + plain Total combination count: 6 Ways to select 3 items from 10 types: 220
Python
<lang python>>>> from itertools import combinations_with_replacement >>> n, k = 'iced jam plain'.split(), 2 >>> list(combinations_with_replacement(n,k)) [('iced', 'iced'), ('iced', 'jam'), ('iced', 'plain'), ('jam', 'jam'), ('jam', 'plain'), ('plain', 'plain')] >>> # Extra credit >>> len(list(combinations_with_replacement(range(10), 3))) 220 >>> </lang>
References:
REXX
<lang rexx> /*REXX program shows a set of combinations with repetitions. */
stores=3 doughnuts=2
/*the following uses a subroutine ($PERMSETS) that */
/*can calculat PermSets, CombSets, or rCombSets,*/
/*depending on the setting of the F variable. */
f='RCOMBSETS' sep=',' list=$permsets(stores,doughnuts,sep,"iced jam plain")
do j=1 for words(list)
say center(word(list,j),30)
end
/*The task was to use the same function to calculate */
/* the number of ways of choosing three doughnuts */
/* from a choice of ten types of doughnuts. */
/*It would be simplier to use the RCOMB function. */
types=10
doughnuts=3 list=$permsets(types,doughnuts) say say 'Number of ways to choose three doughnuts from ten types: ' words(list) say 'Number of ways to choose 3 doughnuts from a choice of 10:' rcomb(10,3) exit
/*────────────────────────────────$PERMSETS subroutine──────────────────*/
$permsets: procedure expose f /*gen COMB or PERM sets. */
@abc='abcdefghijklmnopqrstuvwxyz'; @abcu=@abc; upper @abcu
@abcs=@abcu||@abc; @0abcs=123456789||@abcs
parse arg x,y,between,usyms /*take X things Y at a time.*/
/*X can't be > length(@0abcs). */
@.= $.= sep= k=0 @0abcs_=@0abcs||xrange(' ','fe'x) !=' '
do j=1 for words(usyms) /*build list of symbols. */ _=word(usyms,j) /*get a user symbol. */ if wordpos(_,!)\==0 then iterate k=k+1 $.k=_ /*append to the sumbol list.*/ !=! _ if length(_)\==1 then sep='-' end
do j=1 for x while k<x _=substr(@0abcs_,j,1) /*get a character for symbol*/ if wordpos(_,!)\==0 then iterate k=k+1 $.k=_ /*append to the sumbol list.*/ !=! _ end
!= if between== then between=sep /*use appropriate seperator.*/ return $permgen(1)
/*────────────────────────────────$PERMGEN subroutine───────────────────*/
$permgen: procedure expose @. $. ! between x y f; parse arg ?
_=left(f,1)
fr=_=='R'
fc=_=='C'|fr
if ?>y then do
c=@.1; _=$.c
do j=2 to y
c=@.j; _=_||between||$.c
end
!=! _
end
else do
e=x
if fc then if \fr & ?==1 then e=x-1
do q=1 for e
do k=1 for ?-1
if \fr then if @.k==q then iterate q
if fc then if q<@.k then iterate q
end
@.?=q
call $permgen(?+1) /*construction permutation recursively*/
end
end
return strip(!)
/*────────────────────────────────RCOMB subroutine──────────────────────*/
rcomb: procedure; arg x,y; return $comb(x+y-1,y)
/*────────────────────────────────$COMB subroutine──────────────────────*/
$comb: procedure; arg x,y; if x=y then return 1; if y>x then return 0;
if x-y<y then y=x-y; _=1; do j=x-y+1 to x; _=_*j; end; return _/$fact(y)
/*────────────────────────────────$FACT subroutine──────────────────────*/
$fact: procedure; parse arg x; !=1; do j=2 to x; !=!*j; end; return !
</lang>
Output:
iced,iced
iced,jam
iced,plain
jam,jam
jam,plain
plain,plain
Number of ways to choose three doughnuts from ten types: 220
Number of ways to choose 3 doughnuts from a choice of 10: 220
Ruby
Ruby 1.9.2 <lang ruby> possible_doughnuts = ['iced', 'jam', 'plain'].repeated_combination(2) puts "There are #{possible_doughnuts.count} possible doughnuts:" possible_doughnuts.each{|doughnut_combi| puts doughnut_combi.join(' and ')}
</lang> Output:
There are 6 possible doughnuts: iced and iced iced and jam iced and plain jam and jam jam and plain plain and plain
Scala
Scala has a combinations method in the standard library. <lang scala> object CombinationsWithRepetition {
def multi[A](as: List[A], k: Int): List[List[A]] =
(List.fill(k)(as)).flatten.combinations(k).toList
def main(args: Array[String]): Unit = {
val doughnuts = multi(List("iced", "jam", "plain"), 2)
for (combo <- doughnuts) println(combo.mkString(","))
val bonus = multi(List(0,1,2,3,4,5,6,7,8,9), 3).size
println("There are "+bonus+" ways to choose 3 items from 10 choices")
}
} </lang>
Output
iced,iced iced,jam iced,plain jam,jam jam,plain plain,plain There are 220 ways to choose 3 items from 10 choices
Scheme
<lang scheme> (define combinations
(lambda (lst k)
(cond ((null? lst) '())
((= k 1) (map list lst))
(else
(append
(map
(lambda (x)
(cons (car lst) x))
(combinations lst (- k 1)))
(combinations (cdr lst) k))))))
</lang>
Tcl
<lang tcl>package require Tcl 8.5 proc combrepl {set n {presorted no}} {
if {!$presorted} {
set set [lsort $set]
}
if {[incr n 0] < 1} {
return {}
} elseif {$n < 2} {
return $set
}
# Recursive call
set res [combrepl $set [incr n -1] yes]
set result {}
foreach item $set {
foreach inner $res { dict set result [lsort [list $item {*}$inner]] {} }
} return [dict keys $result]
}
puts [combrepl {iced jam plain} 2] puts [llength [combrepl {1 2 3 4 5 6 7 8 9 10} 3]]</lang> Output:
{iced iced} {iced jam} {iced plain} {jam jam} {jam plain} {plain plain}
220
Ursala
<lang Ursala>#import std
- import nat
cwr = ~&s+ -<&*+ ~&K0=>&^|DlS/~& iota # takes a set and a selection size
- cast %gLSnX
main = ^|(~&,length) cwr~~/(<'iced','jam','plain'>,2) ('1234567890',3)</lang> output:
(
{
<'iced','iced'>,
<'iced','jam'>,
<'iced','plain'>,
<'jam','jam'>,
<'jam','plain'>,
<'plain','plain'>},
220)