Combinations with repetitions

From Rosetta Code
Jump to: navigation, search
Task
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, S (of cardinality n), and a size of resulting selection, k, by reporting the sets of cardinality k where each member of those sets is chosen from S. 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., S is {iced,jam,plain}, | S | = 3, and k = 2.)
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.
Also note that doughnut can also be spelled donut.

Task description

  • Write a function/program/routine/.. to generate all the combinations with repetitions of n types of things taken k 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:

See Also:

The number of samples of size k from n objects.
With combinations and permutations generation tasks.
Order Unimportant Order Important
Without replacement  \binom nk = ^n\operatorname C_k = \frac{n(n-1)\ldots(n-k+1)}{k(k-1)\dots1} ^n\operatorname P_k = n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)
Task: Combinations Task: Permutations
With replacement  \binom {n+k-1}k = ^{n+k-1}\operatorname C_k = {(n+k-1)! \over (n-1)!k!} nk
Task: Combinations with repetitions Task: Permutations with repetitions

Contents

[edit] Ada

Should work for any discrete type: integer, modular, or enumeration.

combinations.adb:

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;
Output:
ICED+ICED
ICED+JAM
ICED+PLAIN
JAM+JAM
JAM+PLAIN
PLAIN+PLAIN
Total Donuts: 6
Total Tens: 220

[edit] BBC BASIC

      DIM list$(2), chosen%(2)
list$() = "iced", "jam", "plain"
PRINT "Choices of 2 from 3:"
choices% = FNchoose(0, 2, 0, 3, chosen%(), list$())
PRINT "Total choices = " ; choices%
 
PRINT '"Choices of 3 from 10:"
choices% = FNchoose(0, 3, 0, 10, chosen%(), nul$())
PRINT "Total choices = " ; choices%
END
 
DEF FNchoose(n%, l%, p%, m%, g%(), RETURN n$())
LOCAL i%, c%
IF n% = l% THEN
IF !^n$() THEN
FOR i% = 0 TO n%-1
PRINT " " n$(g%(i%)) ;
NEXT
PRINT
ENDIF
= 1
ENDIF
FOR i% = p% TO m%-1
g%(n%) = i%
c% += FNchoose(n% + 1, l%, i%, m%, g%(), n$())
NEXT
= c%
Output:
Choices of 2 from 3:
 iced iced
 iced jam
 iced plain
 jam jam
 jam plain
 plain plain
Total choices = 6

Choices of 3 from 10:
Total choices = 220

[edit] Bracmat

This minimalist solution expresses the answer as a sum of products. Bracmat automatically normalises such expressions: terms and factors are sorted alphabetically, products containing a sum as a factor are decomposed in a sum of factors (unless the product is not itself term in a multiterm expression). Like factors are converted to a single factor with an appropriate exponent, so ice^2 is to be understood as ice twice.

( ( choices
= n things thing result
.  !arg:(?n.?things)
& ( !n:0&1
| 0:?result
& (  !things
 :  ?
( %?`thing ?:?things
&  !thing*choices$(!n+-1.!things)+!result
 : ?result
& ~
)
| !result
)
)
)
& out$(choices$(2.iced jam plain))
& out$(choices$(3.iced jam plain butter marmite tahin fish salad onion grass):?+[?N&!N)
);
Output:
iced^2+jam^2+plain^2+iced*jam+iced*plain+jam*plain
220

[edit] Clojure

Translation of: Scheme
 
(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)))))
 
Output:
user> (combinations '[iced jam plain] 2)
((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))

[edit] 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;
}
 
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

[edit] Fortran

 
program main
integer :: chosen(4)
integer :: ssize
 
character(len=50) :: donuts(4) = [ "iced", "jam", "plain", "something completely different" ]
 
ssize = choose( chosen, 2, 3 )
write(*,*) "Total = ", ssize
 
contains
 
recursive function choose( got, len, maxTypes, nChosen, at ) result ( output )
integer :: got(:)
integer :: len
integer :: maxTypes
integer :: output
integer, optional :: nChosen
integer, optional :: at
 
integer :: effNChosen
integer :: effAt
 
integer :: i
integer :: counter
 
effNChosen = 1
if( present(nChosen) ) effNChosen = nChosen
 
effAt = 1
if( present(at) ) effAt = at
 
if ( effNChosen == len+1 ) then
do i=1,len
write(*,"(A10,5X)", advance='no') donuts( got(i)+1 )
end do
 
write(*,*) ""
 
output = 1
return
end if
 
counter = 0
do i=effAt,maxTypes
got(effNChosen) = i-1
counter = counter + choose( got, len, maxTypes, effNChosen + 1, i )
end do
 
output = counter
return
end function choose
 
end program main
 
Output:
iced           iced            
iced           jam             
iced           plain           
jam            jam             
jam            plain           
plain          plain           
 Total =            6

[edit] CoffeeScript

 
combos = (arr, k) ->
return [ [] ] if k == 0
return [] if arr.length == 0
 
combos_with_head = ([arr[0]].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"
 
Output:
jam,plain:
[ [ 'iced', 'iced' ],
  [ 'iced', 'jam' ],
  [ 'iced', 'plain' ],
  [ 'jam', 'jam' ],
  [ 'jam', 'plain' ],
  [ 'plain', 'plain' ] ]
220 ways to order 3 donuts given 10 types

[edit] D

Using lexicographic next bit permutation to generate combinations with repetitions.

import std.stdio, std.range;
 
const struct CombRep {
immutable uint nt, nc;
private const ulong[] combVal;
 
this(in uint numType, in uint numChoice) pure nothrow
in {
assert(0 < numType && numType + numChoice <= 64,
"Valid only for nt + nc <= 64 (ulong bit size)");
} body {
nt = numType;
nc = numChoice;
if (nc == 0)
return;
ulong 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;
 
ulong[] localCombVal;
// 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) {
localCombVal ~= 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);
}
this.combVal = localCombVal;
}
 
uint length() @property const pure nothrow {
return combVal.length;
}
 
uint[] opIndex(in uint idx) const pure nothrow {
return val2set(combVal[idx]);
}
 
int opApply(immutable int delegate(in ref uint[]) dg) {
foreach (immutable 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 (immutable 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 (const s; CombRep(types.length, numChoice)) {
ElementType!R[] r;
foreach (immutable i; s)
r ~= types[i];
result ~= r;
}
 
return result;
}
 
void main() {
foreach (const e; combRep(["iced", "jam", "plain"], 2))
writefln("%-(%5s %)", e);
writeln("Ways to select 3 from 10 types is ",
CombRep(10, 3).length);
}
Output:
 iced  iced
 iced   jam
 iced plain
  jam   jam
  jam plain
plain plain
Ways to select 3 from 10 types is 220

[edit] Short Recursive Version

import std.stdio, std.range, std.algorithm;
 
T[][] combsRep(T)(T[] lst, in int k) {
if (k == 0)
return [[]];
if (lst.empty)
return null;
 
return combsRep(lst, k - 1).map!(L => lst[0] ~ L).array
~ combsRep(lst[1 .. $], k);
}
 
void main() {
["iced", "jam", "plain"].combsRep(2).writeln;
10.iota.array.combsRep(3).length.writeln;
}
Output:
[["iced", "iced"], ["iced", "jam"], ["iced", "plain"], ["jam", "jam"], ["jam", "plain"], ["plain", "plain"]]
220

[edit] Egison

 
(define $comb/rep
(lambda [$n $xs]
(match-all xs (list something)
[(loop $i [1 ,n] <join _ (& <cons $a_i _> ...)> _) a])))
 
(test (comb/rep 2 {"iced" "jam" "plain"}))
 
Output:
{[|"iced" "iced"|] [|"iced" "jam"|] [|"jam" "jam"|] [|"iced" "plain"|] [|"jam" "plain"|] [|"plain" "plain"|]}

[edit] Erlang

 
-module(comb).
-compile(export_all).
 
comb_rep(0,_) ->
[[]];
comb_rep(_,[]) ->
[];
comb_rep(N,[H|T]=S) ->
[[H|L] || L <- comb_rep(N-1,S)]++comb_rep(N,T).
 
Output:
94> comb:comb_rep(2,[iced,jam,plain]).
[[iced,iced],
 [iced,jam],
 [iced,plain],
 [jam,jam],
 [jam,plain],
 [plain,plain]]
95> length(comb:comb_rep(3,lists:seq(1,10))).
220

[edit] GAP

# Built-in
UnorderedTuples(["iced", "jam", "plain"], 2);

[edit] Go

[edit] Concise recursive

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"})))
}
Output:
[[plain plain] [plain jam] [jam jam] [plain iced] [jam iced] [iced iced]]
220

[edit] Channel

Using channel and goroutine, showing how to use synced or unsynced communication.

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)
}
Output:
plain plain 
plain jam 
plain iced 
jam jam 
jam iced 
iced iced 

picking 3 of 10: 220

[edit] Multiset

This version has proper representation of sets and multisets.

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

[edit] Haskell

-- 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 :: Int -> [a] -> [[a]]
combsWithRep 0 _ = [[]]
combsWithRep _ [] = []
combsWithRep k xxs@(x:xs) = map (x:) (combsWithRep (k-1) xxs) ++ combsWithRep k xs
 
binomial n m = (f n) `div` (f (n - m)) `div` (f m) where
f n = if n == 0 then 1 else n * f (n - 1)
 
countCombsWithRep k lst = binomial (k - 1 + length lst) k
-- countCombsWithRep k = length . combsWithRep k
 
main = do
print $ combsWithRep 2 ["iced","jam","plain"]
print $ countCombsWithRep 3 [1..10]
Output:
[["iced","iced"],["iced","jam"],["iced","plain"],["jam","jam"],["jam","plain"],["plain","plain"]]
220

[edit] Dynamic Programming

The first solution is inefficient because it repeatedly calculates the same subproblem in different branches of recursion. For example, combsWithRep k (x:xs) involves computing combsWithRep (k-1) (x:xs) and combsWithRep k xs, both of which (separately) compute combsWithRep (k-1) xs. To avoid repeated computation, we can use dynamic programming:

combsWithRep :: Int -> [a] -> [[a]]
combsWithRep k xs = combsBySize xs !! k
where
combsBySize = foldr f ([[]] : repeat [])
f x next = scanl1 (\z n -> map (x:) z ++ n) next
 
main = do
print $ combsWithRep 2 ["iced","jam","plain"]
Output:
[["iced","iced"],["iced","jam"],["iced","plain"],["jam","jam"],["jam","plain"],["plain","plain"]]

[edit] Icon and Unicon

Following procedure is a generator, which generates each combination of length n in turn:

 
# 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
 

Test procedure:

 
# 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
 
Output:
plain plain 
jam plain 
jam jam 
iced plain 
iced jam 
iced iced 
There are 220 possible combinations of 3 from 10

[edit] J

rcomb=: >@~.@:(/:~&.>)@,@{@# <

Example use:

   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

[edit] Java

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

MultiCombinations.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
 
Output:
iced iced 
iced jam 
iced plain 
jam jam 
jam plain 
plain plain 
----------
The ways to choose 3 items from 10 with replacement = 220

[edit] JavaScript

<html><head><title>Donuts</title></head>
<body><pre id='x'></pre><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>
Output:
iced iced
iced jam
iced plain
jam jam
jam plain
plain plain
6 combos
pick 3 out of 10: 220 combos

[edit] jq

def pick(n):
def pick(n; m): # pick n, from m onwards
if n == 0 then []
elif m == length then empty
elif n == 1 then (.[m:][] | [.])
else ([.[m]] + pick(n-1; m)), pick(n; m+1)
end;
pick(n;0) ;

The task:

 "Pick 2:",
(["iced", "jam", "plain"] | pick(2)),
([[range(0;10)] | pick(3)] | length) as $n
| "There are \($n) ways to pick 3 objects with replacement from 10."
 
Output:
$ jq -n -r -c -f pick.jq
Pick 2:
["iced","iced"]
["iced","jam"]
["iced","plain"]
["jam","jam"]
["jam","plain"]
["plain","plain"]
There are 220 ways to pick 3 objects with replacement from 10.

[edit] Lua

function GenerateCombinations(tList, nMaxElements, tOutput, nStartIndex, nChosen, tCurrentCombination)
if not nStartIndex then
nStartIndex = 1
end
if not nChosen then
nChosen = 0
end
if not tOutput then
tOutput = {}
end
if not tCurrentCombination then
tCurrentCombination = {}
end
 
if nChosen == nMaxElements then
-- Must copy the table to avoid all elements referring to a single reference
local tCombination = {}
for k,v in pairs(tCurrentCombination) do
tCombination[k] = v
end
 
table.insert(tOutput, tCombination)
return
end
 
local nIndex = 1
for k,v in pairs(tList) do
if nIndex >= nStartIndex then
tCurrentCombination[nChosen + 1] = tList[nIndex]
GenerateCombinations(tList, nMaxElements, tOutput, nIndex, nChosen + 1, tCurrentCombination)
end
 
nIndex = nIndex + 1
end
 
return tOutput
end
 
tDonuts = {"iced", "jam", "plain"}
tCombinations = GenerateCombinations(tDonuts, #tDonuts)
for nCombination,tCombination in ipairs(tCombinations) do
print("Combination " .. tostring(nCombination))
for nIndex,strFlavor in ipairs(tCombination) do
print("+" .. strFlavor)
end
end
 

[edit] Mathematica

This method will only work for small set and sample sizes (as it generates all Tuples then filters duplicates - Length[Tuples[Range[10],10]] is already bigger than Mathematica can handle).

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
 


A better method therefore:

CombinWithRep[S_List, k_] := Module[{occupation, assignment},
occupation =
Flatten[Permutations /@
IntegerPartitions[k, {Length[S]}, Range[0, k]], 1];
assignment =
Flatten[Table[ConstantArray[z, {#[[z]]}], {z, Length[#]}]] & /@
occupation;
Thread[S[[#]]] & /@ assignment
]
 
In[2]:= CombinWithRep[{"iced", "jam", "plain"}, 2]
 
Out[2]= {{"iced", "iced"}, {"jam", "jam"}, {"plain",
"plain"}, {"iced", "jam"}, {"iced", "plain"}, {"jam", "plain"}}
 

Which can handle the Length[S] = 10, k=10 situation in still only seconds.

[edit] 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.

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

Usage:

:- 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).
Output:
[[iced, iced], [jam, jam], [plain, plain], [iced, jam], [iced, plain], [jam, plain]]
220 choices.

[edit] Nimrod

Translation of: D
import future, sequtils
 
proc combsReps[T](lst: seq[T], k: int): seq[seq[T]] =
if k == 0:
@[newSeq[T]()]
elif lst.len == 0:
@[]
else:
lst.combsReps(k - 1).map((x: seq[T]) => lst[0] & x) &
lst[1 .. -1].combsReps(k)
 
echo(@["iced", "jam", "plain"].combsReps(2))
echo toSeq(1..10).combsReps(3).len
Output:
@[@[iced, iced], @[iced, jam], @[iced, plain], @[jam, jam], @[jam, plain], @[plain, plain]]
220

[edit] OCaml

Translation of: Haskell
let rec combs_with_rep k xxs =
match k, xxs with
| 0, _ -> [[]]
| _, [] -> []
| k, x::xs ->
List.map (fun ys -> x::ys) (combs_with_rep (k-1) xxs)
@ combs_with_rep k xs

in the interactive loop:

# combs_with_rep 2 ["iced"; "jam"; "plain"] ;;
- : string list list =
[["iced"; "iced"]; ["iced"; "jam"]; ["iced"; "plain"]; ["jam"; "jam"];
 ["jam"; "plain"]; ["plain"; "plain"]]

# List.length (combs_with_rep 3 [1;2;3;4;5;6;7;8;9;10]) ;;
- : int = 220

[edit] Dynamic programming

let combs_with_rep m xs =
let arr = Array.make (m+1) [] in
arr.(0) <- [[]];
List.iter (fun x ->
for i = 1 to m do
arr.(i) <- arr.(i) @ List.map (fun xs -> x::xs) arr.(i-1)
done
) xs;
arr.(m)

in the interactive loop:

# combs_with_rep 2 ["iced"; "jam"; "plain"] ;;
- : string list list =
[["iced"; "iced"]; ["jam"; "iced"]; ["jam"; "jam"]; ["plain"; "iced"];
 ["plain"; "jam"]; ["plain"; "plain"]]

# List.length (combs_with_rep 3 [1;2;3;4;5;6;7;8;9;10]) ;;
- : int = 220

[edit] PARI/GP

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"])

[edit] Perl

The highly readable version:

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

Prints:

iced iced
iced jam
iced plain
jam jam
jam plain
plain plain

There are 11440 ways to pick 7 out of 10

With a module:

use Algorithm::Combinatorics qw/combinations_with_repetition/;
my $iter = combinations_with_repetition([qw/iced jam plain/], 2);
while (my $p = $iter->next) {
print "@$p\n";
}
# Not an efficient way: generates them all in an array!
my $count =()= combinations_with_repetition([1..10],7);
print "There are $count ways to pick 7 out of 10\n";

[edit] Perl 6

Translation of: Haskell
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 );
Output:
["iced", "iced"]
["iced", "jam"]
["iced", "plain"]
["jam", "jam"]
["jam", "plain"]
["plain", "plain"]
220

[edit] PHP

<?php
function combos($arr, $k) {
if ($k == 0) {
return array(array());
}
 
if (count($arr) == 0) {
return array();
}
 
$head = $arr[0];
 
$combos = array();
$subcombos = combos($arr, $k-1);
foreach ($subcombos as $subcombo) {
array_unshift($subcombo, $head);
$combos[] = $subcombo;
}
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) {
echo implode(' ', $combo), "<br>";
}
$donuts = range(1, 10);
$num_donut_combos = count(combos($donuts, 3));
echo "$num_donut_combos ways to order 3 donuts given 10 types";
?>
Output:
in the browser:
iced iced
iced jam
iced plain
jam jam
jam plain
plain plain
220 ways to order 3 donuts given 10 types

[edit] 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)) ) ) ) )
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

[edit] 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
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.
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

[edit] 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
>>>

References:

[edit] Racket

 
#lang racket
(define (combinations xs k)
(cond [(= k 0) '(())]
[(empty? xs) '()]
[(append (combinations (rest xs) k)
(map (λ(x) (cons (first xs) x))
(combinations xs (- k 1))))]))
 

[edit] REXX

/*REXX program shows combination sets for  X  things taken  Y  at a time*/
parse arg x y symbols .; if x=='' | x==',' then x=3
if y=='' | y==',' then y=2
if symbols=='' then symbols='iced jam plain' /*symbol table words.*/
 
say "────────────" abs(x) 'doughnut selection taken' y "at a time:"
say "────────────" RcombN(x,y) 'combinations.'; if x\=='' then exit #
say
x= -10 /*indicate that the combinations aren't to be shown.*/
y= 3
say "────────────" abs(x) 'doughnut selection choose' y "at a time:"
say "────────────" RcombN(x,y) 'combinations.'
exit /*stick a fork in it, we're done.*/
/*─────────────────────────────────────RCOMBN subroutine────────────────*/
RcombN: procedure expose # symbols; parse arg x 1 ox,y; x=abs(x); base=x
!.=1
do #=1; if ox>0 then do; L=; do d=1 for y while ox>0
L=L word(symbols,!.d)
end /*d*/ ; say L
end
 !.y=!.y+1; if !.y==base then if .RcombN(y-1) then leave
end /*#*/
return #
/*─────────────────────────────────────.RCOMBN subroutine───────────────*/
.RcombN: procedure expose !. y base; parse arg d; if d==0 then return 1
p=!.d+1; if p==base then return .RcombN(d-1)
do u=d to y
 !.u=p
end /*u*/
return 0
Output:
using the defaults for input:
──────────── 3 doughnut selection taken 2 at a time:
 iced iced
 iced jam
 iced plain
 jam jam
 jam plain
 plain plain
──────────── 6 combinations.

──────────── 10 doughnut selection choose 3 at a time:
──────────── 220 combinations.

[edit] Ruby

Works with: Ruby version 1.9.2
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 ')}
 
# Extra credit
possible_doughnuts = [*1..10].repeated_combination(3)
puts "", "#{possible_doughnuts.count} ways to order 3 donuts given 10 types"
Output:
There are 6 possible doughnuts:
iced and iced
iced and jam
iced and plain
jam and jam
jam and plain
plain and plain

220 ways to order 3 donuts given 10 types

[edit] Scala

Scala has a combinations method in the standard library.

 
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")
}
}
 
Output:
iced,iced
iced,jam
iced,plain
jam,jam
jam,plain
plain,plain
There are 220 ways to choose 3 items from 10 choices

[edit] Scheme

Translation of: PicoLisp
(define (combs-with-rep k lst)
(cond ((= k 0) '(()))
((null? lst) '())
(else
(append
(map
(lambda (x)
(cons (car lst) x))
(combs-with-rep (- k 1) lst))
(combs-with-rep k (cdr lst))))))
 
(display (combs-with-rep 2 (list "iced" "jam" "plain"))) (newline)
(display (length (combs-with-rep 3 '(1 2 3 4 5 6 7 8 9 10)))) (newline)
Output:
((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))
220

[edit] Dynamic programming

(define (combs-with-rep m lst)
(define arr (make-vector (+ m 1) '()))
(vector-set! arr 0 '(()))
(for-each (lambda (x)
(do ((i 1 (+ i 1)))
((> i m))
(vector-set! arr i (append (vector-ref arr i)
(map (lambda (xs) (cons x xs))
(vector-ref arr (- i 1)))))
)
) lst)
(vector-ref arr m))
 
(display (combs-with-rep 2 (list "iced" "jam" "plain"))) (newline)
(display (length (combs-with-rep 3 '(1 2 3 4 5 6 7 8 9 10)))) (newline)
Output:
((iced iced) (jam iced) (jam jam) (plain iced) (plain jam) (plain plain))
220

[edit] Standard ML

Translation of: Haskell
let rec combs_with_rep k xxs =
match k, xxs with
| 0, _ -> [[]]
| _, [] -> []
| k, x::xs ->
List.map (fun ys -> x::ys) (combs_with_rep (k-1) xxs)
@ combs_with_rep k xs

in the interactive loop:

- combs_with_rep (2, ["iced", "jam", "plain"]) ;
val it =
  [["iced","iced"],["iced","jam"],["iced","plain"],["jam","jam"],
   ["jam","plain"],["plain","plain"]] : string list list
- length (combs_with_rep (3, [1,2,3,4,5,6,7,8,9,10])) ;
val it = 220 : int

[edit] Dynamic programming

fun combs_with_rep (m, xs) = let
val arr = Array.array (m+1, [])
in
Array.update (arr, 0, [[]]);
app (fn x =>
Array.modifyi (fn (i, y) =>
if i = 0 then y else y @ map (fn xs => x::xs) (Array.sub (arr, i-1))
) arr
) xs;
Array.sub (arr, m)
end

in the interactive loop:

- combs_with_rep (2, ["iced", "jam", "plain"]) ;
val it =
  [["iced","iced"],["jam","iced"],["jam","jam"],["plain","iced"],
   ["plain","jam"],["plain","plain"]] : string list list
- length (combs_with_rep (3, [1,2,3,4,5,6,7,8,9,10])) ;
val it = 220 : int

[edit] 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]]
Output:
{iced iced} {iced jam} {iced plain} {jam jam} {jam plain} {plain plain}
220

[edit] 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)
Output:
(
   {
      <'iced','iced'>,
      <'iced','jam'>,
      <'iced','plain'>,
      <'jam','jam'>,
      <'jam','plain'>,
      <'plain','plain'>},
   220)

[edit] XPL0

code ChOut=8, CrLf=9, IntOut=11, Text=12;
int Count, Array(10);
 
proc Combos(D, S, K, N, Names); \Generate all size K combinations of N objects
int D, S, K, N, Names; \depth of recursion, starting value of N, etc.
int I;
[if D<K then \depth < size
[for I:= S to N-1 do
[Array(D):= I;
Combos(D+1, I, K, N, Names);
];
]
else [Count:= Count+1;
if Names(0) then
[for I:= 0 to K-1 do
[Text(0, Names(Array(I))); ChOut(0, ^ )];
CrLf(0);
];
];
];
 
[Count:= 0;
Combos(0, 0, 2, 3, ["iced", "jam", "plain"]);
Text(0, "Combos = "); IntOut(0, Count); CrLf(0);
Count:= 0;
Combos(0, 0, 3, 10, [0]);
Text(0, "Combos = "); IntOut(0, Count); CrLf(0);
]
Output:
iced iced 
iced jam 
iced plain 
jam jam 
jam plain 
plain plain 
Combos = 6
Combos = 220

[edit] zkl

Translation of: Clojure
fcn combosK(k,seq){	// repeats, seq is finite
if (k==1) return(seq);
if (not seq) return(T);
self.fcn(k-1,seq).apply(T.extend.fp(seq[0])).extend(self.fcn(k,seq[1,*]));
}
combosK(2,T("iced","jam","plain")).apply("concat",",");
combosK(3,T(0,1,2,3,4,5,6,7,8,9)).len();
Output:
L("iced,iced","iced,jam","iced,plain","jam,jam","jam,plain","plain,plain")
220
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox