⚠️ Warning: This is a draft ⚠️
This means it might contain formatting issues, incorrect code, conceptual problems, or other severe issues.
If you want to help to improve and eventually enable this page, please fork RosettaGit's repository and open a merge request on GitHub.
{{task|Discrete math}}
The set of combinations with repetitions is computed from a set, (of cardinality ), and a size of resulting selection, , by reporting the sets of cardinality where each member of those sets is chosen from . In the real world, it is about choosing sets where there is a “large” supply of each type of element and where the order of choice does not matter. For example: :Q: How many ways can a person choose two doughnuts from a store selling three types of doughnut: iced, jam, and plain? (i.e., is , , and .)
:A: 6: {iced, iced}; {iced, jam}; {iced, plain}; {jam, jam}; {jam, plain}; {plain, plain}.
Note that both the order of items within a pair, and the order of the pairs given in the answer is not significant; the pairs represent multisets.
Also note that ''doughnut'' can also be spelled ''donut''.
;Task:
- Write a function/program/routine/.. to generate all the combinations with repetitions of types of things taken at a time and use it to ''show'' an answer to the doughnut example above.
- For extra credit, use the function to compute and show ''just the number of ways'' of choosing three doughnuts from a choice of ten types of doughnut. Do not show the individual choices for this part.
;References:
- [[wp:Combination|k-combination with repetitions]]
;See also: {{Template:Combinations and permutations}}
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;
{{out}}
ICED+ICED
ICED+JAM
ICED+PLAIN
JAM+JAM
JAM+PLAIN
PLAIN+PLAIN
Total Donuts: 6
Total Tens: 220
AppleScript
{{Trans|Haskell}} {{Trans|Python}}
-- combsWithRep :: Int -> [a] -> [kTuple a]
on combsWithRep(k, xs)
-- A list of lists, representing
-- sets of cardinality k, with
-- members drawn from xs.
script combsBySize
script f
on |λ|(a, x)
script prefix
on |λ|(z)
{x} & z
end |λ|
end script
script go
on |λ|(ys, xs)
xs & map(prefix, ys)
end |λ|
end script
scanl1(go, a)
end |λ|
end script
on |λ|(xs)
foldl(f, {{{}}} & take(k, |repeat|({})), xs)
end |λ|
end script
|Just| of |index|(|λ|(xs) of combsBySize, 1 + k)
end combsWithRep
-- TEST ---------------------------------------------------
on run
{length of combsWithRep(3, enumFromTo(0, 9)), ¬
combsWithRep(2, {"iced", "jam", "plain"})}
end run
-- GENERIC ------------------------------------------------
-- Just :: a -> Maybe 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
{{Out}}
{220, {{"iced", "iced"}, {"jam", "iced"}, {"jam", "jam"}, {"plain", "iced"}, {"plain", "jam"}, {"plain", "plain"}}}
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
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%
{{out}}
Choices of 2 from 3:
iced iced
iced jam
iced plain
jam jam
jam plain
plain plain
Total choices = 6
Choices of 3 from 10:
Total choices = 220
Bracmat
This minimalist solution expresses the answer as a sum of products. Bracmat automatically normalises such expressions: terms and factors are sorted alphabetically, products containing a sum as a factor are decomposed in a sum of factors (unless the product is not itself term in a multiterm expression). Like factors are converted to a single factor with an appropriate exponent, so ice^2 is to be understood as ice twice.
( ( choices
= n things thing result
. !arg:(?n.?things)
& ( !n:0&1
| 0:?result
& ( !things
: ?
( %?`thing ?:?things
& !thing*choices$(!n+-1.!things)+!result
: ?result
& ~
)
| !result
)
)
)
& out$(choices$(2.iced jam plain))
& out$(choices$(3.iced jam plain butter marmite tahin fish salad onion grass):?+[?N&!N)
);
{{out}}
iced^2+jam^2+plain^2+iced*jam+iced*plain+jam*plain
220
C
#include <stdio.h>
const char * donuts[] = { "iced", "jam", "plain", "something completely different" };
long choose(int * got, int n_chosen, int len, int at, int max_types)
{
int i;
long count = 0;
if (n_chosen == len) {
if (!got) return 1;
for (i = 0; i < len; i++)
printf("%s\t", donuts[got[i]]);
printf("\n");
return 1;
}
for (i = at; i < max_types; i++) {
if (got) got[n_chosen] = i;
count += choose(got, n_chosen + 1, len, i, max_types);
}
return count;
}
int main()
{
int chosen[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;
}
{{out}}
iced iced
iced jam
iced plain
jam jam
jam plain
plain plain
Were there ten donuts, we'd have had 220 choices of three
C++
Non recursive version.
#include <cstdio>
#include <vector>
#include <string>
using namespace std;
void print_vector(const vector<int> &v, size_t n, const vector<string> &s){
for (size_t i = 0; i < n; ++i)
printf("%s\t", s[v[i]].c_str());
printf("\n");
}
void combination_with_repetiton(int sabores, int bolas, const vector<string>& v_sabores){
sabores--;
vector<int> v(bolas+1, 0);
while (true){
for (int i = 0; i < bolas; ++i){ //vai um
if (v[i] > sabores){
v[i + 1] += 1;
for (int k = i; k >= 0; --k){
v[k] = v[i + 1];
}
//v[i] = v[i + 1];
}
}
if (v[bolas] > 0)
break;
print_vector(v, bolas, v_sabores);
v[0] += 1;
}
}
int main(){
vector<string> options{ "iced", "jam", "plain" };
combination_with_repetiton(3, 2, options);
return 0;
}
{{out}}
iced iced
jam iced
plain iced
jam jam
plain jam
plain plain
C#
{{trans|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;
}
}
{{out}}
iced iced
iced jam
iced plain
jam jam
jam plain
plain plain
220 ways to order 3 donuts given 10 types
Recursive version
using System;
class MultiCombination
{
static string [] set = { "iced", "jam", "plain" };
static int k = 2, n = set.Length;
static string [] buf = new string [k];
static void Main()
{
rec(0, 0);
}
static void rec(int ind, int begin)
{
for (int i = begin; i < n; i++)
{
buf [ind] = set[i];
if (ind + 1 < k) rec(ind + 1, i);
else Console.WriteLine(string.Join(",", buf));
}
}
}
Clojure
{{trans|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)))))
{{out}}
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"
{{out}}
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))))))
{{out}}
((:ICED :ICED) (:ICED :JAM) (:ICED :PLAIN) (:JAM :JAM) (:JAM :PLAIN) (:PLAIN :PLAIN))
Crystal
{{trans|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."
{{out}}
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 [http://www.graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation 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);
}
{{out}}
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;
}
{{out}}
[["iced", "iced"], ["iced", "jam"], ["iced", "plain"], ["jam", "jam"], ["jam", "plain"], ["plain", "plain"]]
220
EasyLang
func output . . n_results += 1 if len items$[] > 0 s$ = "" for i range k s$ &= items$[result[i]] & " " . print s$ . . func combine pos val . . if pos = k call output else for i = val to n - 1 result[pos] = i call combine pos + 1 i . . . call combine 0 0
n = 10 k = 3 len result[] k items$[] = [ ] n_results = 0 call combine 0 0 print "" print n_results & " results with 10 donuts"
{{out}}
```txt
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"}))
{{out}}
{[|"iced" "iced"|] [|"iced" "jam"|] [|"jam" "jam"|] [|"iced" "plain"|] [|"jam" "plain"|] [|"plain" "plain"|]}
Elixir
{{trans|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)))}"
{{out}}
[: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).
{{out}}
94> comb:comb_rep(2,[iced,jam,plain]).
[[iced,iced],
[iced,jam],
[iced,plain],
[jam,jam],
[jam,plain],
[plain,plain]]
95> length(comb:comb_rep(3,lists:seq(1,10))).
220
Fortran
program main
integer :: chosen(4)
integer :: ssize
character(len=50) :: donuts(4) = [ "iced", "jam", "plain", "something completely different" ]
ssize = choose( chosen, 2, 3 )
write(*,*) "Total = ", ssize
contains
recursive function choose( got, len, maxTypes, nChosen, at ) result ( output )
integer :: got(:)
integer :: len
integer :: maxTypes
integer :: output
integer, optional :: nChosen
integer, optional :: at
integer :: effNChosen
integer :: effAt
integer :: i
integer :: counter
effNChosen = 1
if( present(nChosen) ) effNChosen = nChosen
effAt = 1
if( present(at) ) effAt = at
if ( effNChosen == len+1 ) then
do i=1,len
write(*,"(A10,5X)", advance='no') donuts( got(i)+1 )
end do
write(*,*) ""
output = 1
return
end if
counter = 0
do i=effAt,maxTypes
got(effNChosen) = i-1
counter = counter + choose( got, len, maxTypes, effNChosen + 1, i )
end do
output = counter
return
end function choose
end program main
{{out}}
iced iced
iced jam
iced plain
jam jam
jam plain
plain plain
Total = 6
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"})))
}
{{out}}
[[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)
}
{{out}}
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)))
}
{{out}}
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]
{{out}}
[["iced","iced"],["iced","jam"],["iced","plain"],["jam","jam"],["jam","plain"],["plain","plain"]]
220
Dynamic Programming
The first solution is inefficient because it repeatedly calculates the same subproblem in different branches of recursion. For example, combsWithRep k (x:xs) involves computing combsWithRep (k-1) (x:xs) and combsWithRep k xs, both of which (separately) compute combsWithRep (k-1) xs. To avoid repeated computation, we can use dynamic programming:
combsWithRep :: Int -> [a] -> [[a]]
combsWithRep k xs = combsBySize xs !! k
where
combsBySize = foldr f ([[]] : repeat [])
f x = scanl1 $ (++) . map (x :)
main :: IO ()
main = print $ combsWithRep 2 ["iced", "jam", "plain"]
and another approach, using manual recursion:
combsWithRep
:: (Eq a)
=> Int -> [a] -> [[a]]
combsWithRep k xs = comb k []
where
comb 0 lst = lst
comb n [] = comb (n - 1) (pure <$> xs)
comb n peers =
let nextLayer ys@(h:_) = (: ys) <$> dropWhile (/= h) xs
in comb (n - 1) (foldMap nextLayer peers)
main :: IO ()
main = do
print $ combsWithRep 2 ["iced", "jam", "plain"]
print $ length $ combsWithRep 3 [0 .. 9]
{{Out}}
[["iced","iced"],["jam","iced"],["plain","iced"],["jam","jam"],["plain","jam"],["plain","plain"]]
220
=={{header|Icon}} and {{header|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
{{out}}
plain plain
jam plain
jam jam
iced plain
iced jam
iced iced
There are 220 possible combinations of 3 from 10
=={{header|IS-BASIC}}==
## 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.
```j>rcomb=:
@~.@:(/:~&.>)@,@{@# <
Example use:
2 rcomb ;:'iced jam plain'
┌─────┬─────┐
│iced │iced │
├─────┼─────┤
│iced │jam │
├─────┼─────┤
│iced │plain│
├─────┼─────┤
│jam │jam │
├─────┼─────┤
│jam │plain│
├─────┼─────┤
│plain│plain│
└─────┴─────┘
#3 rcomb i.10 NB. # ways to choose 3 items from 10 with repetitions
220
J Alternate implementation
Considerably faster:
require 'stats'
combr=: i.@[ -"1~ [ comb + - 1:
rcomb=: (combr #) { ]
rcomb functions identically, and combr calculates indices:
2 combr 3
0 0
0 1
0 2
1 1
1 2
2 2
In other words: we compute 2 comb 4 (note that 4 = (2 + 3)-1) and then subtract from each column the minimum value in each column (i. 2).
Java
'''MultiCombinationsTester.java'''
import com.objectwave.utility.*;
public class MultiCombinationsTester {
public MultiCombinationsTester() throws CombinatoricException {
Object[] objects = {"iced", "jam", "plain"};
//Object[] objects = {"abba", "baba", "ab"};
//Object[] objects = {"aaa", "aa", "a"};
//Object[] objects = {(Integer)1, (Integer)2, (Integer)3, (Integer)4};
MultiCombinations mc = new MultiCombinations(objects, 2);
while (mc.hasMoreElements()) {
for (int i = 0; i < mc.nextElement().length; i++) {
System.out.print(mc.nextElement()[i].toString() + " ");
}
System.out.println();
}
// Extra credit:
System.out.println("----------");
System.out.println("The ways to choose 3 items from 10 with replacement = " + MultiCombinations.c(10, 3));
} // constructor
public static void main(String[] args) throws CombinatoricException {
new MultiCombinationsTester();
}
} // class
'''MultiCombinations.java'''
import com.objectwave.utility.*;
import java.util.*;
public class MultiCombinations {
private HashSet<String> set = new HashSet<String>();
private Combinations comb = null;
private Object[] nextElem = null;
public MultiCombinations(Object[] objects, int k) throws CombinatoricException {
k = Math.max(0, k);
Object[] myObjects = new Object[objects.length * k];
for (int i = 0; i < objects.length; i++) {
for (int j = 0; j < k; j++) {
myObjects[i * k + j] = objects[i];
}
}
comb = new Combinations(myObjects, k);
} // constructor
boolean hasMoreElements() {
boolean ret = false;
nextElem = null;
int oldCount = set.size();
while (comb.hasMoreElements()) {
Object[] elem = (Object[]) comb.nextElement();
String str = "";
for (int i = 0; i < elem.length; i++) {
str += ("%" + elem[i].toString() + "~");
}
set.add(str);
if (set.size() > oldCount) {
nextElem = elem;
ret = true;
break;
}
}
return ret;
} // hasMoreElements()
Object[] nextElement() {
return nextElem;
}
static java.math.BigInteger c(int n, int k) throws CombinatoricException {
return Combinatoric.c(n + k - 1, k);
}
} // class
{{out}}
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=
<body><pre id='x'>