Combinations with repetitions: Difference between revisions

From Rosetta Code
Content added Content deleted
(Corrected position of Scala solution (alphabetical order FTW); added output)
(→‎{{header|Go}}: fixed lang tag)
Line 231: Line 231:


=={{header|Go}}==
=={{header|Go}}==
Using channel and coroutine, showing how to use synced or unsynced communication.<lang Go>package main
Using channel and coroutine, showing how to use synced or unsynced communication.
<lang go>package main


import "fmt"
import "fmt"
Line 288: Line 289:
}
}
fmt.Printf("\npicking 3 of 10: %d\n", count)
fmt.Printf("\npicking 3 of 10: %d\n", count)
}</lang>Output:<lang>plain plain
}</lang>
Output:
<pre>
plain plain
plain jam
plain jam
plain iced
plain iced
Line 295: Line 299:
iced iced
iced iced


picking 3 of 10: 220</lang>
picking 3 of 10: 220
</pre>


=={{header|Haskell}}==
=={{header|Haskell}}==

Revision as of 04:17, 2 December 2011

Task
Combinations with repetitions
You are encouraged to solve this task according to the task description, using any language you may know.

The set of combinations with repetitions is computed from a set, (of cardinality ), and a size of resulting selection, , by reporting the sets of cardinality where each member of those sets is chosen from . In the real world, it is about choosing sets where there is a “large” supply of each type of element and where the order of choice does not matter. For example:

Q: How many ways can a person choose two doughnuts from a store selling three types of doughnut: iced, jam, and plain? (i.e., is , , and .)
A: 6: ; ; ; ; ; .

Note that both the order of items within a pair, and the order of the pairs given in the answer is not significant; the pairs represent multisets.

Task description

  • Write a function/program/routine/.. to generate all the combinations with repetitions of types of things taken at a time and use it to show an answer to the doughnut example above.
  • For extra credit, use the function to compute and show just the number of ways of choosing three doughnuts from a choice of ten types of doughnut. Do not show the individual choices for this part.

References:

Ada

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

combinations.adb: <lang Ada>with Ada.Text_IO; procedure Combinations is 

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

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

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

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

  Donut_Count : constant Natural :=
     Donut_Combinations (Count => 2, Output => True);
  Ten_Count   : constant Natural := Ten_Combinations (Count => 3);

begin 

  Ada.Text_IO.Put_Line ("Total Donuts:" & Natural'Image (Donut_Count));
  Ada.Text_IO.Put_Line ("Total Tens:" & Natural'Image (Ten_Count));

end Combinations;</lang>

Output: 

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

Clojure

Translation of: Scheme

<lang clojure> (defn combinations [coll k] 

 (when-let [[x & xs] coll]
   (if (= k 1)
     (map list coll)
     (concat (map (partial cons x) (combinations coll (dec k)))
             (combinations xs k)))))

</lang>

Example output:

<lang clojure> user> (combinations '[iced jam plain] 2) ((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain)) </lang>

C

<lang C>#include <stdio.h>

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

       int i;
       long count = 0;
       if (n_chosen == len) {
               if (!got) return 1;

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

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

}

int main() { 

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

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

}

</lang>Output:

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

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

D

Using lexicographic next bit permutation to generate combinations with repetitions. <lang d>import std.stdio, std.range ;

struct CombRep { 

   immutable uint nt, nc ;
   private ulong[] combVal;
   this(uint numType, uint numChoice) {
       assert(0 < numType && numType + numChoice <= 64,
           "valid only for nt + nc <= 64 (ulong bit size)") ;
       nt = numType ;
       nc = numChoice ;
       if(nc == 0) return ;
       auto 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 ;
       // 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) {
           combVal ~= v ;
           if(v == 0) break ;
           auto t = (v | (v - 1)) + 1 ; // get next nt-1 bit number
           v = t | ((((t & -t) / (v & -v)) >> 1) - 1) ;
       }
   }
   uint length() @property { return combVal.length ; }
   uint[] opIndex(uint idx) { return val2set(combVal[idx]) ; }
   int opApply(int delegate(ref uint[]) dg) {
       foreach(v;combVal) {
           auto set = val2set(v) ;
           if(dg(set))
               break ;
       }
       return 1 ;
   }
   private uint[] val2set(ulong v) pure {
       // convert bit pattern to selection set
       uint typeIdx = 0, bitLimit = nt + nc - 1 ;
       uint[] set ;
       foreach(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, uint numChoice) 

   if(hasLength!R && isRandomAccessRange!R) {
   ElementType!R[][] result ;
   foreach(s ; CombRep(types.length, numChoice)) {
       ElementType!R[] r ;
       foreach(i ; s)
           r ~= types[i] ;
       result ~= r ;
   }
   return result ;

}

void main() { 

   foreach(e;combRep(["iced","jam","plain"],2))
       writefln("%5s", e) ;
   writefln("Ways to select 3 from 10 types is %d", CombRep(10,3).length) ;

}</lang> output: 

[ iced,  iced]
[ iced,   jam]
[ iced, plain]
[  jam,   jam]
[  jam, plain]
[plain, plain]
Ways to select 3 from 10 types is 220

Go

Using channel and coroutine, showing how to use synced or unsynced communication. <lang go>package main

import "fmt"

func picks(picked []int, pos, need int, c chan[]int, do_wait bool) { if need == 0 { if do_wait { c <- picked <-c } else { // if we want only the count, there's no need to // sync between coroutines; let it clobber the array c <- []int {} } return }

if pos <= 0 { if need == len(picked) { c <- nil } return }

picked[len(picked) - need] = pos - 1 picks(picked, pos, need - 1, c, do_wait) // choose the current donut picks(picked, pos - 1, need, c, do_wait) // or don't }

func main() { donuts := []string {"iced", "jam", "plain" }

picked := make([]int, 2) ch := make(chan []int)

// true: tell the channel to wait for each sending, because // otherwise the picked array may get clobbered before we can do // anything to it go picks(picked, len(donuts), len(picked), ch, true)

var cc []int for { if cc = <-ch; cc == nil { break } for _, i := range cc { fmt.Printf("%s ", donuts[i]) } fmt.Println() ch <- nil // sync }

picked = make([]int, 3) // this time we only want the count, so tell coroutine to keep going // and work the channel buffer go picks(picked, 10, len(picked), ch, false) count := 0 for { if cc = <-ch; cc == nil { break } count++ } fmt.Printf("\npicking 3 of 10: %d\n", count) }</lang> Output: 

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

picking 3 of 10: 220

Haskell

<lang haskell> import Data.List

-- 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 0 _ = [[]] combsWithRep _ [] = [] combsWithRep k xxs@(x:xs) = map (x:) (combsWithRep (k-1) xxs) ++ combsWithRep k xs

countCombsWithRep k = length . combsWithRep k

main = do 

 print $ combsWithRep 2 ["iced","jam","plain"]
 print $ countCombsWithRep 3 [1..10]

</lang>

Example output:

<lang haskell> [["iced","iced"],["iced","jam"],["iced","plain"],["jam","jam"],["jam","plain"],["plain","plain"]] 220 </lang>

Icon and Unicon

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

  1. generate all combinations of length n from list L,
  2. including repetitions

procedure combinations_repetitions (L, n) 

 if n = 0
   then suspend [] # if reach 0, then return an empty list
   else if *L > 0
     then {
       # keep the first element
       item := L[1]                                         
       # get all of length n in remaining list
       every suspend (combinations_repetitions (L[2:0], n)) 
       # get all of length n-1 in remaining list
       # and add kept element to make list of size n
       every i := combinations_repetitions (L, n-1) do      
         suspend [item] ||| i                               
     }

end </lang>

Test procedure:

<lang Icon>

  1. convenience function

procedure write_list (l) 

 every (writes (!l || " "))
 write ()

end

  1. testing routine

procedure main () 

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

end </lang>

Output: 

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

J

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

Example use:

<lang j> 2 rcomb ;:'iced jam plain' ┌─────┬─────┐ │iced │iced │ ├─────┼─────┤ │iced │jam │ ├─────┼─────┤ │iced │plain│ ├─────┼─────┤ │jam │jam │ ├─────┼─────┤ │jam │plain│ ├─────┼─────┤ │plain│plain│ └─────┴─────┘ 

  #3 rcomb i.10         NB. ways to choose 3 items from 10 with replacement

220</lang>

Java

MultiCombinationsTester.java <lang java> import com.objectwave.utility.*;

public class MultiCombinationsTester { 

   public MultiCombinationsTester() throws CombinatoricException {
       Object[] objects = {"iced", "jam", "plain"};
       //Object[] objects = {"abba", "baba", "ab"};
       //Object[] objects = {"aaa", "aa", "a"};
       //Object[] objects = {(Integer)1, (Integer)2, (Integer)3, (Integer)4};
       MultiCombinations mc = new MultiCombinations(objects, 2);
       while (mc.hasMoreElements()) {
           for (int i = 0; i < mc.nextElement().length; i++) {
               System.out.print(mc.nextElement()[i].toString() + " ");
           }
           System.out.println();
       }

       // Extra credit:
       System.out.println("----------");
       System.out.println("The ways to choose 3 items from 10 with replacement = " + MultiCombinations.c(10, 3));
   } // constructor

   public static void main(String[] args) throws CombinatoricException {
       new MultiCombinationsTester();
   }

} // class </lang>

MultiCombinations.java <lang java> import com.objectwave.utility.*; import java.util.*;

public class MultiCombinations { 

   private HashSet<String> set = new HashSet<String>();
   private Combinations comb = null;
   private Object[] nextElem = null;

   public MultiCombinations(Object[] objects, int k) throws CombinatoricException {
       k = Math.max(0, k);
       Object[] myObjects = new Object[objects.length * k];
       for (int i = 0; i < objects.length; i++) {
           for (int j = 0; j < k; j++) {
               myObjects[i * k + j] = objects[i];
           }
       }
       comb = new Combinations(myObjects, k);
   } // constructor

   boolean hasMoreElements() {
       boolean ret = false;
       nextElem = null;
       int oldCount = set.size();
       while (comb.hasMoreElements()) {
           Object[] elem = (Object[]) comb.nextElement();
           String str = "";
           for (int i = 0; i < elem.length; i++) {
               str += ("%" + elem[i].toString() + "~");
           }
           set.add(str);
           if (set.size() > oldCount) {
               nextElem = elem;
               ret = true;
               break;
           }
       }
       return ret;
   } // hasMoreElements()

   Object[] nextElement() {
       return nextElem;
   }

   static java.math.BigInteger c(int n, int k) throws CombinatoricException {
       return Combinatoric.c(n + k - 1, k);
   }

} // class </lang>

Output: 

iced iced 
iced jam 
iced plain 
jam jam 
jam plain 
plain plain 
----------
The ways to choose 3 items from 10 with replacement = 220

JavaScript

<lang javascript><html><head><title>Donuts</title></head>

<body>

<script type="application/javascript">

function disp(x) {
	var e = document.createTextNode(x + '\n');
	document.getElementById('x').appendChild(e);
}

function pick(n, got, pos, from, show) {
	var cnt = 0;
	if (got.length == n) {
		if (show) disp(got.join(' '));
		return 1;
	}
	for (var i = pos; i < from.length; i++) {
		got.push(from[i]);
		cnt += pick(n, got, i, from, show);
		got.pop();
	}
	return cnt;
}

disp(pick(2, [], 0, ["iced", "jam", "plain"], true) + " combos");
disp("pick 3 out of 10: " + pick(3, [], 0, "a123456789".split(), false) + " combos");
</script></body></html></lang>output<lang>iced iced
iced jam
iced plain
jam jam
jam plain
plain plain
6 combos
pick 3 out of 10: 220 combos</lang>



PARI/GP


<lang parigp>ways(k,v,s=[])={
	if(k==0,return([]));
	if(k==1,return(vector(#v,i,concat(s,[v[i]]))));
	if(#v==1,return(ways(k-1,v,concat(s,v))));
	my(u=vecextract(v,2^#v-2));
	concat(ways(k-1,v,concat(s,[v[1]])),ways(k,u,s))
};
xc(k,v)=binomial(#v+k-1,k);
ways(2, ["iced","jam","plain"])</lang>



Perl


The highly readable version:
<lang perl>sub p { $_[0] ? map p($_[0] - 1, [@{$_[1]}, $_[$_]], @_[$_ .. $#_]), 2 .. $#_ : $_[1] }
sub f { $_[0] ? $_[0] * f($_[0] - 1) : 1 }
sub pn{ f($_[0] + $_[1] - 1) / f($_[0]) / f($_[1] - 1) }

for (p(2, [], qw(iced jam plain))) {



       print "@$_\n";



}

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

Prints:



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

There are 11440 ways to pick 7 out of 10


Perl 6


Translation of: Haskell


<lang perl6>proto combs_with_rep (Int, @) {*}

multi combs_with_rep (0,  @)  { [] }
multi combs_with_rep ($,  []) { () }
multi combs_with_rep ($n, [$head, *@tail]) {



   map( { [$head, @^others] },
           combs_with_rep($n - 1, [$head, @tail]) ),
   combs_with_rep($n, @tail);



}

.perl.say for combs_with_rep( 2, [< iced jam plain >] );



  1. Extra credit:


sub postfix:<!> { [*] 1..$^n }
sub combs_with_rep_count ($k, $n) { ($n + $k - 1)! / $k! / ($n - 1)! }

say combs_with_rep_count( 3, 10 );</lang>


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


PicoLisp


<lang PicoLisp>(de combrep (N Lst)



  (cond
     ((=0 N) '(NIL))
     ((not Lst))
     (T
        (conc
           (mapcar
              '((X) (cons (car Lst) X))
              (combrep (dec N) Lst) )
           (combrep N (cdr Lst)) ) ) ) )</lang>



Output:



: (combrep 2 '(iced jam plain))
-> ((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))

: (length (combrep 3 (range 1 10)))
-> 220


PureBasic


<lang PureBasic>Procedure nextCombination(Array combIndex(1), elementCount)



 ;combIndex() must be dimensioned to 'k' - 1, elementCount equals 'n' - 1
 ;combination produced includes repetition of elements and is represented by the array combIndex()
 Protected i, indexValue, combSize = ArraySize(combIndex()), curIndex
 
 ;update indexes
 curIndex = combSize
 Repeat 
   combIndex(curIndex) + 1
   If combIndex(curIndex) > elementCount
     
     curIndex - 1
     If curIndex < 0
       For i = 0 To combSize
         combIndex(i) = 0
       Next 
       ProcedureReturn #False ;array reset to first combination
     EndIf 
     
   ElseIf curIndex < combSize
     
     indexValue = combIndex(curIndex)
     Repeat
       curIndex + 1
       combIndex(curIndex) = indexValue
     Until curIndex = combSize
     
   EndIf
 Until  curIndex = combSize
 
 ProcedureReturn #True ;array contains next combination



EndProcedure

Procedure.s display(Array combIndex(1), Array dougnut.s(1))



 Protected i, elementCount = ArraySize(combIndex()), output.s = "  "
 For i = 0 To elementCount
   output + dougnut(combIndex(i)) + " + "
 Next
 ProcedureReturn Left(output, Len(output) - 3)



EndProcedure

DataSection



 Data.s "iced", "jam", "plain"



EndDataSection

If OpenConsole()



 Define n = 3, k = 2, i, combinationCount
 Dim combIndex(k - 1)
 Dim dougnut.s(n - 1)
 For i = 0 To n - 1: Read.s dougnut(i): Next
 
 PrintN("Combinations of " + Str(k) + " dougnuts taken " + Str(n) + " at a time with repetitions.")
 combinationCount = 0
 Repeat
   PrintN(display(combIndex(), dougnut()))
   combinationCount + 1
 Until Not nextCombination(combIndex(), n - 1)
 PrintN("Total combination count: " + Str(combinationCount))
 
 ;extra credit
 n = 10: k = 3
 Dim combIndex(k - 1)
 combinationCount = 0
 Repeat: combinationCount + 1: Until Not nextCombination(combIndex(), n - 1)
 PrintN(#CRLF$ + "Ways to select " + Str(k) + " items from " + Str(n) + " types: " + Str(combinationCount))
 
 Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
 CloseConsole()



EndIf </lang>The nextCombination() procedure operates on an array of indexes to produce the next combination.  This generalization allows producing a combination from any collection of elements.  nextCombination() returns the value #False when the indexes have reach their maximum values and are then reset.

Sample output:



Combinations of 2 dougnuts taken 3 at a time with repetitions.
  iced + iced
  iced + jam
  iced + plain
  jam + jam
  jam + plain
  plain + plain
Total combination count: 6

Ways to select 3 items from 10 types: 220


Python


<lang python>>>> from itertools import combinations_with_replacement
>>> n, k = 'iced jam plain'.split(), 2
>>> list(combinations_with_replacement(n,k))
[('iced', 'iced'), ('iced', 'jam'), ('iced', 'plain'), ('jam', 'jam'), ('jam', 'plain'), ('plain', 'plain')]
>>> # Extra credit
>>> len(list(combinations_with_replacement(range(10), 3)))
220
>>> </lang>

References:




REXX


<lang rexx>
/*REXX program shows a set of combinations with repetitions. */

stores=3
doughnuts=2



                   /*the following uses a subroutine ($PERMSETS) that  */
                   /*can calculat  PermSets,  CombSets,  or  rCombSets,*/
                   /*depending on the setting of the   F  variable.    */



f='RCOMBSETS'
sep=','
list=$permsets(stores,doughnuts,sep,"iced jam plain")



 do j=1 for words(list)
 say center(word(list,j),30)
 end
                  /*The task was to use the same function to calculate */
                  /*   the number of ways of choosing three doughnuts  */
                  /*   from a choice of ten types of doughnuts.        */
                  /*It would be simplier to use the RCOMB function.    */
   types=10



doughnuts=3
list=$permsets(types,doughnuts)
say
say 'Number of ways to choose three doughnuts from ten types: ' words(list)
say 'Number of ways to choose 3 doughnuts from a choice of 10:' rcomb(10,3)
exit



/*────────────────────────────────$PERMSETS subroutine──────────────────*/
$permsets: procedure expose f               /*gen COMB or PERM sets.    */
@abc='abcdefghijklmnopqrstuvwxyz'; @abcu=@abc; upper @abcu
@abcs=@abcu||@abc; @0abcs=123456789||@abcs
parse arg x,y,between,usyms                 /*take X things Y at a time.*/



                                      /*X can't be >  length(@0abcs).  */



@.=
$.=
sep=
k=0
@0abcs_=@0abcs||xrange(' ','fe'x)
!=' '



do j=1 for words(usyms)                    /*build list of symbols.    */
_=word(usyms,j)                            /*get a user symbol.        */
if wordpos(_,!)\==0 then iterate
k=k+1
$.k=_                                      /*append to the sumbol list.*/
!=! _
if length(_)\==1 then sep='-'
end



  do j=1 for x while k<x
  _=substr(@0abcs_,j,1)                    /*get a character for symbol*/
  if wordpos(_,!)\==0 then iterate
  k=k+1
  $.k=_                                    /*append to the sumbol list.*/
  !=! _
  end



!=
if between== then between=sep             /*use appropriate seperator.*/
return $permgen(1)



/*────────────────────────────────$PERMGEN subroutine───────────────────*/
$permgen: procedure expose @. $. ! between x y f; parse arg ?
_=left(f,1)
fr=_=='R'
fc=_=='C'|fr

if ?>y then do



           c=@.1; _=$.c
               do j=2 to y
               c=@.j; _=_||between||$.c
               end
           !=! _
           end
      else do
           e=x
           if fc then if \fr & ?==1 then e=x-1
              do q=1 for e
                  do k=1 for ?-1
                  if \fr then if @.k==q then iterate q
                  if fc then if q<@.k then iterate q
                  end
              @.?=q
              call $permgen(?+1) /*construction permutation recursively*/
              end
           end



return strip(!)



/*────────────────────────────────RCOMB subroutine──────────────────────*/
rcomb: procedure; arg x,y; return $comb(x+y-1,y)



/*────────────────────────────────$COMB subroutine──────────────────────*/
$comb: procedure; arg x,y; if x=y then return 1; if y>x then return 0;
if x-y<y then y=x-y; _=1; do j=x-y+1 to x; _=_*j; end; return _/$fact(y)



/*────────────────────────────────$FACT subroutine──────────────────────*/
$fact: procedure; parse arg x; !=1; do j=2 to x; !=!*j; end; return !
</lang>
Output:



          iced,iced
           iced,jam
          iced,plain
           jam,jam
          jam,plain
         plain,plain

Number of ways to choose three doughnuts from ten types:  220
Number of ways to choose 3 doughnuts from a choice of 10: 220



Ruby


Ruby 1.9.2
<lang ruby>
possible_doughnuts = ['iced', 'jam', 'plain'].repeated_combination(2)
puts "There are #{possible_doughnuts.count} possible doughnuts:"
possible_doughnuts.each{|doughnut_combi| puts doughnut_combi.join(' and ')}

</lang>
Output:



There are 6 possible doughnuts:
iced and iced
iced and jam
iced and plain
jam and jam
jam and plain
plain and plain



Scala


Scala has a combinations method in the standard library.
<lang scala>
object CombinationsWithRepetition {



 def multi[A](as: List[A], k: Int): List[List[A]] = 
   (List.fill(k)(as)).flatten.combinations(k).toList
 
 def main(args: Array[String]): Unit = {
   val doughnuts = multi(List("iced", "jam", "plain"), 2)
   for (combo <- doughnuts) println(combo.mkString(","))
 
   val bonus = multi(List(0,1,2,3,4,5,6,7,8,9), 3).size
   println("There are "+bonus+" ways to choose 3 items from 10 choices")
 }



}
</lang>

Output



iced,iced
iced,jam
iced,plain
jam,jam
jam,plain
plain,plain
There are 220 ways to choose 3 items from 10 choices


Scheme


Translation of: PicoLisp


<lang scheme>
(define combinations



 (lambda (lst k)
   (cond ((null? lst) '())
         ((= k 1) (map list lst))
         (else
          (append
           (map
            (lambda (x)
              (cons (car lst) x))
            (combinations lst (- k 1)))
           (combinations (cdr lst) k))))))



</lang>






Tcl


<lang tcl>package require Tcl 8.5
proc combrepl {set n {presorted no}} {



   if {!$presorted} {
       set set [lsort $set]
   }
   if {[incr n 0] < 1} {



	return {}



   } elseif {$n < 2} {



	return $set



   }
   # Recursive call
   set res [combrepl $set [incr n -1] yes]
   set result {}
   foreach item $set {



	foreach inner $res {
	    dict set result [lsort [list $item {*}$inner]] {}
	}



   }
   return [dict keys $result]



}

puts [combrepl {iced jam plain} 2]
puts [llength [combrepl {1 2 3 4 5 6 7 8 9 10} 3]]</lang>
Output:



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



Ursala


<lang Ursala>#import std



  1. import nat


cwr = ~&s+ -<&*+ ~&K0=>&^|DlS/~& iota     # takes a set and a selection size



  1. cast %gLSnX


main = ^|(~&,length) cwr~~/(<'iced','jam','plain'>,2) ('1234567890',3)</lang>
output:



(
   {
      <'iced','iced'>,
      <'iced','jam'>,
      <'iced','plain'>,
      <'jam','jam'>,
      <'jam','plain'>,
      <'plain','plain'>},
   220)



Retrieved from "https://rosettacode.org/wiki/Combinations_with_repetitions?oldid=165102"