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.

Task

• 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

• k-combination with repetitions

See also

The number of samples of size k from n objects.

With   combinations and permutations   generation tasks.

	Order Unimportant	Order Important
Without replacement	${\binom {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)$
	Task: Combinations	Task: Permutations
With replacement	${\binom {n+k-1}{k}}=^{n+k-1}\operatorname {C} _{k}={(n+k-1)! \over (n-1)!k!}$	$n^{k}$
	Task: Combinations with repetitions	Task: Permutations with repetitions

11l

Translation of: Nim

F combsReps(lst, k)
   T Ty = T(lst[0])
   I k == 0
      R [[Ty]()]
   I lst.empty
      R [[Ty]]()
   R combsReps(lst, k - 1).map(x -> @lst[0] [+] x) [+] combsReps(lst[1..], k)

print(combsReps([‘iced’, ‘jam’, ‘plain’], 2))
print(combsReps(Array(1..10), 3).len)

Output:

[[iced, iced], [iced, jam], [iced, plain], [jam, jam], [jam, plain], [plain, plain]]
220

360 Assembly

*        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

Output:

list:
iced  iced
jam   iced
plain iced
jam   jam
plain jam
plain plain
cwr( 3, 2)=           6
cwr(10, 3)=         220

Acornsoft Lisp

Translation of: Scheme

(defun samples (k items)
  (cond
    ((zerop k) '(()))
    ((null items) '())
    (t (append
          (mapc '(lambda (c) (cons (car items) c))
                (samples (sub1 k) items))
          (samples k (cdr items))))))

(defun append (a b)
  (cond ((null a) b)
        (t (cons (car a) (append (cdr a) b)))))

(defun length (list (len . 0))
  (map '(lambda (e) (setq len (add1 len)))
       list)
  len)

Output:

Evaluate : (samples 2 '(iced jam plain))

Value is : ((iced iced) (iced jam) (iced plain) (jam jam)
(jam plain) (plain plain))

Evaluate : (length (samples 3 '(1 2 3 4 5 6 7 8 9 10)))

Value is : 220

Action!

PROC PrintComb(BYTE ARRAY c BYTE len)
  BYTE i,ind

  FOR i=0 TO len-1
  DO
    IF i>0 THEN Put('+) FI
    ind=c(i)
    IF ind=0 THEN
      Print("iced")
    ELSEIF ind=1 THEN
      Print("jam")
    ELSE
      Print("plain")
    FI
  OD
  PutE()
RETURN

BYTE FUNC NotDecreasing(BYTE ARRAY c BYTE len)
  BYTE i

  IF len<2 THEN RETURN (1) FI

  FOR i=0 TO len-2
  DO
    IF c(i)>c(i+1) THEN
      RETURN (0)
    FI
  OD
RETURN (1)

BYTE FUNC NextComb(BYTE ARRAY c BYTE n,k)
  INT pos,i

  DO
    pos=k-1
    DO
      c(pos)==+1
      IF c(pos)<n THEN
        EXIT
      ELSE
        pos==-1
        IF pos<0 THEN RETURN (0) FI
      FI
      FOR i=pos+1 TO k-1
      DO
        c(i)=c(pos)
      OD
    OD
  UNTIL NotDecreasing(c,k)
  OD
RETURN (1)

PROC Comb(BYTE n,k,show)
  BYTE ARRAY c(10)
  BYTE i,count

  IF k>n THEN
    Print("Error! k is greater than n.")
    Break()
  FI

  PrintF("Choices of %B from %B:%E",k,n)
  FOR i=0 TO k-1
  DO
    c(i)=0
  OD

  count=0
  DO
    count==+1
    IF show THEN
      PrintF(" %B. ",count)
      PrintComb(c,k)
    FI
  UNTIL NextComb(c,n,k)=0
  OD
  PrintF("Total choices %B%E%E",count)
RETURN

PROC Main()
  Comb(3,2,1)
  Comb(10,3,0)
RETURN

Output:

Screenshot from Atari 8-bit computer

Choices of 2 from 3:
1. iced+iced
2. iced+jam
3. iced+plain
4. jam+jam
5. jam+plain
6. plain+plain
Total choices 6

Choices of 3 from 10:
Total choices 220

Ada

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

combinations.adb:

with Ada.Text_IO;
procedure Combinations is

   generic
      type Set is (<>);
   function Combinations
     (Count  : Positive;
      Output : Boolean := False)
      return   Natural;

   function Combinations
     (Count  : Positive;
      Output : Boolean := False)
      return   Natural
   is
      package Set_IO is new Ada.Text_IO.Enumeration_IO (Set);
      type Set_Array is array (Positive range <>) of Set;
      Empty_Array : Set_Array (1 .. 0);
      function Recurse_Combinations
        (Number : Positive;
         First  : Set;
         Prefix : Set_Array)
         return   Natural
      is
         Combination_Count : Natural := 0;
      begin
         for Next in First .. Set'Last loop
            if Number = 1 then
               Combination_Count := Combination_Count + 1;
               if Output then
                  for Element in Prefix'Range loop
                     Set_IO.Put (Prefix (Element));
                     Ada.Text_IO.Put ('+');
                  end loop;
                  Set_IO.Put (Next);
                  Ada.Text_IO.New_Line;
               end if;
            else
               Combination_Count := Combination_Count +
                                    Recurse_Combinations
                                       (Number - 1,
                                        Next,
                                        Prefix & (1 => Next));
            end if;
         end loop;
         return Combination_Count;
      end Recurse_Combinations;
   begin
      return Recurse_Combinations (Count, Set'First, Empty_Array);
   end Combinations;

   type Donuts is (Iced, Jam, Plain);
   function Donut_Combinations is new Combinations (Donuts);

   subtype Ten is Positive range 1 .. 10;
   function Ten_Combinations is new Combinations (Ten);

   Donut_Count : constant Natural :=
      Donut_Combinations (Count => 2, Output => True);
   Ten_Count   : constant Natural := Ten_Combinations (Count => 3);
begin
   Ada.Text_IO.Put_Line ("Total Donuts:" & Natural'Image (Donut_Count));
   Ada.Text_IO.Put_Line ("Total Tens:" & Natural'Image (Ten_Count));
end Combinations;

Output:

ICED+ICED
ICED+JAM
ICED+PLAIN
JAM+JAM
JAM+PLAIN
PLAIN+PLAIN
Total Donuts: 6
Total Tens: 220

AppleScript

Translation of: Haskell

Translation of: Python

--------------- COMBINATIONS WITH REPETITION -------------

-- combinationsWithRepetition :: Int -> [a] -> [kTuple a]
on combinationsWithRepetition(k, xs)
    -- A list of lists, representing 
    -- sets of cardinality k, with
    -- members drawn from xs.
    
    script combinationsBySize
        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 combinationsBySize, 1 + k)
end combinationsWithRepetition


--------------------------- TEST -------------------------
on run
    {length of combinationsWithRepetition(3, enumFromTo(0, 9)), ¬
        combinationsWithRepetition(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

Output:

{220, {{"iced", "iced"}, {"jam", "iced"}, {"jam", "jam"}, {"plain", "iced"}, {"plain", "jam"}, {"plain", "plain"}}}

Arturo

print combine.repeated.by:2 ["iced" "jam" "plain"]

print combine.count.repeated.by:3 @1..10

Output:

[iced iced] [iced jam] [iced plain] [jam jam] [jam plain] [plain plain] 
220

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++)
} ;===========================================================

Examples:

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

Outputs:

---------------------------
6 Combinations with Repetition found:
iced + iced
iced + jam
iced + plain
jam + jam
jam + plain
plain + plain
---------------------------
220
---------------------------

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

output:

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

BASIC

BASIC256

arraybase 0
print "Enter n comb m.  "
input integer "n:  ", n
input integer "m:  ", m
outstr$ = ""
dim names$(m)

for i = 0 to m - 1
	print "Name for item "; i; ":  ";
	input string names$[i]
next i
call iterate (outstr$, 0, m-1, n-1, names$)
end

subroutine iterate(curr$, start, stp, depth, names$)
	for i = start to stp
		if depth = 0 then
			print curr$; " "; names$[i]
		else
			call iterate (curr$ & " " & names$[i], i, stp, depth-1, names$)
		end if
	next i
	return
end subroutine

BBC BASIC

Works with: BBC BASIC for Windows

      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

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

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

Non recursive solution

#include <stdio.h>

const char *donuts[] = {"iced", "jam", "plain",
                        "something completely different"};
int pos[] = {0, 0, 0, 0};

void printDonuts(int k) {
  for (size_t i = 1; i < k + 1; i += 1) // offset: i:1..N, N=k+1
    printf("%s\t", donuts[pos[i]]);     // str:0..N-1
  printf("\n");
}

// idea: custom number system with 2s complement like 0b10...0==MIN stop case
void combination_with_repetiton(int n, int k) {
  while (1) {
    for (int i = k; i > 0; i -= 1) {
      if (pos[i] > n - 1) // if number spilled over: xx0(n-1)xx
      {
        pos[i - 1] += 1; // set xx1(n-1)xx
        for (int j = i; j <= k; j += 1)
          pos[j] = pos[j - 1]; // set xx11..1
      }
    }
    if (pos[0] > 0) // stop condition: 1xxxx
      break;
    printDonuts(k);
    pos[k] += 1; // xxxxN -> xxxxN+1
  }
}

int main() {
  combination_with_repetiton(3, 2);
  return 0;
}

#include <stdio.h>

const char * donuts[] = { "iced", "jam", "plain", "something completely different" };
long choose(int * got, int n_chosen, int len, int at, int max_types)
{
        int i;
        long count = 0;
        if (n_chosen == len) {
                if (!got) return 1;

                for (i = 0; i < len; i++)
                        printf("%s\t", donuts[got[i]]);
                printf("\n");
                return 1;
        }

        for (i = at; i < max_types; i++) {
                if (got) got[n_chosen] = i;
                count += choose(got, n_chosen + 1, len, i, max_types);
        }
        return count;
}

int main()
{
        int chosen[3];
        choose(chosen, 0, 2, 0, 3);

        printf("\nWere there ten donuts, we'd have had %ld choices of three\n",
                choose(0, 0, 3, 0, 10));
        return 0;
}

Output:

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

Were there ten donuts, we'd have had 220 choices of three

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

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

C++

Non recursive version.

#include <iostream>
#include <string>
#include <vector>

void print_vector(const std::vector<int> &pos,
                  const std::vector<std::string> &str) {
  for (size_t i = 1; i < pos.size(); ++i) // offset: i:1..N
    printf("%s\t", str[pos[i]].c_str());  // str:      0..N-1
  printf("\n");
}

// idea: custom number system with 2s complement like 0b10...0==MIN stop case
void combination_with_repetiton(int n, int k,
                                const std::vector<std::string> &str) {
  std::vector<int> pos(k + 1, 0);
  while (true) {
    for (int i = k; i > 0; i -= 1) {
      if (pos[i] > n - 1) // if number spilled over: xx0(n-1)xx
      {
        pos[i - 1] += 1; // set xx1(n-1)xx
        for (int j = i; j <= k; j += 1)
          pos[j] = pos[j - 1]; // set xx11..1
      }
    }
    if (pos[0] > 0) // stop condition: 1xxxx
      break;
    print_vector(pos, str);
    pos[k] += 1; // xxxxN -> xxxxN+1
  }
}

int main() {
  std::vector<std::string> str{"iced", "jam", "plain"};
  combination_with_repetiton(3, 2, str);
  return 0;
}

Output:

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

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[0]].concat combo for combo in combos arr, k-1)
  combos_sans_head = combos arr[1...], k
  combos_with_head.concat combos_sans_head
  
arr = ['iced', 'jam', 'plain']
console.log "valid pairs from #{arr.join ','}:"
console.log combos arr, 2
console.log "#{combos([1..10], 3).length} ways to order 3 donuts given 10 types"

Output:

jam,plain:
[ [ 'iced', 'iced' ],
  [ 'iced', 'jam' ],
  [ 'iced', 'plain' ],
  [ 'jam', 'jam' ],
  [ 'jam', 'plain' ],
  [ 'plain', 'plain' ] ]
220 ways to order 3 donuts given 10 types

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

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

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[0] ~ L).array
           ~ combsRep(lst[1 .. $], k);
}

void main() {
    ["iced", "jam", "plain"].combsRep(2).writeln;
    10.iota.array.combsRep(3).length.writeln;
}

Output:

[["iced", "iced"], ["iced", "jam"], ["iced", "plain"], ["jam", "jam"], ["jam", "plain"], ["plain", "plain"]]
220

EasyLang

items$[] = [ "iced" "jam" "plain" ]
n = len items$[]
k = 2
len result[] k
n_results = 0
# 
proc output . .
   n_results += 1
   if len items$[] > 0
      s$ = ""
      for i = 1 to k
         s$ &= items$[result[i]] & " "
      .
      print s$
   .
.
proc combine pos val . .
   if pos > k
      output
   else
      for i = val to n
         result[pos] = i
         combine pos + 1 i
      .
   .
.
combine 1 1
# 
n = 10
k = 3
len result[] k
items$[] = [ ]
n_results = 0
combine 1 1
print ""
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)
  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)))}"

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

Factor

See the implementation of all-combinations-with-replacement here.

Works with: Factor version 0.99 2022-04-03

USING: math.combinatorics prettyprint qw ;

qw{ iced jam plain } 2 all-combinations-with-replacement .

Output:

{
    { "iced" "iced" }
    { "iced" "jam" }
    { "iced" "plain" }
    { "jam" "jam" }
    { "jam" "plain" }
    { "plain" "plain" }
}

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

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

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

# Built-in
UnorderedTuples(["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[0]))
    }
    return r
}

func main() {
    fmt.Println(combrep(2, []string{"iced", "jam", "plain"}))
    fmt.Println(len(combrep(3,
        []string{"1", "2", "3", "4", "5", "6", "7", "8", "9", "10"})))
}

Output:

[[plain plain] [plain jam] [jam jam] [plain iced] [jam iced] [iced iced]]
220

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 []msPair
func (p pairList) Len() int { return len(p) }
func (p pairList) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func (p pairList) Less(i, j int) bool { return p[i].string < p[j].string }

// Function required by task.
func combrep(n int, lst set) msSet {
    if n == 0 {
        var ms multiset
        return msSet{ms.key(): ms}
    }
    if len(lst) == 0 {
        return msSet{}
    }
    var car string
    var cdr set
    for ele := range lst {
        if cdr == nil {
            car = ele
            cdr = make(set)
        } else {
            cdr[ele] = true
        }
    }
    r := combrep(n, cdr)

    for _, x := range combrep(n-1, lst) {
        c := multiset{car: 1}
        for k, v := range x {
            c[k] += v
        }
        r[c.key()] = c
    }
    return r
}

// Driver for examples required by task.
func main() {
    // Input is a set.
    three := set{"iced": true, "jam": true, "plain": true}
    // Output is a set of multisets.  The set is a Go map:
    // The key is a string representation that compares equal
    // for equal multisets.  We ignore this here.  The value
    // is the multiset.  We print this.
    for _, ms := range combrep(2, three) {
        fmt.Println(ms)
    }
    ten := make(set)
    for i := 1; i <= 10; i++ {
        ten[strconv.Itoa(i)] = true
    }
    fmt.Println(len(combrep(3, ten)))
}

Output:

map[plain:1 jam:1]
map[plain:2]
map[iced:1 jam:1]
map[jam:2]
map[iced:1 plain:1]
map[iced:2]
220

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]

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:

--------------- COMBINATIONS WITH REPETITION -------------

combinationsWithRepetition ::
  (Eq a) =>
  Int ->
  [a] ->
  [[a]]
combinationsWithRepetition k xs = cmb k []
  where
    cmb 0 ys = ys
    cmb n [] = cmb (pred n) (pure <$> xs)
    cmb n peers = cmb (pred n) (peers >>= nextLayer)
      where
        nextLayer [] = []
        nextLayer ys@(h : _) =
          (: ys) <$> dropWhile (/= h) xs


-------------------------- TESTS -------------------------
main :: IO ()
main = do
  print $
    combinationsWithRepetition
      2
      ["iced", "jam", "plain"]
  print $ length $ combinationsWithRepetition 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 repetitions
procedure combinations_repetitions (L, n)
  if n = 0
    then suspend [] # if reach 0, then return an empty list
    else if *L > 0
      then {
        # keep the first element
        item := L[1]                                         
        # get all of length n in remaining list
        every suspend (combinations_repetitions (L[2:0], n)) 
        # get all of length n-1 in remaining list
        # and add kept element to make list of size n
        every i := combinations_repetitions (L, n-1) do      
          suspend [item] ||| i                               
      }
end

Test procedure:

# convenience function
procedure write_list (l)
  every (writes (!l || " "))
  write ()
end

# testing routine
procedure main ()
  # display all combinations for 2 of iced/jam/plain
  every write_list (combinations_repetitions(["iced", "jam", "plain"], 2))
  # get a count for number of ways to select 3 items from 10
  every push(num_list := [], 1 to 10)
  count := 0
  every combinations_repetitions(num_list, 3) do count +:= 1
  write ("There are " || count || " possible combinations of 3 from 10")
end

Output:

plain plain 
jam plain 
jam jam 
iced plain 
iced jam 
iced iced 
There are 220 possible combinations of 3 from 10

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=: >@~.@:(/:~&.>)@,@{@# <

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 repetitions
220

J Alternate implementation

Considerably faster:

require 'stats'
rcomb=: (combrep #) { ]

This definition of rcomb behaves identically to the previous one, and combrep calculates indices:

   2 combrep 3
0 0
0 1
0 2
1 1
1 2
2 2

combrep computes 2 comb 4 (note that 4 = (2 + 3)-1) and then subtracts 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[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
    ];

})();

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[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)))
    });
})();

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".chunked(1)
    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))

Lobster

Translation of: C

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

Output:

["iced", "iced"]
["iced", "jam"]
["iced", "plain"]
["jam", "jam"]
["jam", "plain"]
["plain", "plain"]
6
220

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

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

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

DeleteDuplicates[Tuples[{"iced", "jam", "plain"}, 2],Sort[#1] == Sort[#2] &]
->{{"iced", "iced"}, {"iced", "jam"}, {"iced", "plain"}, {"jam", "jam"}, {"jam", "plain"}, {"plain", "plain"}}

Combi[x_, y_] := Binomial[(x + y) - 1, y]
Combi[3, 2]
-> 6
Combi[10, 3]
->220

A better method therefore:

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

In[2]:= CombinWithRep[{"iced", "jam", "plain"}, 2]

Out[2]= {{"iced", "iced"}, {"jam", "jam"}, {"plain", 
  "plain"}, {"iced", "jam"}, {"iced", "plain"}, {"jam", "plain"}}

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

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

Output:

@[@[iced, iced], @[iced, jam], @[iced, plain], @[jam, jam], @[jam, plain], @[plain, plain]]
220

OCaml

Translation of: Haskell

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

in the interactive loop:

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

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

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

Pascal

used in Munchausen_numbers or Own_digits_power_sum

program CombWithRep;
//combinations with repetitions
//Limit = count of elements
//Maxval = value of top , lowest is always 0
//so 0..Maxvalue => maxValue+1 elements
{$IFDEF FPC}
//  {$R+,O+}
  {$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$COPERATORS ON}
{$ELSE}{$APPTYPE CONSOLE}{$ENDIF}
uses
  SysUtils;//GetTickCount64

var
  CombIdx: array of byte;

  function InitCombIdx(ElemCount: Int32): pbyte;
  begin
    setlength(CombIdx, ElemCount + 1);
    Fillchar(CombIdx[0], sizeOf(CombIdx[0]) * (ElemCount + 1), #0);
    Result := @CombIdx[0];
  end;

  function NextCombWithRep(pComb: pByte; MaxVal, ElemCount: UInt32): boolean;
  var
    i, dgt: NativeInt;
  begin
    i := -1;
    repeat
      i += 1;
      dgt := pComb[i];
      if dgt < MaxVal then
        break;
    until i > ElemCount;
    Result := i >= ElemCount;
    dgt +=1;
    repeat
      pComb[i] := dgt;
      i -= 1;
    until i < 0;
  end;

  procedure GetDoughnuts(ElemCount: NativeInt);
  const
    doughnuts: array[0..2] of string = ('iced', 'jam', 'plain');
  var
    pComb: pByte;
    MaxVal, i: Uint32;
  begin
    if ElemCount < 1 then
      EXIT;
    MaxVal := High(doughnuts);
    writeln('Getting ', ElemCount, ' elements of ', MaxVal + 1, ' different');
    pComb := InitCombIdx(ElemCount);
    repeat
      Write('[');
      for i := 0 to ElemCount - 2 do
        Write(pComb[i], ',');
      Write(pComb[ElemCount - 1], ']');
      Write('{');
      for i := 0 to ElemCount - 2 do
        Write(doughnuts[pComb[i]], ',');
      Write(doughnuts[pComb[ElemCount - 1]], '}');
    until NextCombWithRep(pComb, MaxVal, ElemCount);
    writeln(#10);
  end;

  procedure Check(ElemCount: Int32; ElemRange: Uint32);
  var
    pComb: pByte;
    T0: int64;
    rec_cnt: NativeInt;
  begin
    T0 := GetTickCount64;
    rec_cnt := 0;
    ElemRange -= 1;
    pComb := InitCombIdx(ElemCount);
    repeat
      Inc(rec_cnt);
    until NextCombWithRep(pComb, ElemRange, ElemCount);
    T0 := GetTickCount64 - T0;
    writeln('Getting ', ElemCount, ' elements of ', ElemRange + 1, ' different');
    writeln(rec_cnt: 10, t0: 10,' ms');
  end;

begin
  GetDoughnuts(2);
  GetDoughnuts(3);
  Check(3, 10);
  Check(9, 10);
  Check(15, 16);
  {$IFDEF WINDOWS}
  readln;
  {$ENDIF}
end.

Output:

TIO.RUN
Getting 2 elements of 3 different
[0,0]{iced,iced}[1,0]{jam,iced}[2,0]{plain,iced}[1,1]{jam,jam}[2,1]{plain,jam}[2,2]{plain,plain}

Getting 3 elements of 3 different
[0,0,0]{iced,iced,iced}[1,0,0]{jam,iced,iced}[2,0,0]{plain,iced,iced}[1,1,0]{jam,jam,iced}[2,1,0]{plain,jam,iced}[2,2,0]{plain,plain,iced}[1,1,1]{jam,jam,jam}[2,1,1]{plain,jam,jam}[2,2,1]{plain,plain,jam}[2,2,2]{plain,plain,plain}

Getting 3 elements of 10 different
       220         0 ms
Getting 9 elements of 10 different
     48620         0 ms
Getting 15 elements of 16 different
 155117520       735 ms

Perl

The highly readable version:

sub p { $_[0] ? map p($_[0] - 1, [@{$_[1]}, $_[$_]], @_[$_ .. $#_]), 2 .. $#_ : $_[1] }
sub f { $_[0] ? $_[0] * f($_[0] - 1) : 1 }
sub pn{ f($_[0] + $_[1] - 1) / f($_[0]) / f($_[1] - 1) }

for (p(2, [], qw(iced jam plain))) {
        print "@$_\n";
}

printf "\nThere are %d ways to pick 7 out of 10\n", pn(7,10);

Prints:

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

There are 11440 ways to pick 7 out of 10

With a module:

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

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

As of 1.0.2 there is a builtin combinations_with_repetitions() function. Using a string here for simplicity and neater output, but it works with any sequence:

?join(combinations_with_repetitions("ijp",2),',')
?length(combinations_with_repetitions(tagset(10),3))

Output:

"ii,ij,ip,jj,jp,pp"
220

PHP

<?php
  function combos($arr, $k) {
    if ($k == 0) {
      return array(array());
    }
    
    if (count($arr) == 0) {
      return array();
    }
    
    $head = $arr[0];
    
    $combos = array();
    $subcombos = combos($arr, $k-1);
    foreach ($subcombos as $subcombo) {
      array_unshift($subcombo, $head);
      $combos[] = $subcombo;
    }
    array_shift($arr);
    $combos = array_merge($combos, combos($arr, $k));
    return $combos;
  }
  
  $arr = array("iced", "jam", "plain");
  $result = combos($arr, 2);
  foreach($result as $combo) {
    echo implode(' ', $combo), "<br>";
  }
  $donuts = range(1, 10);
  $num_donut_combos = count(combos($donuts, 3));
  echo "$num_donut_combos ways to order 3 donuts given 10 types";
?>

Output:

in the browser

iced iced
iced jam
iced plain
jam jam
jam plain
plain plain
220 ways to order 3 donuts given 10 types

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. 

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

	}
}

?>

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

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

?- [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

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

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

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

• Python documentation

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

Translation of: Haskell

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 String
def 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

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.

( 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

Output:

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

220

R

The idiomatic solution is to just use a library.

library(gtools)
combinations(3, 2, c("iced", "jam", "plain"), set = FALSE, repeats.allowed = TRUE)
nrow(combinations(10, 3, repeats.allowed = TRUE))

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
(define (combinations xs k)
  (cond [(= k 0)     '(())]
        [(empty? xs) '()]
        [(append (combinations (rest xs) k)
                 (map (λ(x) (cons (first xs) x))
                      (combinations xs (- k 1))))]))

Raku

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

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?*/
               @.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

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

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 credit
possible_doughnuts = [*1..1000].repeated_combination(30)
# size returns the size of the enumerator, or nil if it can’t be calculated lazily.
puts "", "#{possible_doughnuts.size} ways to order 30 donuts given 1000 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

5799990040867421088231767567302459508715964845043404147200 ways to order 30 donuts given 1000 types.

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

Output:

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

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

Translation of: Haskell

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

in the interactive loop:

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

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

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.5
proc combrepl {set n {presorted no}} {
    if {!$presorted} {
        set set [lsort $set]
    }
    if {[incr n 0] < 1} {
	return {}
    } elseif {$n < 2} {
	return $set
    }
    # Recursive call
    set res [combrepl $set [incr n -1] yes]
    set result {}
    foreach item $set {
	foreach inner $res {
	    dict set result [lsort [list $item {*}$inner]] {}
	}
    }
    return [dict keys $result]
}

puts [combrepl {iced jam plain} 2]
puts [llength [combrepl {1 2 3 4 5 6 7 8 9 10} 3]]

Output:

{iced iced} {iced jam} {iced plain} {jam jam} {jam plain} {plain plain}
220

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)

VBScript

' 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

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

Concise recursive

Translation of: Go

Produces results in no particular order.

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

Output:

[[plain, plain], [plain, jam], [jam, jam], [plain, iced], [jam, iced], [iced, iced]]
220

Library based

Library: Wren-seq

Library: Wren-perm

Produces results in lexicographic order.

import "./seq" for Lst
import "./perm" for Comb

var a = ["iced", "jam", "plain"]
a = Lst.flatten(Lst.zip(a, a))
System.print(Comb.listDistinct(a, 2))

a = (1..10).toList
a = Lst.flatten(Lst.zip(Lst.zip(a, a), a))
System.print(Comb.listDistinct(a, 3).count)

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 objects
int  D, S, K, N, Names;         \depth of recursion, starting value of N, etc.
int  I;
[if D<K then                    \depth < size
    [for I:= S to N-1 do
        [Array(D):= I;
        Combos(D+1, I, K, N, Names);
        ];
    ]
else [Count:= Count+1;
     if Names(0) then
        [for I:= 0 to K-1 do
            [Text(0, Names(Array(I)));  ChOut(0, ^ )];
        CrLf(0);
        ];
     ];
];

[Count:= 0;
Combos(0, 0, 2, 3, ["iced", "jam", "plain"]);
Text(0, "Combos = ");  IntOut(0, Count);  CrLf(0);
Count:= 0;
Combos(0, 0, 3, 10, [0]);
Text(0, "Combos = ");  IntOut(0, Count);  CrLf(0);
]

Output:

iced iced 
iced jam 
iced plain 
jam jam 
jam plain 
plain plain 
Combos = 6
Combos = 220

zkl

Translation of: Clojure

fcn combosK(k,seq){	// repeats, seq is finite
   if (k==1)    return(seq);
   if (not seq) return(T);
   self.fcn(k-1,seq).apply(T.extend.fp(seq[0])).extend(self.fcn(k,seq[1,*]));
}

combosK(2,T("iced","jam","plain")).apply("concat",",");
combosK(3,T(0,1,2,3,4,5,6,7,8,9)).len();

Output:

L("iced,iced","iced,jam","iced,plain","jam,jam","jam,plain","plain,plain")
220

ZX Spectrum Basic

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