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: {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
- 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
- See also
The number of samples of size k from n objects.
With combinations and permutations generation tasks.
Order Unimportant Order Important Without replacement Task: Combinations Task: Permutations With replacement Task: Combinations with repetitions Task: Permutations with repetitions
360 Assembly
<lang 360asm>* Combinations with repetitions - 16/04/2019 COMBREP CSECT
USING COMBREP,R13 base register B 72(R15) skip savearea DC 17F'0' savearea SAVE (14,12) save previous context ST R13,4(R15) link backward ST R15,8(R13) link forward LR R13,R15 set addressability MVC FLAVORS(9),SET1 flavors=3,draws=2,tell=1 BAL R14,COMBINE call combine MVC FLAVORS(9),SET2 flavors=10,draws=3,tell=0 BAL R14,COMBINE call combine L R13,4(0,R13) restore previous savearea pointer RETURN (14,12),RC=0 restore registers from calling sav
COMBINE SR R9,R9 n=0
MVI V,X'00' ~ MVC V+1(NN*L'V-1),V v=0 IF CLI,TELL,EQ,X'01' THEN if tell then XPRNT =C'list:',5 print ENDIF , endif
LOOP LA R6,1 i=1
DO WHILE=(C,R6,LE,DRAWS) do i=1 to draws LR R1,R6 i SLA R1,2 ~ L R2,V-4(R1) v(i) L R3,FLAVORS flavors BCTR R3,0 flavors-1 IF CR,R2,GT,R3 THEN if v(i)>flavors-1 then LR R1,R6 i SLA R1,2 ~ LA R1,V(R1) @v(i+1) L R2,0(R1) v(i+1) LA R2,1(R2) v(i+1)+1 ST R2,0(R1) v(i+1)=v(i+1)+1 LR R7,R6 j=i DO WHILE=(C,R7,GE,=A(1)) do j=i to 1 by -1 LR R1,R6 i SLA R1,2 ~ L R2,V(R1) v(i+1) LR R1,R7 j SLA R1,2 ~ ST R2,V-4(R1) v(j)=v(i+1) BCTR R7,0 j-- ENDDO , enddo j ENDIF , endif LA R6,1(R6) i++ ENDDO , enddo i L R1,DRAWS draws LA R1,1(R1) draws+1 SLA R1,2 ~ L R2,V-4(R1) v(draws+1) LTR R2,R2 if v(draws+1)>0 BP EXITLOOP then exit loop LA R9,1(R9) n=n+1 IF CLI,TELL,EQ,X'01' THEN if tell then MVC BUF,=CL60' ' buf=' ' LA R10,1 ibuf=1 LA R6,1 i=1 DO WHILE=(C,R6,LE,DRAWS) do i=1 to draws LR R1,R6 i SLA R1,2 ~ L R1,V-4(R1) v(i) MH R1,=AL2(L'ITEMS) ~ LA R4,ITEMS(R1) @items(v(i)+1) LA R5,BUF-1 @buf-1 AR R5,R10 +ibuf MVC 0(6,R5),0(R4) substr(buf,ibuf,6)=items(v(i)+1) LA R10,L'ITEMS(R10) ibuf=ibuf+length(items) LA R6,1(R6) i++ ENDDO , enddo i XPRNT BUF,L'BUF print buf ENDIF , endif L R2,V v(1) LA R2,1(R2) v(1)+1 ST R2,V v(1)=v(1)+1 B LOOP loop
EXITLOOP L R1,FLAVORS flavors
XDECO R1,XDEC edit flavors MVC PG+4(2),XDEC+10 output flavors L R1,DRAWS draws XDECO R1,XDEC edit draws MVC PG+7(2),XDEC+10 output draws XDECO R9,PG+11 edit & output n XPRNT PG,L'PG print buffer BR R14 return
NN EQU 16 ITEMS DC CL6'iced',CL6'jam',CL6'plain' FLAVORS DS F DRAWS DS F TELL DS X SET1 DC F'3',F'2',X'01' flavors=3,draws=2,tell=1 SET2 DC F'10',F'3',X'00' flavors=10,draws=3,tell=0 V DS (NN)F v(nn) BUF DS CL60 buf PG DC CL40'cwr(..,..)=............' XDEC DS CL12 temp for xdeco
REGEQU END COMBREP </lang>
- Output:
list: iced iced jam iced plain iced jam jam plain jam plain plain cwr( 3, 2)= 6 cwr(10, 3)= 220
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
AppleScript
<lang applescript>-- combsWithRep :: Int -> [a] -> [kTuple a] on combsWithRep(k, xs)
-- A list of lists, representing -- sets of cardinality k, with -- members drawn from xs. script combsBySize script f on |λ|(a, x) script prefix on |λ|(z) {x} & z end |λ| end script script go on |λ|(ys, xs) xs & map(prefix, ys) end |λ| end script scanl1(go, a) end |λ| end script on |λ|(xs) foldl(f, {{{}}} & take(k, |repeat|({})), xs) end |λ| end script |Just| of |index|(|λ|(xs) of combsBySize, 1 + k)
end combsWithRep
-- TEST ---------------------------------------------------
on run
{length of combsWithRep(3, enumFromTo(0, 9)), ¬ combsWithRep(2, {"iced", "jam", "plain"})}
end run
-- GENERIC ------------------------------------------------
-- Just :: a -> Maybe a on Just(x)
{type:"Maybe", Nothing:false, Just:x}
end Just
-- Nothing :: Maybe a on Nothing()
{type:"Maybe", Nothing:true}
end Nothing
-- enumFromTo :: (Int, Int) -> [Int] on enumFromTo(m, n)
if m ≤ n then set lst to {} repeat with i from m to n set end of lst to i end repeat return lst else return {} end if
end enumFromTo
-- foldl :: (a -> b -> a) -> a -> [b] -> a on foldl(f, startValue, xs)
tell mReturn(f) set v to startValue set lng to length of xs repeat with i from 1 to lng set v to |λ|(v, item i of xs, i, xs) end repeat return v end tell
end foldl
-- index (!!) :: [a] -> Int -> Maybe a -- index (!!) :: Gen [a] -> Int -> Maybe a -- index (!!) :: String -> Int -> Maybe Char on |index|(xs, i)
if script is class of xs then repeat with j from 1 to i set v to |λ|() of xs end repeat if missing value is not v then Just(v) else Nothing() end if else if length of xs < i then Nothing() else Just(item i of xs) end if end if
end |index|
-- map :: (a -> b) -> [a] -> [b] on map(f, xs)
tell mReturn(f) set lng to length of xs set lst to {} repeat with i from 1 to lng set end of lst to |λ|(item i of xs, i, xs) end repeat return lst end tell
end map
-- min :: Ord a => a -> a -> a on min(x, y)
if y < x then y else x end if
end min
-- Lift 2nd class handler function into 1st class script wrapper -- mReturn :: First-class m => (a -> b) -> m (a -> b) on mReturn(f)
if script is class of f then f else script property |λ| : f end script end if
end mReturn
-- repeat :: a -> Generator [a] on |repeat|(x)
script on |λ|() return x end |λ| end script
end |repeat|
-- scanl :: (b -> a -> b) -> b -> [a] -> [b]
on scanl(f, startValue, xs)
tell mReturn(f) set v to startValue set lng to length of xs set lst to {startValue} repeat with i from 1 to lng set v to |λ|(v, item i of xs, i, xs) set end of lst to v end repeat return lst end tell
end scanl
-- scanl1 :: (a -> a -> a) -> [a] -> [a] on scanl1(f, xs)
if 0 < length of xs then scanl(f, item 1 of xs, rest of xs) else {} end if
end scanl1
-- take :: Int -> [a] -> [a]
-- take :: Int -> String -> String
on take(n, xs)
set c to class of xs if list is c then if 0 < n then items 1 thru min(n, length of xs) of xs else {} end if else if string is c then if 0 < n then text 1 thru min(n, length of xs) of xs else "" end if else if script is c then set ys to {} repeat with i from 1 to n set v to |λ|() of xs if missing value is v then return ys else set end of ys to v end if end repeat return ys else missing value end if
end take</lang>
- Output:
{220, {{"iced", "iced"}, {"jam", "iced"}, {"jam", "jam"}, {"plain", "iced"}, {"plain", "jam"}, {"plain", "plain"}}}
AutoHotkey
<lang AutoHotkey>;===========================================================
- based on "https://www.geeksforgeeks.org/combinations-with-repetitions/"
- ===========================================================
CombinationRepetition(arr, k:=0, Delim:="") { CombinationRepetitionUtil(arr, k?k:str.count(), Delim, [k+1], result:=[]) return result } ;=========================================================== CombinationRepetitionUtil(arr, k, Delim, chosen, result , index:=1, start:=1){ line := [], i:=0, res := "" if (index = k+1){ while (++i <= k) res .= arr[chosen[i]] Delim, line.push(arr[chosen[i]]) return result.Push(Trim(res, Delim)) } i:=start while (i <= arr.count()) chosen[Index]:=i, CombinationRepetitionUtil(arr, k, Delim, chosen, result, index+1, i++) } ;===========================================================</lang> Examples:<lang AutoHotkey>result := CombinationRepetition(["iced","jam","plain"], 2, " + ") for k, v in result res .= v "`n" res := trim(res, ",") "`n" MsgBox % result.count() " Combinations with Repetition found:`n" res MsgBox % CombinationRepetition([0,1,2,3,4,5,6,7,8,9], 3).Count()</lang>
Outputs:
--------------------------- 6 Combinations with Repetition found: iced + iced iced + jam iced + plain jam + jam jam + plain plain + plain --------------------------- 220 ---------------------------
AWK
<lang AWK>
- syntax: GAWK -f COMBINATIONS_WITH_REPETITIONS.AWK
BEGIN {
n = split("iced,jam,plain",donuts,",") for (i=1; i<=n; i++) { for (j=1; j<=n; j++) { if (donuts[i] < donuts[j]) { key = sprintf("%s %s",donuts[i],donuts[j]) } else { key = sprintf("%s %s",donuts[j],donuts[i]) } arr[key]++ } } cmd = "SORT" for (i in arr) { printf("%s\n",i) | cmd choices++ } close(cmd) printf("choices = %d\n",choices) exit(0)
} </lang>
output:
iced iced iced jam iced plain jam jam jam plain plain plain choices = 6
BBC BASIC
<lang bbcbasic> 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%</lang>
- 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
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.
<lang bracmat>( ( 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) );</lang>
- Output:
iced^2+jam^2+plain^2+iced*jam+iced*plain+jam*plain 220
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 icediced jam iced plain jam jam jam plain plain plain
Were there ten donuts, we'd have had 220 choices of three
C#
<lang csharp> using System; using System.Collections.Generic; using System.Linq;
public static class MultiCombinations {
private static void Main() { var set = new List<string> { "iced", "jam", "plain" }; var combinations = GenerateCombinations(set, 2);
foreach (var combination in combinations) { string combinationStr = string.Join(" ", combination); Console.WriteLine(combinationStr); }
var donuts = Enumerable.Range(1, 10).ToList();
int donutsCombinationsNumber = GenerateCombinations(donuts, 3).Count;
Console.WriteLine("{0} ways to order 3 donuts given 10 types", donutsCombinationsNumber); } private static List<List<T>> GenerateCombinations<T>(List<T> combinationList, int k) { var combinations = new List<List<T>>();
if (k == 0) { var emptyCombination = new List<T>(); combinations.Add(emptyCombination);
return combinations; }
if (combinationList.Count == 0) { return combinations; }
T head = combinationList[0]; var copiedCombinationList = new List<T>(combinationList); List<List<T>> subcombinations = GenerateCombinations(copiedCombinationList, k - 1);
foreach (var subcombination in subcombinations) { subcombination.Insert(0, head); combinations.Add(subcombination); }
combinationList.RemoveAt(0); combinations.AddRange(GenerateCombinations(combinationList, k));
return combinations; }
} </lang>
- Output:
iced iced iced jam iced plain jam jam jam plain plain plain 220 ways to order 3 donuts given 10 types
Recursive version <lang csharp> using System; class MultiCombination {
static string [] set = { "iced", "jam", "plain" }; static int k = 2, n = set.Length; static string [] buf = new string [k];
static void Main() { rec(0, 0); }
static void rec(int ind, int begin) { for (int i = begin; i < n; i++) { buf [ind] = set[i]; if (ind + 1 < k) rec(ind + 1, i); else Console.WriteLine(string.Join(",", buf)); } }
}
</lang>
C++
Non recursive version. <lang cpp>
- include <cstdio>
- include <vector>
- include <string>
using namespace std;
void print_vector(const vector<int> &v, size_t n, const vector<string> &s){
for (size_t i = 0; i < n; ++i) printf("%s\t", s[v[i]].c_str()); printf("\n");
}
void combination_with_repetiton(int sabores, int bolas, const vector<string>& v_sabores){
sabores--; vector<int> v(bolas+1, 0); while (true){ for (int i = 0; i < bolas; ++i){ //vai um if (v[i] > sabores){ v[i + 1] += 1; for (int k = i; k >= 0; --k){ v[k] = v[i + 1]; } //v[i] = v[i + 1]; } } if (v[bolas] > 0) break; print_vector(v, bolas, v_sabores); v[0] += 1; }
}
int main(){
vector<string> options{ "iced", "jam", "plain" }; combination_with_repetiton(3, 2, options); return 0;
} </lang>
- Output:
iced iced jam iced plain iced jam jam plain jam plain plain
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>
- Output:
user> (combinations '[iced jam plain] 2) ((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))
CoffeeScript
<lang 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" </lang>
- Output:
jam,plain: [ [ 'iced', 'iced' ], [ 'iced', 'jam' ], [ 'iced', 'plain' ], [ 'jam', 'jam' ], [ 'jam', 'plain' ], [ 'plain', 'plain' ] ] 220 ways to order 3 donuts given 10 types
Common Lisp
The code below is a modified version of the Clojure solution. <lang lisp>(defun combinations (xs k)
(let ((x (car xs))) (cond ((null xs) nil) ((= k 1) (mapcar #'list xs)) (t (append (mapcar (lambda (ys) (cons x ys))
(combinations xs (1- k))) (combinations (cdr xs) k)))))) </lang>
- Output:
((:ICED :ICED) (:ICED :JAM) (:ICED :PLAIN) (:JAM :JAM) (:JAM :PLAIN) (:PLAIN :PLAIN))
Crystal
<lang ruby>possible_doughnuts = ["iced", "jam", "plain"].repeated_combinations(2) puts "There are #{possible_doughnuts.size} possible doughnuts:" possible_doughnuts.each{|doughnut_combi| puts doughnut_combi.join(" and ")}
- Extra credit
possible_doughnuts = (1..10).to_a.repeated_combinations(3)
- size returns the size of the enumerator, or nil if it can’t be calculated lazily.
puts "", "#{possible_doughnuts.size} ways to order 3 donuts given 10 types."</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 220 ways to order 3 donuts given 10 types.
D
Using lexicographic next bit permutation to generate combinations with repetitions. <lang d>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 @safe 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 @safe { return combVal.length; }
uint[] opIndex(in uint idx) const pure nothrow @safe { return val2set(combVal[idx]); }
int opApply(immutable int delegate(in ref uint[]) pure nothrow @safe dg) pure nothrow @safe { foreach (immutable v; combVal) { auto set = val2set(v); if (dg(set)) break; } return 1; }
private uint[] val2set(in ulong v) const pure nothrow @safe { // 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 @safe 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() @safe {
foreach (const e; combRep(["iced", "jam", "plain"], 2)) writefln("%-(%5s %)", 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
Short Recursive Version
<lang d>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;
}</lang>
- Output:
[["iced", "iced"], ["iced", "jam"], ["iced", "plain"], ["jam", "jam"], ["jam", "plain"], ["plain", "plain"]] 220
EasyLang
<lang>items$[] = [ "iced" "jam" "plain" ] n = len items$[] k = 2 len result[] k n_results = 0
func output . .
n_results += 1 if len items$[] > 0 s$ = "" for i range k s$ &= items$[result[i]] & " " . print s$ .
. func combine pos val . .
if pos = k call output else for i = val to n - 1 result[pos] = i call combine pos + 1 i . .
. call combine 0 0
n = 10 k = 3 len result[] k items$[] = [ ] n_results = 0 call combine 0 0 print "" print n_results & " results with 10 donuts"</lang>
- Output:
iced iced iced jam iced plain jam jam jam plain plain plain 220 results with 10 donuts
EchoLisp
We can use the native combinations/rep function, or use a combinator iterator, or implement the function. <lang scheme>
- native function
- combinations/rep in list.lib
(lib 'list)
(combinations/rep '(iced jam plain) 2)
→ ((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))
- using a combinator iterator
(lib 'sequences)
(take (combinator/rep '(iced jam plain) 2) 8)
→ ((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))
- or, implementing the function
(define (comb/rep nums k) (cond [(null? nums) null] [(<= k 0) null] [(= k 1) (map list nums)] [else (for/fold (acc null) ((anum nums)) (append acc (for/list ((xs (comb/rep nums (1- k)))) #:continue (< (first xs) anum) (cons anum xs))))]))
(map (curry list-permute '(iced jam plain)) (comb/rep (iota 3) 2))
→ ((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))
- extra credit
(length (combinator/rep (iota 10) 3))
→ 220
</lang>
Egison
<lang 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"})) </lang>
- Output:
{[|"iced" "iced"|] [|"iced" "jam"|] [|"jam" "jam"|] [|"iced" "plain"|] [|"jam" "plain"|] [|"plain" "plain"|]}
Elixir
<lang elixir>defmodule RC do
def comb_rep(0, _), do: [[]] def comb_rep(_, []), do: [] def comb_rep(n, [h|t]=s) do (for l <- comb_rep(n-1, s), do: [h|l]) ++ comb_rep(n, t) end
end
s = [:iced, :jam, :plain] Enum.each(RC.comb_rep(2, s), fn x -> IO.inspect x end)
IO.puts "\nExtra credit: #{length(RC.comb_rep(3, Enum.to_list(1..10)))}"</lang>
- Output:
[:iced, :iced] [:iced, :jam] [:iced, :plain] [:jam, :jam] [:jam, :plain] [:plain, :plain] Extra credit: 220
Erlang
<lang 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).
</lang>
- 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
Fortran
<lang 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 </lang>
- Output:
iced iced iced jam iced plain jam jam jam plain plain plain Total = 6
FreeBASIC
<lang freebasic>sub iterate( byval curr as string, byval start as uinteger,_
byval stp as uinteger, byval depth as uinteger,_ names() as string ) dim as uinteger i for i = start to stp if depth = 0 then print curr + " " + names(i) else iterate curr+" "+names(i), i, stp, depth-1, names() end if next i return
end sub
dim as uinteger m, n, o, i input "Enter n comb m. ", n, m dim as string outstr = "" dim as string names(0 to m-1) for i = 0 to m - 1
print "Name for item ",+i input names(i)
next i iterate outstr, 0, m-1, n-1, names()</lang>
- Output:
Enter n comb m. 2,3 Name for item 0 ? Iced Name for item 1 ? Jam Name for item 2 ? Plain Iced Iced Iced Jam Iced Plain Jam Jam Jam Plain Plain Plain
GAP
<lang gap># Built-in UnorderedTuples(["iced", "jam", "plain"], 2);</lang>
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>-- 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) =
(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 :: Int -> [a] -> Int countCombsWithRep k lst = binomial (k - 1 + length lst) k
-- countCombsWithRep k = length . combsWithRep k main :: IO () main = do
print $ combsWithRep 2 ["iced", "jam", "plain"] print $ countCombsWithRep 3 [1 .. 10]</lang>
- Output:
[["iced","iced"],["iced","jam"],["iced","plain"],["jam","jam"],["jam","plain"],["plain","plain"]] 220
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:
<lang haskell>combsWithRep :: Int -> [a] -> a combsWithRep k xs = combsBySize xs !! k
where combsBySize = foldr f ([[]] : repeat []) f x = scanl1 $ (++) . map (x :)
main :: IO () main = print $ combsWithRep 2 ["iced", "jam", "plain"]</lang>
and another approach, using manual recursion: <lang haskell>combsWithRep
:: (Eq a) => Int -> [a] -> a
combsWithRep k xs = comb k []
where comb 0 ys = ys comb n [] = comb (pred n) (pure <$> xs) comb n peers = comb (pred n) (peers >>= nextLayer) where nextLayer ys@(h:_) = (: ys) <$> dropWhile (/= h) xs
main :: IO () main = do
print $ combsWithRep 2 ["iced", "jam", "plain"] print $ length $ combsWithRep 3 [0 .. 9]</lang>
- Output:
[["iced","iced"],["jam","iced"],["plain","iced"],["jam","jam"],["plain","jam"],["plain","plain"]] 220
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
IS-BASIC
<lang IS-BASIC>100 PROGRAM "Combinat.bas" 110 READ N 120 STRING D$(1 TO N)*5 130 FOR I=1 TO N 140 READ D$(I) 150 NEXT 160 FOR I=1 TO N 170 FOR J=I TO N 180 PRINT D$(I);" ";D$(J) 190 NEXT 200 NEXT 210 DATA 3,iced,jam,plain</lang>
J
Cartesian product, the monadic j verb { solves the problem. The rest of the code handles the various data types, order, and quantity to choose, and makes a set from the result.
<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 repetitions
220</lang>
J Alternate implementation
Considerably faster:
<lang j>require 'stats' combr=: i.@[ -"1~ [ comb + - 1: rcomb=: (combr #) { ]</lang>
rcomb
functions identically, and combr
calculates indices:
<lang j> 2 combr 3 0 0 0 1 0 2 1 1 1 2 2 2</lang>
In other words: we compute 2 comb 4
(note that 4 = (2 + 3)-1) and then subtract from each column the minimum value in each column (i. 2).
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
ES5
Imperative
<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:
iced iced iced jam iced plain jam jam jam plain plain plain 6 combos pick 3 out of 10: 220 combos
Functional
<lang JavaScript>(function () {
// n -> [a] -> a function combsWithRep(n, lst) { return n ? ( lst.length ? combsWithRep(n - 1, lst).map(function (t) { return [lst[0]].concat(t); }).concat(combsWithRep(n, lst.slice(1))) : [] ) : [[]]; };
// If needed, we can derive a significantly faster version of // the simple recursive function above by memoizing it
// f -> f function memoized(fn) { m = {}; return function (x) { var args = [].slice.call(arguments), strKey = args.join('-');
v = m[strKey]; if ('u' === (typeof v)[0]) m[strKey] = v = fn.apply(null, args); return v; } }
// [m..n] function range(m, n) { return Array.apply(null, Array(n - m + 1)).map(function (x, i) { return m + i; }); }
return [
combsWithRep(2, ["iced", "jam", "plain"]),
// obtaining and applying a memoized version of the function memoized(combsWithRep)(3, range(1, 10)).length ];
})();</lang>
- Output:
<lang JavaScript>[
[["iced", "iced"], ["iced", "jam"], ["iced", "plain"], ["jam", "jam"], ["jam", "plain"], ["plain", "plain"]], 220
]</lang>
ES6
<lang JavaScript>(() => {
'use strict';
// COMBINATIONS WITH REPETITIONS -------------------------------------------
// combsWithRep :: Int -> [a] -> a const combsWithRep = (k, xs) => { const comb = (n, ys) => { if (0 === n) return ys; if (isNull(ys)) return comb(n - 1, map(pure, xs));
return comb(n - 1, concatMap(zs => { const h = head(zs); return map(x => [x].concat(zs), dropWhile(x => x !== h, xs)); }, ys)); }; return comb(k, []); };
// GENERIC FUNCTIONS ------------------------------------------------------
// concatMap :: (a -> [b]) -> [a] -> [b] const concatMap = (f, xs) => [].concat.apply([], xs.map(f));
// dropWhile :: (a -> Bool) -> [a] -> [a] const dropWhile = (p, xs) => { let i = 0; for (let lng = xs.length; (i < lng) && p(xs[i]); i++) {} return xs.slice(i); };
// enumFromTo :: Int -> Int -> [Int] const enumFromTo = (m, n) => Array.from({ length: Math.floor(n - m) + 1 }, (_, i) => m + i);
// head :: [a] -> Maybe a const head = xs => xs.length ? xs[0] : undefined;
// isNull :: [a] -> Bool const isNull = xs => (xs instanceof Array) ? xs.length < 1 : undefined;
// length :: [a] -> Int const length = xs => xs.length;
// map :: (a -> b) -> [a] -> [b] const map = (f, xs) => xs.map(f);
// pure :: a -> [a] const pure = x => [x];
// show :: a -> String const show = x => JSON.stringify(x, null, 2);
// TEST ------------------------------------------------------------------- return show({ twoFromThree: combsWithRep(2, ['iced', 'jam', 'plain']), threeFromTen: length(combsWithRep(3, enumFromTo(0, 9))) });
})();</lang>
- Output:
{ "twoFromThree": [ [ "iced", "iced" ], [ "jam", "iced" ], [ "plain", "iced" ], [ "jam", "jam" ], [ "plain", "jam" ], [ "plain", "plain" ] ], "threeFromTen": 220 }
jq
<lang 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) ;</lang>
The task: <lang jq> "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."
</lang>
- 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.
Julia
<lang julia>using Combinatorics
l = ["iced", "jam", "plain"] println("List: ", l, "\nCombinations:") for c in with_replacement_combinations(l, 2)
println(c)
end
@show length(with_replacement_combinations(1:10, 3))</lang>
- Output:
List: String["iced", "jam", "plain"] Combinations: String["iced", "iced"] String["iced", "jam"] String["iced", "plain"] String["jam", "jam"] String["jam", "plain"] String["plain", "plain"] length(with_replacement_combinations(1:10, 3)) = 220
Kotlin
<lang scala>// version 1.0.6
class CombsWithReps<T>(val m: Int, val n: Int, val items: List<T>, val countOnly: Boolean = false) {
private val combination = IntArray(m) private var count = 0
init { generate(0) if (!countOnly) println() println("There are $count combinations of $n things taken $m at a time, with repetitions") }
private fun generate(k: Int) { if (k >= m) { if (!countOnly) { for (i in 0 until m) print("${items[combination[i]]}\t") println() } count++ } else { for (j in 0 until n) if (k == 0 || j >= combination[k - 1]) { combination[k] = j generate(k + 1) } } }
}
fun main(args: Array<String>) {
val doughnuts = listOf("iced", "jam", "plain") CombsWithReps(2, 3, doughnuts) println() val generic10 = "0123456789".chunked(1) CombsWithReps(3, 10, generic10, true)
}</lang>
- Output:
iced iced iced jam iced plain jam jam jam plain plain plain There are 6 combinations of 3 things taken 2 at a time, with repetitions There are 220 combinations of 10 things taken 3 at a time, with repetitions
LFE
and
With List Comprehension
<lang lisp> (defun combinations
(('() _) '()) ((coll 1) (lists:map #'list/1 coll)) (((= (cons head tail) coll) n) (++ (lc ((<- subcoll (combinations coll (- n 1)))) (cons head subcoll)) (combinations tail n))))
</lang>
With Map
<lang lisp> (defun combinations
(('() _) '()) ((coll 1) (lists:map #'list/1 coll)) (((= (cons head tail) coll) n) (++ (lists:map (lambda (subcoll) (cons head subcoll)) (combinations coll (- n 1))) (combinations tail n))))
</lang>
Output is the same for both:
<lang lisp> > (combinations '(iced jam plain) 2) ((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain)) </lang>
Lobster
<lang Lobster>import std
// set S of length n, choose k
def choose(s, k, f):
let got = map(k): s[0] let n = s.length
def choosi(n_chosen, at): var count = 0 if n_chosen == k: f(got) return 1 var i = at while i < n: got[n_chosen] = s[i] count += choosi(n_chosen + 1, i) i += 1 return count return choosi(0, 0)
let count = choose(["iced", "jam", "plain"], 2): print(_) print count let extra = choose(map(10):_, 3): _ print extra</lang>
- Output:
["iced", "iced"] ["iced", "jam"] ["iced", "plain"] ["jam", "jam"] ["jam", "plain"] ["plain", "plain"] 6 220
Lua
<lang 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 </lang>
Maple
<lang maple>with(combinat): chooserep:=(s,k)->choose([seq(op(s),i=1..k)],k): chooserep({iced,jam,plain},2);
- [[iced, iced], [iced, jam], [iced, plain], [jam, jam], [jam, plain], [plain, plain]]
numbchooserep:=(s,k)->binomial(nops(s)+k-1,k); numbchooserep({iced,jam,plain},2);
- 6</lang>
Mathematica / Wolfram Language
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). <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>
A better method therefore:
<lang Mathematica>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"}}
</lang>
Which can handle the Length[S] = 10, k=10 situation in still only seconds.
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.
Nim
<lang nim>import sugar, 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</lang>
- Output:
@[@[iced, iced], @[iced, jam], @[iced, plain], @[jam, jam], @[jam, plain], @[plain, plain]] 220
OCaml
<lang ocaml>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</lang>
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
Dynamic programming
<lang ocaml>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)</lang>
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
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
With a module: <lang perl>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";</lang>
Phix
with javascript_semantics procedure show_choices(sequence set, integer n, at=1, sequence res={}) if length(res)=n then ?res else for i=at to length(set) do show_choices(set,n,i,append(deep_copy(res),set[i])) end for end if end procedure show_choices({"iced","jam","plain"},2)
- Output:
{"iced","iced"} {"iced","jam"} {"iced","plain"} {"jam","jam"} {"jam","plain"} {"plain","plain"}
The second part suggests enough differences (collecting and showing vs only counting) to strike me as ugly and confusing. While I could easily, say, translate the C version, I'd rather forego the extra credit and use a completely different routine:
with javascript_semantics function count_choices(integer set_size, n, at=1, taken=0) integer count = 0 if taken=n then return 1 end if taken += 1 for i=at to set_size do count += count_choices(set_size,n,i,taken) end for return count end function ?count_choices(10,3)
- Output:
220
PHP
<lang 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), "
"; } $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
iced iced iced jam iced plain jam jam jam plain plain plain 220 ways to order 3 donuts given 10 types
Non-recursive algorithm to generate all combinations with repetitons. Taken from here: [1]
You must set k n variables and fill arrays b and c.
<lang PHP> <?php //Author Ivan Gavryushin @dcc0 $k=3; $n=5; //set amount of elements as in $n var $c=array(1,2,3,4,5); //set amount of 1 as in $k var $b=array(1,1,1); $j=$k-1; //Вывод function printt($b,$k) {
$z=0;
while ($z < $k) print $b[$z++].' ';
print '
';
}
printt ($b,$k);
while (1) {
//Увеличение на позиции K до N
if (array_search($b[$j]+1,$c)!==false ) { $b[$j]=$b[$j]+1; printt ($b,$k); } if ($b[$k-1]==$n) {
$i=$k-1; //Просмотр массива справа налево while ($i >= 0) { //Условие выхода if ( $i == 0 && $b[$i] == $n) break 2; //Поиск элемента для увеличения
$m=array_search($b[$i]+1,$c);
if ($m!==false) { $c[$m]=$c[$m]-1; $b[$i]=$b[$i]+1;
$g=$i; //Сортировка массива B while ($g != $k-1) { array_unshift ($c, $b[$g+1]); $b[$g+1]=$b[$i]; $g++; } //Удаление повторяющихся значений из C $c=array_diff($c,$b); printt ($b,$k);
array_unshift ($c, $n);
break;
}
$i--;
}
} }
?> </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
Prolog
<lang prolog> combinations_of_length(_,[]). combinations_of_length([X|T],[X|Combinations]):-
combinations_of_length([X|T],Combinations).
combinations_of_length([_|T],[X|Combinations]):-
combinations_of_length(T,[X|Combinations]).
</lang>
?- [user]. |: combinations_of_length(_,[]). |: combinations_of_length([X|T],[X|Combinations]):- |: combinations_of_length([X|T],Combinations). |: combinations_of_length([_|T],[X|Combinations]):- |: combinations_of_length(T,[X|Combinations]). |: ^D% user://1 compiled 0.01 sec, 3 clauses true. ?- combinations_of_length([0,1,2,4],[L0, L1, L2, L3, L4, L5]). L0 = L1, L1 = L2, L2 = L3, L3 = L4, L4 = L5, L5 = 0 ; L0 = L1, L1 = L2, L2 = L3, L3 = L4, L4 = 0, L5 = 1 ; L0 = L1, L1 = L2, L2 = L3, L3 = L4, L4 = 0, L5 = 2 ; L0 = L1, L1 = L2, L2 = L3, L3 = L4, L4 = 0, L5 = 4 ; L0 = L1, L1 = L2, L2 = L3, L3 = 0, L4 = L5, L5 = 1 ; L0 = L1, L1 = L2, L2 = L3, L3 = 0, L4 = 1, L5 = 2 ; L0 = L1, L1 = L2, L2 = L3, L3 = 0, L4 = 1, L5 = 4 ; L0 = L1, L1 = L2, L2 = L3, L3 = 0, L4 = L5, L5 = 2 ; L0 = L1, L1 = L2, L2 = L3, L3 = 0, L4 = 2, . . .
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(n) + " dougnut types taken " + Str(k) + " 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.
- Output:
Combinations of 3 dougnut types taken 2 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:
Or, assembling our own combsWithRep, by composition of functional primitives:
<lang python>Combinations with repetitions
from itertools import (accumulate, chain, islice, repeat) from functools import (reduce)
- combsWithRep :: Int -> [a] -> [kTuple a]
def combsWithRep(k):
A list of tuples, representing sets of cardinality k, with elements drawn from xs. def f(a, x): def go(ys, xs): return xs + [[x] + y for y in ys] return accumulate(a, go)
def combsBySize(xs): return reduce( f, xs, chain( [[[]]], islice(repeat([]), k) ) ) return lambda xs: [ tuple(x) for x in next(islice( combsBySize(xs), k, None )) ]
- TEST ----------------------------------------------------
def main():
Test the generation of sets of cardinality k with elements drawn from xs. print( combsWithRep(2)(['iced', 'jam', 'plain']) ) print( len(combsWithRep(3)(enumFromTo(0)(9))) )
- GENERIC -------------------------------------------------
- enumFromTo :: (Int, Int) -> [Int]
def enumFromTo(m):
Integer enumeration from m to n. return lambda n: list(range(m, 1 + n))
- showLog :: a -> IO String
def showLog(*s):
Arguments printed with intercalated arrows. print( ' -> '.join(map(str, s)) )
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
[('iced', 'iced'), ('jam', 'iced'), ('jam', 'jam'), ('plain', 'iced'), ('plain', 'jam'), ('plain', 'plain')] 220
Quackery
Regarding the extra credit portion of the task, while this is clearly not the most efficient way of computing the number, it does serve to illustrate that, at the very least, the algorithm generates the correct number of choices, so I am content to comply with the specification rather than demonstrate a more efficient method.
"plaindrome" is not a typo. It is however, a neologism that appears to have little to no currency outside of The On-Line Encyclopedia of Integer Sequences.
<lang Quackery>( nextplain generates the next plaindrome in the
current base by adding one to a given plaindrome, then replacing each trailing zero with the least significant non-zero digit of the number See: https://oeis.org/search?q=plaindromes 4 base put -1 10 times [ nextplain dup echo sp ] drop base release prints "0 1 2 3 11 12 13 22 23 33" i.e. decimal "0 1 2 3 5 6 7 10 11 15" Right padding the base 4 representations with zeros gives all the combinations with repetitions for selecting two doughnuts in a store selling four types of doughnut, numbered 0, 1, 2, and 3. 00 01 02 03 11 12 13 22 23 33 ) [ 1+ dup 0 = if done 0 swap [ base share /mod dup 0 = while drop dip 1+ again ] swap rot 1+ times [ base share * over + ] nip ] is nextplain ( n --> n ) [ dup base put swap ** 1 - [] swap -1 [ 2dup > while nextplain rot over join unrot again ] base release 2drop ] is kcombnums ( n n --> [ )
[ [] unrot times [ base share /mod rot join swap ] drop ] is ndigits ( n n --> [ )
[ [] unrot witheach [ dip dup peek nested rot swap join swap ] drop ] is [peek] ( [ [ --> [ )
[ dup temp put size dup base put dip dup kcombnums [] unrot witheach [ over ndigits temp share swap [peek] nested rot swap join swap ] temp release base release drop ] is kcombs ( n [ --> [ )
2 $ "jam iced plain" nest$ kcombs witheach [ witheach [ echo$ sp ] cr ] cr 3 10 kcombnums size echo</lang>
- Output:
jam jam iced jam plain jam iced iced plain iced plain plain 220
R
The idiomatic solution is to just use a library. <lang R>library(gtools) combinations(3, 2, c("iced", "jam", "plain"), set = FALSE, repeats.allowed = TRUE) nrow(combinations(10, 3, repeats.allowed = TRUE))</lang>
- Output:
> combinations(3, 2, c("iced", "jam", "plain"), set = FALSE, repeats.allowed = TRUE) [,1] [,2] [1,] "iced" "iced" [2,] "iced" "jam" [3,] "iced" "plain" [4,] "jam" "jam" [5,] "jam" "plain" [6,] "plain" "plain" > nrow(combinations(10, 3, repeats.allowed = TRUE)) [1] 220
Racket
<lang 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))))]))
</lang>
Raku
(formerly Perl 6)
One could simply generate all permutations, and then remove "duplicates":
<lang perl6>my @S = <iced jam plain>; my $k = 2;
.put for [X](@S xx $k).unique(as => *.sort.cache, with => &[eqv])</lang>
- Output:
iced iced iced jam iced plain jam jam jam plain plain plain
Alternatively, a recursive solution:
<lang perl6>proto combs_with_rep (UInt, @) {*}
multi combs_with_rep (0, @) { () } multi combs_with_rep (1, @a) { map { $_, }, @a } multi combs_with_rep ($, []) { () } multi combs_with_rep ($n, [$head, *@tail]) {
|combs_with_rep($n - 1, ($head, |@tail)).map({ $head, |@_ }), |combs_with_rep($n, @tail);
}
.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
REXX
version 1
This REXX version uses a type of anonymous recursion. <lang rexx>/*REXX pgm displays combination sets with repetitions for X things taken Y at a time*/ call RcombN 3, 2, 'iced jam plain' /*The 1st part of Rosetta Code task. */ call RcombN -10, 3, 'Iced jam plain' /* " 2nd " " " " " */ exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ RcombN: procedure; parse arg x,y,syms; tell= x>0; x=abs(x); z=x+1 /*X>0? Show combo*/
say copies('─',15) x "doughnut selection taken" y 'at a time:' /*display title. */ do i=1 for words(syms); $.i=word(syms, i) /*assign symbols.*/ end /*i*/ @.=1 /*assign default.*/ do #=1; if tell then call show /*display combos?*/ @.y=@.y + 1; if @.y==z then if .(y-1) then leave /* ◄─── recursive*/ end /*#*/ say copies('═',15) # "combinations."; say; say /*display answer.*/ return
/*──────────────────────────────────────────────────────────────────────────────────────*/ .: procedure expose @. y z; parse arg ?; if ?==0 then return 1; p=@.? +1
if p==z then return .(? -1); do j=? to y; @.j=p; end /*j*/; return 0
/*──────────────────────────────────────────────────────────────────────────────────────*/ show: L=; do c=1 for y; _=@.c; L=L $._; end /*c*/; say L; return</lang>
- output:
─────────────── 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 taken 3 at a time: ═══════════════ 220 combinations.
version 2
recursive (taken from version 1) Reformatted and variable names suitable for OoRexx. <lang rexx>/*REXX compute (and show) combination sets for nt things in ns places*/
debug=0 Call time 'R' Call RcombN 3,2,'iced,jam,plain' /* The 1st part of the task */ Call RcombN -10,3,'iced,jam,plain,d,e,f,g,h,i,j' /* 2nd part */ Call RcombN -10,9,'iced,jam,plain,d,e,f,g,h,i,j' /* extra part */ Say time('E') 'seconds' Exit
/*-------------------------------------------------------------------*/ Rcombn: Procedure Expose thing. debug
Parse Arg nt,ns,thinglist tell=nt>0 nt=abs(nt) Say '------------' nt 'doughnut selection taken' ns 'at a time:' If tell=0 Then Say ' list output suppressed' Do i=1 By 1 While thinglist> Parse Var thinglist thing.i ',' thinglist /* assign things. */ End index.=1 Do cmb=1 By 1 If tell Then /* display combinations */ Call show /* show this one */ index.ns=index.ns+1 Call show_index 'A' If index.ns==nt+1 Then If proc(ns-1) Then Leave End Say '------------' cmb 'combinations.' Say Return
/*-------------------------------------------------------------------*/ proc: Procedure Expose nt ns thing. index. debug
Parse Arg recnt If recnt>0 Then Do p=index.recnt+1 If p=nt+1 Then Return proc(recnt-1) Do i=recnt To ns index.i=p End Call show_index 'C' End Return recnt=0
/*-------------------------------------------------------------------*/ show: Procedure Expose index. thing. ns debug
l= Call show_index 'B----------------------->' Do i=1 To ns j=index.i l=l thing.j End Say l Return
show_index: Procedure Expose index. ns debug
If debug Then Do Parse Arg tag l=tag Do i=1 To ns l=l index.i End Say l End Return</lang>
- Output:
----------- 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 taken 3 at a time: list output suppressed ------------ 220 combinations. ------------ 10 doughnut selection taken 9 at a time: list output suppressed ------------ 48620 combinations. 0.125000 seconds
version 3
iterative (transformed from version 1) <lang rexx>/*REXX compute (and show) combination sets for nt things in ns places*/
Numeric Digits 20 debug=0 Call time 'R' Call IcombN 3,2,'iced,jam,plain' /* The 1st part of the task */ Call IcombN -10,3,'iced,jam,plain,d,e,f,g,h,i,j' /* 2nd part */ Call IcombN -10,9,'iced,jam,plain,d,e,f,g,h,i,j' /* extra part */ Say time('E') 'seconds' Exit
IcombN: Procedure Expose thing. debug
Parse Arg nt,ns,thinglist tell=nt>0 nt=abs(nt) Say '------------' nt 'doughnut selection taken' ns 'at a time:' If tell=0 Then Say ' list output suppressed' Do i=1 By 1 While thinglist> Parse Var thinglist thing.i ',' thinglist /* assign things. */ End index.=1 cmb=0 Call show i=ns+1 Do While i>1 i=i-1 Do j=1 By 1 While index.i<nt index.i=index.i+1 Call show End i1=i-1 If index.i1<nt Then Do index.i1=index.i1+1 Do ii=i To ns index.ii=index.i1 End Call show i=ns+1 End If index.1=nt Then Leave End Say cmb Return
show: Procedure Expose ns index. thing. tell cmb
cmb=cmb+1 If tell Then Do l= Do i=1 To ns j=index.i l=l thing.j End Say l End Return</lang>
- Output:
------------ 3 doughnut selection taken 2 at a time: iced iced iced jam iced plain jam jam jam plain plain plain 6 ------------ 10 doughnut selection taken 3 at a time: list output suppressed 220 ------------ 10 doughnut selection taken 9 at a time: list output suppressed 48620 0.109000 seconds
Slightly faster
Ring
<lang ring>
- Project : Combinations with repetitions
n = 2 k = 3 temp = [] comb = [] num = com(n, k) combinations(n, k) comb = sortfirst(comb, 1) see showarray(comb) + nl
func combinations(n, k) while true
temp = [] for nr = 1 to k tm = random(n-1) + 1 add(temp, tm) next add(comb, temp) for p = 1 to len(comb) - 1 for q = p + 1 to len(comb) if (comb[p][1] = comb[q][1]) and (comb[p][2] = comb[q][2]) and (comb[p][3] = comb[q][3]) del(comb, p) ok next next if len(comb) = num exit ok
end
func com(n, k)
res = pow(n, k) return res
func showarray(vect)
svect = "" for nrs = 1 to len(vect) svect = "[" + vect[nrs][1] + " " + vect[nrs][2] + " " + vect[nrs][3] + "]" + nl see svect next
Func sortfirst(alist, ind)
aList = sort(aList,ind) for n = 1 to len(alist)-1 for m= n + 1 to len(aList) if alist[n][1] = alist[m][1] and alist[m][2] < alist[n][2] temp = alist[n] alist[n] = alist[m] alist[m] = temp ok next next for n = 1 to len(alist)-1 for m= n + 1 to len(aList) if alist[n][1] = alist[m][1] and alist[n][2] = alist[m][2] and alist[m][3] < alist[n][3] temp = alist[n] alist[n] = alist[m] alist[m] = temp ok next next return aList
</lang> Output:
[1 1 1] [1 1 2] [1 2 1] [1 2 2] [2 1 1] [2 1 2] [2 2 1] [2 2 2]
Ruby
<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 ')}
- Extra credit
possible_doughnuts = [*1..10].repeated_combination(3)
- size returns the size of the enumerator, or nil if it can’t be calculated lazily.
puts "", "#{possible_doughnuts.size} ways to order 3 donuts given 10 types."</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 220 ways to order 3 donuts given 10 types.
Rust
<lang rust> // Iterator for the combinations of `arr` with `k` elements with repetitions. // Yields the combinations in lexicographical order. struct CombinationsWithRepetitions<'a, T: 'a> {
// source array to get combinations from arr: &'a [T], // length of the combinations k: u32, // current counts of each object that represent the next combination counts: Vec<u32>, // whether there are any combinations left remaining: bool,
}
impl<'a, T> CombinationsWithRepetitions<'a, T> {
fn new(arr: &[T], k: u32) -> CombinationsWithRepetitions<T> { let mut counts = vec![0; arr.len()]; counts[arr.len() - 1] = k; CombinationsWithRepetitions { arr, k, counts, remaining: true, } }
}
impl<'a, T> Iterator for CombinationsWithRepetitions<'a, T> {
type Item = Vec<&'a T>;
fn next(&mut self) -> Option<Vec<&'a T>> { if !self.remaining { return None; } let mut comb = Vec::new(); for (count, item) in self.counts.iter().zip(self.arr.iter()) { for _ in 0..*count { comb.push(item); } } // this is lexicographically largest, and thus the last combination if self.counts[0] == self.k { self.remaining = false; } else { let n = self.counts.len(); for i in (1..n).rev() { if self.counts[i] > 0 { let original_value = self.counts[i]; self.counts[i - 1] += 1; for j in i..(n - 1) { self.counts[j] = 0; } self.counts[n - 1] = original_value - 1; break; } } } Some(comb) }
}
fn main() {
let collection = vec!["iced", "jam", "plain"]; for comb in CombinationsWithRepetitions::new(&collection, 2) { for item in &comb { print!("{} ", item) } println!() }
}
</lang>
- Output:
plain plain jam plain jam jam iced plain iced jam iced iced
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 (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)</lang>
- Output:
((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain)) 220
Dynamic programming
<lang scheme>(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)</lang>
- Output:
((iced iced) (jam iced) (jam jam) (plain iced) (plain jam) (plain plain)) 220
Sidef
<lang ruby>func cwr (n, l, a = []) {
n>0 ? (^l -> map {|k| __FUNC__(n-1, l.slice(k), [a..., l[k]]) }) : a
}
cwr(2, %w(iced jam plain)).each {|a|
say a.map{ .join(' ') }.join("\n")
}</lang>
Also built-in:
<lang ruby>%w(iced jam plain).combinations_with_repetition(2, {|*a|
say a.join(' ')
})</lang>
- Output:
iced iced iced jam iced plain jam jam jam plain plain plain
Efficient count of the total number of combinations with repetition: <lang ruby>func cwr_count (n, m) { binomial(n + m - 1, m) } printf("\nThere are %s ways to pick 7 out of 10 with repetition\n", cwr_count(10, 7))</lang>
- Output:
There are 11440 ways to pick 7 out of 10 with repetition
Standard ML
<lang sml>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</lang>
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
Dynamic programming
<lang sml>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</lang>
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
Stata
<lang stata>function combrep(v,k) { n = cols(v) a = J(comb(n+k-1,k),k,v[1]) u = J(1,k,1) for (i=2; 1; i++) { for (j=k; j>0; j--) { if (u[j]<n) break } if (j<1) return(a) m = u[j]+1 for (; j<=k; j++) u[j] = m a[i,.] = v[u] } }
combrep(("iced","jam","plain"),2)
a = combrep(1..10,3) rows(a)</lang>
Output
1 2 +-----------------+ 1 | iced iced | 2 | iced jam | 3 | iced plain | 4 | jam jam | 5 | jam plain | 6 | plain plain | +-----------------+ 220
Swift
<lang Swift>func combosWithRep<T>(var objects: [T], n: Int) -> T {
if n == 0 { return [[]] } else { var combos = T() while let element = objects.last { combos.appendContentsOf(combosWithRep(objects, n: n - 1).map{ $0 + [element] }) objects.removeLast() } return combos }
} print(combosWithRep(["iced", "jam", "plain"], n: 2).map {$0.joinWithSeparator(" and ")}.joinWithSeparator("\n"))</lang> Output:
plain and plain jam and plain iced and plain jam and jam iced and jam iced and iced
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
TXR
<lang dos>txr -p "(rcomb '(iced jam plain) 2)"</lang>
- Output:
((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))
<lang dos>txr -p "(length-list (rcomb '(0 1 2 3 4 5 6 7 8 9) 3))"</lang>
- Output:
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)
VBScript
<lang vb>' Combinations with repetitions - iterative - VBScript
Sub printc(vi,n,vs) Dim i, w For i=0 To n-1 w=w &" "& vs(vi(i)) Next 'i Wscript.Echo w End Sub
Sub combine(flavors, draws, xitem, tell) Dim n, i, j ReDim v(draws) If tell Then Wscript.Echo "list of cwr("& flavors &","& draws &") :" Do While True For i=0 To draws-1 If v(i)>flavors-1 Then v(i+1)=v(i+1)+1 For j=i To 0 Step -1 v(j)=v(i+1) Next 'j End If Next 'i If v(draws)>0 Then Exit Do n=n+1 If tell Then Call printc(v, draws, xitem) v(0)=v(0)+1 Loop Wscript.Echo "cwr("& flavors &","& draws &")="&n End Sub
items=Array( "iced", "jam", "plain" ) combine 3, 2, items, True combine 10, 3, , False combine 10, 7, , False combine 10, 9, , False </lang>
- Output:
list of cwr(3,2) : iced iced jam iced plain iced jam jam plain jam plain plain cwr(3,2)=6 cwr(10,3)=220 cwr(10,7)=11440 cwr(10,9)=48620
Wren
<lang ecmascript>var combrep // recursive combrep = Fn.new { |n, lst|
if (n == 0 ) return [[]] if (lst.count == 0) return [] var r = combrep.call(n, lst[1..-1]) for (x in combrep.call(n-1, lst)) { var y = x.toList y.add(lst[0]) r.add(y) } return r
}
System.print(combrep.call(2, ["iced", "jam", "plain"])) System.print(combrep.call(3, (1..10).toList).count)</lang>
- Output:
[[plain, plain], [plain, jam], [jam, jam], [plain, iced], [jam, iced], [iced, iced]] 220
XPL0
<lang 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); ]</lang>
- Output:
iced iced iced jam iced plain jam jam jam plain plain plain Combos = 6 Combos = 220
zkl
<lang zkl>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,*]));
}</lang> <lang zkl>combosK(2,T("iced","jam","plain")).apply("concat",","); combosK(3,T(0,1,2,3,4,5,6,7,8,9)).len();</lang>
- Output:
L("iced,iced","iced,jam","iced,plain","jam,jam","jam,plain","plain,plain") 220
ZX Spectrum Basic
<lang zxbasic>10 READ n 20 DIM d$(n,5) 30 FOR i=1 TO n 40 READ d$(i) 50 NEXT i 60 DATA 3,"iced","jam","plain" 70 FOR i=1 TO n 80 FOR j=i TO n 90 PRINT d$(i);" ";d$(j) 100 NEXT j 110 NEXT i</lang>
- Programming Tasks
- Discrete math
- 360 Assembly
- Ada
- AppleScript
- AutoHotkey
- AWK
- BBC BASIC
- Bracmat
- C
- C sharp
- C++
- Clojure
- CoffeeScript
- Common Lisp
- Crystal
- D
- EasyLang
- EchoLisp
- Egison
- Elixir
- Erlang
- Fortran
- FreeBASIC
- GAP
- Go
- Haskell
- Icon
- Unicon
- IS-BASIC
- J
- Java
- JavaScript
- Jq
- Julia
- Kotlin
- LFE
- Lobster
- Lua
- Maple
- Mathematica
- Wolfram Language
- Mercury
- Nim
- OCaml
- PARI/GP
- Perl
- Phix
- PHP
- PicoLisp
- Prolog
- PureBasic
- Python
- Quackery
- R
- Racket
- Raku
- REXX
- Ring
- Ruby
- Rust
- Scala
- Scheme
- Sidef
- Standard ML
- Stata
- Swift
- Tcl
- TXR
- Ursala
- VBScript
- Wren
- XPL0
- Zkl
- ZX Spectrum Basic