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:
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
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