Combinations with repetitions
You are encouraged to solve this task according to the task description, using any language you may know.
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:
- 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: ; ; ; ; ; .
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 sets.
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>
D
Using lexicographic next bit permutation to generate combinations with repetitions. <lang d>import std.stdio, std.range ;
struct CombRep {
immutable uint nt, nc ; private ulong[] combVal; this(uint numType, uint numChoice) { 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 ; auto t = (v | (v - 1)) + 1 ; // get next nt-1 bit number v = t | ((((t & -t) / (v & -v)) >> 1) - 1) ; } } uint length() @property { return combVal.length ; } uint[] opIndex(uint idx) { 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(ulong v) pure { // convert bit pattern to selection set uint typeIdx = 0, bitLimit = nt + nc - 1 ; 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, uint numChoice)
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) ; writefln("Ways to select 3 from 10 types is %d", 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
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>
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
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
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
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