# Combinations with repetitions

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 $\{\mathrm {iced} ,\mathrm {jam} ,\mathrm {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.

• 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

The number of samples of size k from n objects.
With combinations and permutations generation tasks.
Order Unimportant Order Important
Without replacement ${\binom {n}{k}}=^{n}\operatorname {C} _{k}={\frac {n(n-1)\ldots (n-k+1)}{k(k-1)\dots 1}}$ $^{n}\operatorname {P} _{k}=n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)$
With replacement ${\binom {n+k-1}{k}}=^{n+k-1}\operatorname {C} _{k}={(n+k-1)! \over (n-1)!k!}$ $n^{k}$

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

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

## AppleScript

Translation of: Python
-- 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 aon Just(x)    {type:"Maybe", Nothing:false, Just:x}end Just -- Nothing :: Maybe aon 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 ifend enumFromTo -- foldl :: (a -> b -> a) -> a -> [b] -> aon 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 tellend foldl -- index (!!) :: [a] -> Int -> Maybe a-- index (!!) :: Gen [a] -> Int -> Maybe a-- index (!!) :: String -> Int -> Maybe Charon |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 ifend |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 tellend map -- min :: Ord a => a -> a -> aon min(x, y)    if y < x then        y    else        x    end ifend 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 ifend mReturn -- repeat :: a -> Generator [a]on |repeat|(x)    script        on |λ|()            return x        end |λ|    end scriptend |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 tellend 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 ifend scanl1  -- take :: Int -> [a] -> [a]-- take :: Int -> String -> Stringon 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 ifend take
Output:
{220, {{"iced", "iced"}, {"jam", "iced"}, {"jam", "jam"}, {"plain", "iced"}, {"plain", "jam"}, {"plain", "plain"}}}

## AWK

 # syntax: GAWK -f COMBINATIONS_WITH_REPETITIONS.AWKBEGIN {    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)}

output:

iced iced
iced jam
iced plain
jam jam
jam plain
plain plain
choices = 6


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


## 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 ## 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; 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 ## C++ Non recursive version.  #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 += 1; }} int main(){ vector<string> options{ "iced", "jam", "plain" }; combination_with_repetiton(3, 2, options); return 0; }  Output: iced iced jam iced plain iced jam jam plain jam plain plain  ## C# Translation of: PHP  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; 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; }}  Output: iced iced iced jam iced plain jam jam jam plain plain plain 220 ways to order 3 donuts given 10 types  Recursive version  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)); } }}  ## 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))  ## CoffeeScript  combos = (arr, k) -> return [ [] ] if k == 0 return [] if arr.length == 0 combos_with_head = ([arr].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, 2console.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  ## Common Lisp The code below is a modified version of the Clojure solution. (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))))))  Output: ((:ICED :ICED) (:ICED :JAM) (:ICED :PLAIN) (:JAM :JAM) (:JAM :PLAIN) (:PLAIN :PLAIN))  ## Crystal Translation of: 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 creditpossible_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." 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. 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 @safeif (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);} 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 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 ~ 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

## EasyLang

items$[] = [ "iced" "jam" "plain" ]n = len items$[]k = 2len result[] kn_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 = 10k = 3len result[] kitems$[] = [ ]n_results = 0call combine 0 0print ""print n_results & " results with 10 donuts"
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.

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

## 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"|]}  ## Elixir Translation of: Erlang 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) endend 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)))}" Output: [:iced, :iced] [:iced, :jam] [:iced, :plain] [:jam, :jam] [:jam, :plain] [:plain, :plain] Extra credit: 220  ## 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  ## 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  ## GAP # Built-inUnorderedTuples(["iced", "jam", "plain"], 2); ## Go ### 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)) } 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  ### 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  ### 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 []msPairfunc (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  ## 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] -> IntcountCombsWithRep k lst = binomial (k - 1 + length lst) k -- countCombsWithRep k = length . combsWithRep kmain :: IO ()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

### 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 = scanl1 $(++) . map (x :) main :: IO ()main = print$ combsWithRep 2 ["iced", "jam", "plain"]

and another approach, using manual recursion:

combsWithRep  :: (Eq a)  => Int -> [a] -> [[a]]combsWithRep k xs = comb k []  where    comb 0 lst = lst    comb n [] = comb (n - 1) (pure <$> xs) comb n peers = let nextLayer ys@(h:_) = (: ys) <$> dropWhile (/= h) xs      in comb (n - 1) (foldMap nextLayer peers) main :: IO ()main = do  print $combsWithRep 2 ["iced", "jam", "plain"] print$ length $combsWithRep 3 [0 .. 9] 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:  # generate all combinations of length n from list L, # including repetitionsprocedure 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 # 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 functionprocedure write_list (l) every (writes (!l || " ")) write ()end # testing routineprocedure 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  ## IS-BASIC 100 PROGRAM "Combinat.bas"110 READ N120 STRING D$(1 TO N)*5130 FOR I=1 TO N140   READ D$(I)150 NEXT160 FOR I=1 TO N170 FOR J=I TO N180 PRINT D$(I);" ";D$(J)190 NEXT200 NEXT210 DATA 3,iced,jam,plain ## 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. rcomb=: >@[email protected]:(/:~&.>)@,@{@# < 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 repetitions220 ### J Alternate implementation Considerably faster: require 'stats'combr=: [email protected][ -"1~ [ comb + - 1:rcomb=: (combr #) { ] rcomb functions identically, and combr calculates indices:  2 combr 30 00 10 21 11 22 2 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  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  ## JavaScript ### ES5 #### Imperative <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 #### Functional (function () { // n -> [a] -> [[a]] function combsWithRep(n, lst) { return n ? ( lst.length ? combsWithRep(n - 1, lst).map(function (t) { return [lst].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)) 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 ]; })(); Output: [ [["iced", "iced"], ["iced", "jam"], ["iced", "plain"], ["jam", "jam"], ["jam", "plain"], ["plain", "plain"]], 220] ### ES6 Translation of: Haskell (() => { '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 : 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))) });})(); Output: { "twoFromThree": [ [ "iced", "iced" ], [ "jam", "iced" ], [ "plain", "iced" ], [ "jam", "jam" ], [ "plain", "jam" ], [ "plain", "plain" ] ], "threeFromTen": 220 } ## 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.

## Julia

Works with: Julia version 0.6
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))
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

// 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".split("")    CombsWithReps(3, 10, generic10, true)   }
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

Translation of: Erlang
and
Translation of: Clojure

### With List Comprehension

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

### With Map

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

Output is the same for both:

 > (combinations '(iced jam plain) 2)((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain)) 

## 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 tOutputend 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)	endend 

## 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]] 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]-> 6Combi[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:= CombinWithRep[{"iced", "jam", "plain"}, 2] Out= {{"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.

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

## Nim

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

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

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

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


## 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])),ways(k,u,s))};xc(k,v)=binomial(#v+k-1,k);ways(2, ["iced","jam","plain"])

sub p { $_ ? map p($_ - 1, [@{$_},$_[$_]], @_[$_ .. $#_]), 2 ..$#_ : $_ }sub f {$_ ? $_ * f($_ - 1) : 1 }sub pn{ f($_ +$_ - 1) / f($_) / f($_ - 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"; ## Perl 6 One could simply generate all permutations, and then remove "duplicates": Works with: Rakudo version 2016.07 my @S = <iced jam plain>;my$k = 2; .put for [X](@S xx $k).unique(as => *.sort.cache, with => &[eqv]) Output: iced iced iced jam iced plain jam jam jam plain plain plain  Alternatively, a recursive solution: Translation of: Haskell 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 );
Output:
(iced iced)
(iced jam)
(iced plain)
(jam jam)
(jam plain)
(plain plain)
220

## Phix

procedure choose(sequence from, integer n, at=1, sequence res={})    if length(res)=n then        ?res    else        for i=at to length(from) do            choose(from,n,i,append(res,from[i]))        end for    end ifend procedure choose({"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:

function choices(integer from, n, at=1, taken=0)integer count = 0    if taken=n then return 1 end if    taken += 1    for i=at to from do        count += choices(from,n,i,taken)    end for    return countend function ?choices(10,3)
Output:
220


## PHP

Non-recursive algorithm to generate all combinations with repetitons. Taken from here: 

You must set k n variables and fill arrays b and c.

 <?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 '<br>';}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--; } } } ?>  ## PHP <?php function combos($arr, $k) { if ($k == 0) {      return array(array());    }     if (count($arr) == 0) { return array(); }$head = $arr;$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  ## 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 ## 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 combinationEndProcedure 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

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

Or, assembling our own combsWithRep, by composition of functional primitives:

Works with: Python version 3.7
'''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 Stringdef showLog(*s):    '''Arguments printed with       intercalated arrows.'''    print(        ' -> '.join(map(str, s))    )  # MAIN ---if __name__ == '__main__':    main()
Output:
[('iced', 'iced'), ('jam', 'iced'), ('jam', 'jam'), ('plain', 'iced'), ('plain', 'jam'), ('plain', 'plain')]
220

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

## REXX

### version 1

This REXX version uses a type of anonymous recursion.

/*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?*/ @.[email protected].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; [email protected].? +1 if p==z then return .(? -1); do j=? to y; @.j=p; end /*j*/; return 0/*──────────────────────────────────────────────────────────────────────────────────────*/show: L=; do c=1 for y; [email protected].c; L=L$._;   end  /*c*/;       say L;    return
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.

/*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
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)

/*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
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

 # Project : Combinations with repetitions n = 2k = 3temp = []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] = comb[q]) and (comb[p] = comb[q]) and (comb[p] = comb[q])                         del(comb, p)                     ok                next         next         if len(comb) = num            exit         okend func com(n, k)        res = pow(n, k)        return res func showarray(vect)        svect = ""        for nrs = 1 to len(vect)              svect = "[" + vect[nrs] + " " + vect[nrs] + " " + vect[nrs] + "]" + 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] = alist[m] and alist[m] < alist[n]                     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] = alist[m] and alist[n] = alist[m] and alist[m] < alist[n]                     temp = alist[n]                     alist[n] = alist[m]                     alist[m] = temp                   ok              next       next       return aList 

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

Works with: Ruby version 2.0
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 creditpossible_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."
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.


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

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


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


## Sidef

Translation of: Perl
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")}

Also built-in:

%w(iced jam plain).combinations_with_repetition(2, {|*a|    say a.join(' ')})
Output:
iced iced
iced jam
iced plain
jam jam
jam plain
plain plain


Efficient count of the total number of combinations with repetition:

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))
Output:
There are 11440 ways to pick 7 out of 10 with repetition


## Standard ML

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


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


## Stata

function combrep(v,k) {	n = cols(v)	a = J(comb(n+k-1,k),k,v)	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)

Output

           1       2
+-----------------+
1 |   iced    iced  |
2 |   iced     jam  |
3 |   iced   plain  |
4 |    jam     jam  |
5 |    jam   plain  |
6 |  plain   plain  |
+-----------------+

220

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

Output:

plain and plain
jam and plain
iced and plain
jam and jam
iced and jam
iced and iced

## Tcl

package require Tcl 8.5proc 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


## TXR

txr -p "(rcomb '(iced jam plain) 2)"
Output:
((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))


txr -p "(length-list (rcomb '(0 1 2 3 4 5 6 7 8 9) 3))"
Output:
220


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


## 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 objectsint  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, );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


## 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)).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


## ZX Spectrum Basic

10 READ n20 DIM d$(n,5)30 FOR i=1 TO n40 READ d$(i)50 NEXT i60 DATA 3,"iced","jam","plain"70 FOR i=1 TO n80 FOR j=i TO n90 PRINT d$(i);" ";d$(j)100 NEXT j110 NEXT i`