Combinations with repetitions: Difference between revisions
→Concise recursive: Changed to Wren S/H
(→{{header|Perl}}: Add a module) |
(→Concise recursive: Changed to Wren S/H) |
||
| (165 intermediate revisions by 64 users not shown) | |||
Line 1:
{{task|Discrete math}}
The set of combinations with repetitions is computed from a set, <math>S</math> (of cardinality <math>n</math>), and a size of resulting selection, <math>k</math>, by reporting the sets of cardinality <math>k</math> where each member of those sets is chosen from <math>S</math>.
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., <math>S</math> is <math>\{\mathrm{iced}, \mathrm{jam}, \mathrm{plain}\}</math>, <math>|S| = 3</math>, and <math>k = 2</math>.)
Line 8 ⟶ 11:
<br><small>Also note that ''doughnut'' can also be spelled ''donut''.</small>
;Task:
* Write a function/program/routine/.. to generate all the combinations with repetitions of <math>n</math> types of things taken <math>k</math> 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}}
<br><br>
=={{header|11l}}==
{{trans|Nim}}
<syntaxhighlight lang="11l">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)</syntaxhighlight>
{{out}}
<pre>
[[iced, iced], [iced, jam], [iced, plain], [jam, jam], [jam, plain], [plain, plain]]
220
</pre>
=={{header|360 Assembly}}==
<syntaxhighlight lang="360asm">* Combinations with repetitions - 16/04/2019
COMBREP CSECT
USING COMBREP,R13 base register
B 72(R15) skip savearea
DC 17F'0' savearea
SAVE (14,12) save previous context
ST R13,4(R15) link backward
ST R15,8(R13) link forward
LR R13,R15 set addressability
MVC FLAVORS(9),SET1 flavors=3,draws=2,tell=1
BAL R14,COMBINE call combine
MVC FLAVORS(9),SET2 flavors=10,draws=3,tell=0
BAL R14,COMBINE call combine
L R13,4(0,R13) restore previous savearea pointer
RETURN (14,12),RC=0 restore registers from calling sav
COMBINE SR R9,R9 n=0
MVI V,X'00' ~
MVC V+1(NN*L'V-1),V v=0
IF CLI,TELL,EQ,X'01' THEN if tell then
XPRNT =C'list:',5 print
ENDIF , endif
LOOP LA R6,1 i=1
DO WHILE=(C,R6,LE,DRAWS) do i=1 to draws
LR R1,R6 i
SLA R1,2 ~
L R2,V-4(R1) v(i)
L R3,FLAVORS flavors
BCTR R3,0 flavors-1
IF CR,R2,GT,R3 THEN if v(i)>flavors-1 then
LR R1,R6 i
SLA R1,2 ~
LA R1,V(R1) @v(i+1)
L R2,0(R1) v(i+1)
LA R2,1(R2) v(i+1)+1
ST R2,0(R1) v(i+1)=v(i+1)+1
LR R7,R6 j=i
DO WHILE=(C,R7,GE,=A(1)) do j=i to 1 by -1
LR R1,R6 i
SLA R1,2 ~
L R2,V(R1) v(i+1)
LR R1,R7 j
SLA R1,2 ~
ST R2,V-4(R1) v(j)=v(i+1)
BCTR R7,0 j--
ENDDO , enddo j
ENDIF , endif
LA R6,1(R6) i++
ENDDO , enddo i
L R1,DRAWS draws
LA R1,1(R1) draws+1
SLA R1,2 ~
L R2,V-4(R1) v(draws+1)
LTR R2,R2 if v(draws+1)>0
BP EXITLOOP then exit loop
LA R9,1(R9) n=n+1
IF CLI,TELL,EQ,X'01' THEN if tell then
MVC BUF,=CL60' ' buf=' '
LA R10,1 ibuf=1
LA R6,1 i=1
DO WHILE=(C,R6,LE,DRAWS) do i=1 to draws
LR R1,R6 i
SLA R1,2 ~
L R1,V-4(R1) v(i)
MH R1,=AL2(L'ITEMS) ~
LA R4,ITEMS(R1) @items(v(i)+1)
LA R5,BUF-1 @buf-1
AR R5,R10 +ibuf
MVC 0(6,R5),0(R4) substr(buf,ibuf,6)=items(v(i)+1)
LA R10,L'ITEMS(R10) ibuf=ibuf+length(items)
LA R6,1(R6) i++
ENDDO , enddo i
XPRNT BUF,L'BUF print buf
ENDIF , endif
L R2,V v(1)
LA R2,1(R2) v(1)+1
ST R2,V v(1)=v(1)+1
B LOOP loop
EXITLOOP L R1,FLAVORS flavors
XDECO R1,XDEC edit flavors
MVC PG+4(2),XDEC+10 output flavors
L R1,DRAWS draws
XDECO R1,XDEC edit draws
MVC PG+7(2),XDEC+10 output draws
XDECO R9,PG+11 edit & output n
XPRNT PG,L'PG print buffer
BR R14 return
NN EQU 16
ITEMS DC CL6'iced',CL6'jam',CL6'plain'
FLAVORS DS F
DRAWS DS F
TELL DS X
SET1 DC F'3',F'2',X'01' flavors=3,draws=2,tell=1
SET2 DC F'10',F'3',X'00' flavors=10,draws=3,tell=0
V DS (NN)F v(nn)
BUF DS CL60 buf
PG DC CL40'cwr(..,..)=............'
XDEC DS CL12 temp for xdeco
REGEQU
END COMBREP </syntaxhighlight>
{{out}}
<pre>
list:
iced iced
jam iced
plain iced
jam jam
plain jam
plain plain
cwr( 3, 2)= 6
cwr(10, 3)= 220
</pre>
=={{header|Acornsoft Lisp}}==
{{trans|Scheme}}
<syntaxhighlight lang="lisp">
(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)
</syntaxhighlight>
{{Out}}
<pre>
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
</pre>
=={{header|Action!}}==
<syntaxhighlight lang="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</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Combinations_with_repetitions.png Screenshot from Atari 8-bit computer]
<pre>
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
</pre>
=={{header|Ada}}==
Should work for any discrete type: integer, modular, or enumeration.
combinations.adb:
<
procedure Combinations is
Line 84 ⟶ 362:
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}}
<pre>ICED+ICED
ICED+JAM
Line 96 ⟶ 374:
Total Tens: 220</pre>
=={{header|
{{Trans|Haskell}}
{{Trans|Python}}
<syntaxhighlight lang="applescript">--------------- 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</syntaxhighlight>
{{Out}}
<pre>{220, {{"iced", "iced"}, {"jam", "iced"}, {"jam", "jam"}, {"plain", "iced"}, {"plain", "jam"}, {"plain", "plain"}}}</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">print combine.repeated.by:2 ["iced" "jam" "plain"]
print combine.count.repeated.by:3 @1..10</syntaxhighlight>
{{out}}
<pre>[iced iced] [iced jam] [iced plain] [jam jam] [jam plain] [plain plain]
220</pre>
=={{header|AutoHotkey}}==
<syntaxhighlight lang="autohotkey">;===========================================================
; based on "https://www.geeksforgeeks.org/combinations-with-repetitions/"
;===========================================================
CombinationRepetition(arr, k:=0, Delim:="") {
CombinationRepetitionUtil(arr, k?k:str.count(), Delim, [k+1], result:=[])
return result
} ;===========================================================
CombinationRepetitionUtil(arr, k, Delim, chosen, result , index:=1, start:=1){
line := [], i:=0, res := ""
if (index = k+1){
while (++i <= k)
res .= arr[chosen[i]] Delim, line.push(arr[chosen[i]])
return result.Push(Trim(res, Delim))
}
i:=start
while (i <= arr.count())
chosen[Index]:=i, CombinationRepetitionUtil(arr, k, Delim, chosen, result, index+1, i++)
} ;===========================================================</syntaxhighlight>
Examples:<syntaxhighlight lang="autohotkey">result := CombinationRepetition(["iced","jam","plain"], 2, " + ")
for k, v in result
res .= v "`n"
res := trim(res, ",") "`n"
MsgBox % result.count() " Combinations with Repetition found:`n" res
MsgBox % CombinationRepetition([0,1,2,3,4,5,6,7,8,9], 3).Count()</syntaxhighlight>
Outputs:<pre>---------------------------
6 Combinations with Repetition found:
iced + iced
iced + jam
iced + plain
jam + jam
jam + plain
plain + plain
---------------------------
220
---------------------------</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f COMBINATIONS_WITH_REPETITIONS.AWK
BEGIN {
n = split("iced,jam,plain",donuts,",")
for (i=1; i<=n; i++) {
for (j=1; j<=n; j++) {
if (donuts[i] < donuts[j]) {
key = sprintf("%s %s",donuts[i],donuts[j])
}
else {
key = sprintf("%s %s",donuts[j],donuts[i])
}
arr[key]++
}
}
cmd = "SORT"
for (i in arr) {
printf("%s\n",i) | cmd
choices++
}
close(cmd)
printf("choices = %d\n",choices)
exit(0)
}
</syntaxhighlight>
<p>output:</p>
<pre>
iced iced
iced jam
iced plain
jam jam
jam plain
plain plain
choices = 6
</pre>
=={{header|BASIC}}==
==={{header|BASIC256}}===
<syntaxhighlight lang="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</syntaxhighlight>
==={{header|BBC BASIC}}===
{{works with|BBC BASIC for Windows}}
<
list$() = "iced", "jam", "plain"
PRINT "Choices of 2 from 3:"
Line 124 ⟶ 728:
c% += FNchoose(n% + 1, l%, i%, m%, g%(), n$())
NEXT
= c%</
{{out}}
<pre>
Choices of 2 from 3:
Line 139 ⟶ 743:
Total choices = 220
</pre>
==={{header|IS-BASIC}}===
<syntaxhighlight lang="is-basic">100 PROGRAM "Combinat.bas"
110 READ N
120 STRING D$(1 TO N)*5
130 FOR I=1 TO N
140 READ D$(I)
150 NEXT
160 FOR I=1 TO N
170 FOR J=I TO N
180 PRINT D$(I);" ";D$(J)
190 NEXT
200 NEXT
210 DATA 3,iced,jam,plain</syntaxhighlight>
=={{header|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 <code>ice^2</code> is to be understood as ice twice.
<
= n things thing result
. !arg:(?n.?things)
Line 160 ⟶ 778:
& out$(choices$(2.iced jam plain))
& out$(choices$(3.iced jam plain butter marmite tahin fish salad onion grass):?+[?N&!N)
);</
{{out}}
<pre>iced^2+jam^2+plain^2+iced*jam+iced*plain+jam*plain
220</pre>
=={{header|
Non recursive solution
<syntaxhighlight lang="c">
#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;
}
</syntaxhighlight>
<syntaxhighlight lang="c">#include <stdio.h>
const char * donuts[] = { "iced", "jam", "plain", "something completely different" };
Line 217 ⟶ 854:
return 0;
}
</syntaxhighlight>
{{out}}<pre>iced iced
iced jam
iced plain
Line 226 ⟶ 864:
Were there ten donuts, we'd have had 220 choices of three</pre>
=={{header|
{{trans|PHP}}
<syntaxhighlight lang="csharp">
using System;
using System.Collections.Generic;
using System.Linq;
public static class MultiCombinations
{
private static void Main()
{
var set = new List<string> { "iced", "jam", "plain" };
var combinations = GenerateCombinations(set, 2);
foreach (var combination in combinations)
{
string combinationStr = string.Join(" ", combination);
Console.WriteLine(combinationStr);
}
var donuts = Enumerable.Range(1, 10).ToList();
int donutsCombinationsNumber = GenerateCombinations(donuts, 3).Count;
Console.WriteLine("{0} ways to order 3 donuts given 10 types", donutsCombinationsNumber);
}
private static List<List<T>> GenerateCombinations<T>(List<T> combinationList, int k)
{
var combinations = new List<List<T>>();
if (k == 0)
{
var emptyCombination = new List<T>();
combinations.Add(emptyCombination);
return combinations;
}
if (combinationList.Count == 0)
{
return combinations;
}
T head = combinationList[0];
var copiedCombinationList = new List<T>(combinationList);
List<List<T>> subcombinations = GenerateCombinations(copiedCombinationList, k - 1);
foreach (var subcombination in subcombinations)
{
subcombination.Insert(0, head);
combinations.Add(subcombination);
}
combinationList.RemoveAt(0);
combinations.AddRange(GenerateCombinations(combinationList, k));
return combinations;
}
}
</syntaxhighlight>
{{out}}
<pre>
iced
iced
iced
jam
jam
plain
220 ways to order 3 donuts given 10 types
</pre>
Recursive version
<syntaxhighlight lang="csharp">
using System;
class MultiCombination
{
static string [] set = { "iced", "jam", "plain" };
static int k = 2, n = set.Length;
static string [] buf = new string [k];
static void Main()
{
rec(0, 0);
}
static void rec(int ind, int begin)
{
for (int i = begin; i < n; i++)
{
buf [ind] = set[i];
if (ind + 1 < k) rec(ind + 1, i);
else Console.WriteLine(string.Join(",", buf));
}
}
}
</syntaxhighlight>
=={{header|C++}}==
Non recursive version.
<syntaxhighlight lang="cpp">
#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;
}
</syntaxhighlight>
{{out}}
<pre>
iced iced
iced jam
iced plain
jam jam
jam plain
plain plain
</pre>
=={{header|Clojure}}==
{{trans|Scheme}}
<syntaxhighlight 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)))))
</syntaxhighlight>
{{out}}
<pre>
user> (combinations '[iced jam plain] 2)
((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))
</pre>
=={{header|CoffeeScript}}==
<
combos = (arr, k) ->
return [ [] ] if k == 0
Line 307 ⟶ 1,049:
console.log combos arr, 2
console.log "#{combos([1..10], 3).length} ways to order 3 donuts given 10 types"
</syntaxhighlight>
{{out}}
<
jam,plain:
[ [ 'iced', 'iced' ],
Line 319 ⟶ 1,061:
[ 'plain', 'plain' ] ]
220 ways to order 3 donuts given 10 types
</
=={{header|Common Lisp}}==
The code below is a modified version of the Clojure solution.
<syntaxhighlight lang="lisp">(defun combinations (xs k)
(let ((x (car xs)))
(cond
((null xs) nil)
((= k 1) (mapcar #'list xs))
(t (append (mapcar (lambda (ys) (cons x ys))
(combinations xs (1- k)))
(combinations (cdr xs) k))))))
</syntaxhighlight>
{{out}}
<pre>((:ICED :ICED) (:ICED :JAM) (:ICED :PLAIN) (:JAM :JAM) (:JAM :PLAIN) (:PLAIN :PLAIN))
</pre>
=={{header|Crystal}}==
{{trans|Ruby}}
<syntaxhighlight lang="ruby">possible_doughnuts = ["iced", "jam", "plain"].repeated_combinations(2)
puts "There are #{possible_doughnuts.size} possible doughnuts:"
possible_doughnuts.each{|doughnut_combi| puts doughnut_combi.join(" and ")}
# Extra credit
possible_doughnuts = (1..10).to_a.repeated_combinations(3)
# size returns the size of the enumerator, or nil if it can’t be calculated lazily.
puts "", "#{possible_doughnuts.size} ways to order 3 donuts given 10 types."</syntaxhighlight>
{{out}}
<pre>
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.
</pre>
=={{header|D}}==
Using [http://www
<
const struct CombRep {
Line 329 ⟶ 1,110:
private const ulong[] combVal;
this(in uint numType, in uint numChoice) pure nothrow @safe
in {
assert(0 < numType && numType + numChoice <= 64,
Line 359 ⟶ 1,140:
}
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);
Line 376 ⟶ 1,158:
}
private uint[] val2set(in ulong v) const pure nothrow @safe {
// Convert bit pattern to selection set
immutable uint bitLimit = nt + nc - 1;
Line 391 ⟶ 1,173:
// For finite Random Access Range.
auto combRep(R)(R types, in uint numChoice) /*pure
if (hasLength!R && isRandomAccessRange!R) {
ElementType!R[][] result;
Line 405 ⟶ 1,187:
}
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}}
<pre> iced iced
Line 421 ⟶ 1,203:
===Short Recursive Version===
<
T[][] combsRep(T)(T[] lst, in int k) {
Line 436 ⟶ 1,218:
["iced", "jam", "plain"].combsRep(2).writeln;
10.iota.array.combsRep(3).length.writeln;
}</
{{out}}
<pre>[["iced", "iced"], ["iced", "jam"], ["iced", "plain"], ["jam", "jam"], ["jam", "plain"], ["plain", "plain"]]
220</pre>
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
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"
</syntaxhighlight>
{{out}}
<pre>
iced iced
iced jam
iced plain
jam jam
jam plain
plain plain
220 results with 10 donuts
</pre>
=={{header|EchoLisp}}==
We can use the native '''combinations/rep''' function, or use a '''combinator''' iterator, or implement the function.
<syntaxhighlight lang="scheme">
;;
;; native function : combinations/rep in list.lib
;;
(lib 'list)
(combinations/rep '(iced jam plain) 2)
→ ((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))
;;
;; using a combinator iterator
;;
(lib 'sequences)
(take (combinator/rep '(iced jam plain) 2) 8)
→ ((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))
;;
;; or, implementing the function
;;
(define (comb/rep nums k)
(cond
[(null? nums) null]
[(<= k 0) null]
[(= k 1) (map list nums)]
[else
(for/fold (acc null) ((anum nums))
(append acc
(for/list ((xs (comb/rep nums (1- k))))
#:continue (< (first xs) anum)
(cons anum xs))))]))
(map (curry list-permute '(iced jam plain)) (comb/rep (iota 3) 2))
→ ((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))
;;
;; extra credit
;;
(length (combinator/rep (iota 10) 3))
→ 220
</syntaxhighlight>
=={{header|Egison}}==
<
(define $comb/rep
(lambda [$n $xs]
Line 449 ⟶ 1,332:
(test (comb/rep 2 {"iced" "jam" "plain"}))
</syntaxhighlight>
{{out}}
<pre>
{[|"iced" "iced"|] [|"iced" "jam"|] [|"jam" "jam"|] [|"iced" "plain"|] [|"jam" "plain"|] [|"plain" "plain"|]}
</
=={{header|Elixir}}==
{{trans|Erlang}}
<syntaxhighlight lang="elixir">defmodule RC do
def comb_rep(0, _), do: [[]]
def comb_rep(_, []), do: []
def comb_rep(n, [h|t]=s) do
(for l <- comb_rep(n-1, s), do: [h|l]) ++ comb_rep(n, t)
end
end
s = [:iced, :jam, :plain]
Enum.each(RC.comb_rep(2, s), fn x -> IO.inspect x end)
IO.puts "\nExtra credit: #{length(RC.comb_rep(3, Enum.to_list(1..10)))}"</syntaxhighlight>
{{out}}
<pre>
[:iced, :iced]
[:iced, :jam]
[:iced, :plain]
[:jam, :jam]
[:jam, :plain]
[:plain, :plain]
Extra credit: 220
</pre>
=={{header|Erlang}}==
<
-module(comb).
-compile(export_all).
Line 466 ⟶ 1,376:
comb_rep(N,[H|T]=S) ->
[[H|L] || L <- comb_rep(N-1,S)]++comb_rep(N,T).
</syntaxhighlight>
{{out}}
<pre>
94> comb:comb_rep(2,[iced,jam,plain]).
[[iced,iced],
Line 478 ⟶ 1,388:
95> length(comb:comb_rep(3,lists:seq(1,10))).
220
</
=={{header|Factor}}==
See the implementation of <code>all-combinations-with-replacement</code> [https://docs.factorcode.org/content/word-all-combinations-with-replacement,math.combinatorics.html here].
{{works with|Factor|0.99 2022-04-03}}
<syntaxhighlight lang=factor>USING: math.combinatorics prettyprint qw ;
qw{ iced jam plain } 2 all-combinations-with-replacement .</syntaxhighlight>
{{out}}
<pre>
{
{ "iced" "iced" }
{ "iced" "jam" }
{ "iced" "plain" }
{ "jam" "jam" }
{ "jam" "plain" }
{ "plain" "plain" }
}
</pre>
=={{header|Fortran}}==
<syntaxhighlight lang="fortran">
program main
integer :: chosen(4)
integer :: ssize
character(len=50) :: donuts(4) = [ "iced", "jam", "plain", "something completely different" ]
ssize = choose( chosen, 2, 3 )
write(*,*) "Total = ", ssize
contains
recursive function choose( got, len, maxTypes, nChosen, at ) result ( output )
integer :: got(:)
integer :: len
integer :: maxTypes
integer :: output
integer, optional :: nChosen
integer, optional :: at
integer :: effNChosen
integer :: effAt
integer :: i
integer :: counter
effNChosen = 1
if( present(nChosen) ) effNChosen = nChosen
effAt = 1
if( present(at) ) effAt = at
if ( effNChosen == len+1 ) then
do i=1,len
write(*,"(A10,5X)", advance='no') donuts( got(i)+1 )
end do
write(*,*) ""
output = 1
return
end if
counter = 0
do i=effAt,maxTypes
got(effNChosen) = i-1
counter = counter + choose( got, len, maxTypes, effNChosen + 1, i )
end do
output = counter
return
end function choose
end program main
</syntaxhighlight>
{{out}}
<pre>
iced iced
iced jam
iced plain
jam jam
jam plain
plain plain
Total = 6
</pre>
=={{header|FreeBASIC}}==
<syntaxhighlight lang="freebasic">sub iterate( byval curr as string, byval start as uinteger,_
byval stp as uinteger, byval depth as uinteger,_
names() as string )
dim as uinteger i
for i = start to stp
if depth = 0 then
print curr + " " + names(i)
else
iterate curr+" "+names(i), i, stp, depth-1, names()
end if
next i
return
end sub
dim as uinteger m, n, o, i
input "Enter n comb m. ", n, m
dim as string outstr = ""
dim as string names(0 to m-1)
for i = 0 to m - 1
print "Name for item ",+i
input names(i)
next i
iterate outstr, 0, m-1, n-1, names()</syntaxhighlight>
{{out}}<pre>
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
</pre>
=={{header|GAP}}==
<
UnorderedTuples(["iced", "jam", "plain"], 2);</
=={{header|Go}}==
===Concise recursive===
<
import "fmt"
Line 507 ⟶ 1,544:
fmt.Println(len(combrep(3,
[]string{"1", "2", "3", "4", "5", "6", "7", "8", "9", "10"})))
}</
{{out}}
<pre>
[[plain plain] [plain jam] [jam jam] [plain iced] [jam iced] [iced iced]]
220
</pre>
===Channel===
Using channel and goroutine, showing how to use synced or unsynced communication.
<
import "fmt"
Line 572 ⟶ 1,610:
}
fmt.Printf("\npicking 3 of 10: %d\n", count)
}</
{{out}}
<pre>
plain plain
Line 586 ⟶ 1,624:
===Multiset===
This version has proper representation of sets and multisets.
<
import (
Line 595 ⟶ 1,633:
// 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
Line 687 ⟶ 1,725:
}
fmt.Println(len(combrep(3, ten)))
}</
{{out}}
<pre>
map[plain:1 jam:1]
Line 700 ⟶ 1,738:
=={{header|Haskell}}==
<
-- 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 =
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}}
<pre>[["iced","iced"],["iced","jam"],["iced","plain"],["jam","jam"],["jam","plain"],["plain","plain"]]
220</pre>
===Dynamic Programming===
Line 727 ⟶ 1,770:
The first solution is inefficient because it repeatedly calculates the same subproblem in different branches of recursion. For example, <code>combsWithRep k (x:xs)</code> involves computing <code>combsWithRep (k-1) (x:xs)</code> and <code>combsWithRep k xs</code>, both of which (separately) compute <code>combsWithRep (k-1) xs</code>. To avoid repeated computation, we can use dynamic programming:
<
combsWithRep k xs = combsBySize xs !! k
combsBySize = foldr f ([[]] : repeat [])
f x
main :: IO ()
main = print $ combsWithRep 2 ["iced", "jam", "plain"]</syntaxhighlight>
and another approach, using manual recursion:
<syntaxhighlight lang="haskell">--------------- 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
print $ length $ combinationsWithRepetition 3 [0 .. 9]</syntaxhighlight>
{{Out}}
<pre>[["iced","iced"],["jam","iced"],["plain","iced"],["jam","jam"],["plain","jam"],["plain","plain"]]
220</pre>
=={{header|Icon}} and {{header|Unicon}}==
Following procedure is a generator, which generates each combination of length n in turn:
<syntaxhighlight lang="icon">
# generate all combinations of length n from list L,
# including repetitions
Line 761 ⟶ 1,831:
}
end
</syntaxhighlight>
Test procedure:
<syntaxhighlight lang="icon">
# convenience function
procedure write_list (l)
Line 782 ⟶ 1,852:
write ("There are " || count || " possible combinations of 3 from 10")
end
</syntaxhighlight>
{{out}}
<pre>
plain plain
Line 796 ⟶ 1,866:
=={{header|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.
<syntaxhighlight lang="j">rcomb=: >@~.@:(/:~&.>)@,@{@# <</syntaxhighlight>
Example use:
<
┌─────┬─────┐
│iced │iced │
Line 814 ⟶ 1,886:
│plain│plain│
└─────┴─────┘
#3 rcomb i.10 NB. # ways to choose 3 items from 10 with
220</
===J Alternate implementation===
Considerably faster:
<syntaxhighlight lang="j">require 'stats'
rcomb=: (combrep #) { ]</syntaxhighlight>
This definition of <code>rcomb</code> behaves identically to the previous one, and <code>combrep</code> calculates indices:
<syntaxhighlight lang="j"> 2 combrep 3
0 0
0 1
0 2
1 1
1 2
2 2</syntaxhighlight>
<code>combrep</code> computes <code>2 comb 4 </code> (note that 4 = (2 + 3)-1) and then subtracts from each column the minimum value in each column (<code>i. 2</code>).
=={{header|Java}}==
'''MultiCombinationsTester.java'''
<
import com.objectwave.utility.*;
Line 846 ⟶ 1,937:
}
} // class
</syntaxhighlight>
'''MultiCombinations.java'''
<
import com.objectwave.utility.*;
import java.util.*;
Line 898 ⟶ 1,989:
}
} // class
</syntaxhighlight>
{{out}}
<pre>
iced iced
Line 911 ⟶ 2,002:
The ways to choose 3 items from 10 with replacement = 220
</pre>
=={{header|JavaScript}}==
===ES5===
====Imperative====
<syntaxhighlight lang="javascript"><html><head><title>Donuts</title></head>
<body><pre id='x'></pre><script type="application/javascript">
function disp(x) {
Line 935 ⟶ 2,029:
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></
{{out}}
<pre>iced iced
iced jam
iced plain
Line 942 ⟶ 2,038:
plain plain
6 combos
pick 3 out of 10: 220 combos</
====Functional====
<syntaxhighlight lang="javascript">(function () {
// n -> [a] -> [[a]]
function combsWithRep(n, lst) {
return n ? (
lst.length ? combsWithRep(n - 1, lst).map(function (t) {
return [lst[0]].concat(t);
}).concat(combsWithRep(n, lst.slice(1))) : []
) : [[]];
};
// If needed, we can derive a significantly faster version of
// the simple recursive function above by memoizing it
// f -> f
function memoized(fn) {
m = {};
return function (x) {
var args = [].slice.call(arguments),
strKey = args.join('-');
v = m[strKey];
if ('u' === (typeof v)[0])
m[strKey] = v = fn.apply(null, args);
return v;
}
}
// [m..n]
function range(m, n) {
return Array.apply(null, Array(n - m + 1)).map(function (x, i) {
return m + i;
});
}
return [
combsWithRep(2, ["iced", "jam", "plain"]),
// obtaining and applying a memoized version of the function
memoized(combsWithRep)(3, range(1, 10)).length
];
})();</syntaxhighlight>
{{Out}}
<syntaxhighlight lang="javascript">[
[["iced", "iced"], ["iced", "jam"], ["iced", "plain"],
["jam", "jam"], ["jam", "plain"], ["plain", "plain"]],
220
]</syntaxhighlight>
===ES6===
{{Trans|Haskell}}
<syntaxhighlight lang="javascript">(() => {
'use strict';
// COMBINATIONS WITH REPETITIONS -------------------------------------------
// combsWithRep :: Int -> [a] -> [[a]]
const combsWithRep = (k, xs) => {
const comb = (n, ys) => {
if (0 === n) return ys;
if (isNull(ys)) return comb(n - 1, map(pure, xs));
return comb(n - 1, concatMap(zs => {
const h = head(zs);
return map(x => [x].concat(zs), dropWhile(x => x !== h, xs));
}, ys));
};
return comb(k, []);
};
// GENERIC FUNCTIONS ------------------------------------------------------
// concatMap :: (a -> [b]) -> [a] -> [b]
const concatMap = (f, xs) => [].concat.apply([], xs.map(f));
// dropWhile :: (a -> Bool) -> [a] -> [a]
const dropWhile = (p, xs) => {
let i = 0;
for (let lng = xs.length;
(i < lng) && p(xs[i]); i++) {}
return xs.slice(i);
};
// enumFromTo :: Int -> Int -> [Int]
const enumFromTo = (m, n) =>
Array.from({
length: Math.floor(n - m) + 1
}, (_, i) => m + i);
// head :: [a] -> Maybe a
const head = xs => xs.length ? xs[0] : undefined;
// isNull :: [a] -> Bool
const isNull = xs => (xs instanceof Array) ? xs.length < 1 : undefined;
// length :: [a] -> Int
const length = xs => xs.length;
// map :: (a -> b) -> [a] -> [b]
const map = (f, xs) => xs.map(f);
// pure :: a -> [a]
const pure = x => [x];
// show :: a -> String
const show = x => JSON.stringify(x, null, 2);
// TEST -------------------------------------------------------------------
return show({
twoFromThree: combsWithRep(2, ['iced', 'jam', 'plain']),
threeFromTen: length(combsWithRep(3, enumFromTo(0, 9)))
});
})();</syntaxhighlight>
{{Out}}
<pre>{
"twoFromThree": [
[
"iced",
"iced"
],
[
"jam",
"iced"
],
[
"plain",
"iced"
],
[
"jam",
"jam"
],
[
"plain",
"jam"
],
[
"plain",
"plain"
]
],
"threeFromTen": 220
}</pre>
=={{header|jq}}==
<syntaxhighlight lang="jq">def pick(n):
def pick(n; m): # pick n, from m onwards
if n == 0 then []
elif m == length then empty
elif n == 1 then (.[m:][] | [.])
else ([.[m]] + pick(n-1; m)), pick(n; m+1)
end;
pick(n;0) ;</syntaxhighlight>
'''The task''':
<syntaxhighlight lang="jq"> "Pick 2:",
(["iced", "jam", "plain"] | pick(2)),
([[range(0;10)] | pick(3)] | length) as $n
| "There are \($n) ways to pick 3 objects with replacement from 10."
</syntaxhighlight>
{{Out}}
<pre>$ 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.</pre>
=={{header|Julia}}==
{{works with|Julia|0.6}}
<syntaxhighlight lang="julia">using Combinatorics
l = ["iced", "jam", "plain"]
println("List: ", l, "\nCombinations:")
for c in with_replacement_combinations(l, 2)
println(c)
end
@show length(with_replacement_combinations(1:10, 3))</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|Kotlin}}==
<syntaxhighlight lang="scala">// version 1.0.6
class CombsWithReps<T>(val m: Int, val n: Int, val items: List<T>, val countOnly: Boolean = false) {
private val combination = IntArray(m)
private var count = 0
init {
generate(0)
if (!countOnly) println()
println("There are $count combinations of $n things taken $m at a time, with repetitions")
}
private fun generate(k: Int) {
if (k >= m) {
if (!countOnly) {
for (i in 0 until m) print("${items[combination[i]]}\t")
println()
}
count++
}
else {
for (j in 0 until n)
if (k == 0 || j >= combination[k - 1]) {
combination[k] = j
generate(k + 1)
}
}
}
}
fun main(args: Array<String>) {
val doughnuts = listOf("iced", "jam", "plain")
CombsWithReps(2, 3, doughnuts)
println()
val generic10 = "0123456789".chunked(1)
CombsWithReps(3, 10, generic10, true)
}</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|LFE}}==
{{trans|Erlang}} and {{trans|Clojure}}
===With List Comprehension===
<syntaxhighlight lang="lisp">
(defun combinations
(('() _)
'())
((coll 1)
(lists:map #'list/1 coll))
(((= (cons head tail) coll) n)
(++ (lc ((<- subcoll (combinations coll (- n 1))))
(cons head subcoll))
(combinations tail n))))
</syntaxhighlight>
===With Map===
<syntaxhighlight lang="lisp">
(defun combinations
(('() _)
'())
((coll 1)
(lists:map #'list/1 coll))
(((= (cons head tail) coll) n)
(++ (lists:map (lambda (subcoll) (cons head subcoll))
(combinations coll (- n 1)))
(combinations tail n))))
</syntaxhighlight>
Output is the same for both:
<syntaxhighlight lang="lisp">
> (combinations '(iced jam plain) 2)
((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))
</syntaxhighlight>
=={{header|Lobster}}==
{{trans|C}}
<syntaxhighlight lang="lobster">import std
// set S of length n, choose k
def choose(s, k, f):
let got = map(k): s[0]
let n = s.length
def choosi(n_chosen, at):
var count = 0
if n_chosen == k:
f(got)
return 1
var i = at
while i < n:
got[n_chosen] = s[i]
count += choosi(n_chosen + 1, i)
i += 1
return count
return choosi(0, 0)
let count = choose(["iced", "jam", "plain"], 2): print(_)
print count
let extra = choose(map(10):_, 3): _
print extra</syntaxhighlight>
{{out}}
<pre>["iced", "iced"]
["iced", "jam"]
["iced", "plain"]
["jam", "jam"]
["jam", "plain"]
["plain", "plain"]
6
220
</pre>
=={{header|Lua}}==
<
if not nStartIndex then
nStartIndex = 1
Line 991 ⟶ 2,416:
end
end
</syntaxhighlight>
=={{header|
<syntaxhighlight lang="maple">with(combinat):
chooserep:=(s,k)->choose([seq(op(s),i=1..k)],k):
chooserep({iced,jam,plain},2);
# [[iced, iced], [iced, jam], [iced, plain], [jam, jam], [jam, plain], [plain, plain]]
numbchooserep:=(s,k)->binomial(nops(s)+k-1,k);
numbchooserep({iced,jam,plain},2);
# 6</syntaxhighlight>
=={{header|Mathematica}} / {{header|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).
<
->{{"iced", "iced"}, {"iced", "jam"}, {"iced", "plain"}, {"jam", "jam"}, {"jam", "plain"}, {"plain", "plain"}}
Line 1,004 ⟶ 2,437:
Combi[10, 3]
->220
</syntaxhighlight>
A better method therefore:
<
occupation =
Flatten[Permutations /@
Line 1,022 ⟶ 2,455:
Out[2]= {{"iced", "iced"}, {"jam", "jam"}, {"plain",
"plain"}, {"iced", "jam"}, {"iced", "plain"}, {"jam", "plain"}}
</syntaxhighlight>
Which can handle the Length[S] = 10, k=10 situation in still only seconds.
Line 1,031 ⟶ 2,464:
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.
<
:- interface.
:- import_module list, int, bag.
Line 1,062 ⟶ 2,495:
:- pred count(T::in, int::in, int::out) is det.
count(_, N0, N) :- N0 + 1 = N.</
Usage:
<
:- interface.
:- import_module io.
Line 1,083 ⟶ 2,516:
mystery, cubed, cream_covered, explosive], 3, N),
io.write(L, !IO), io.nl(!IO),
io.write_string(from_int(N) ++ " choices.\n", !IO).</
{{out}}
<pre>[[iced, iced], [jam, jam], [plain, plain], [iced, jam], [iced, plain], [jam, plain]]
220 choices.</pre>
=={{header|
{{trans|D}}
<
proc combsReps[T](lst: seq[T], k: int): seq[seq[T]] =
Line 1,101 ⟶ 2,533:
else:
lst.combsReps(k - 1).map((x: seq[T]) => lst[0] & x) &
lst[1 ..
echo(@["iced", "jam", "plain"].combsReps(2))
echo toSeq(1..10).combsReps(3).len</
{{out}}
<pre>@[@[iced, iced], @[iced, jam], @[iced, plain], @[jam, jam], @[jam, plain], @[plain, plain]]
220</pre>
Line 1,112 ⟶ 2,544:
{{trans|Haskell}}
<
match k, xxs with
| 0, _ -> [[]]
Line 1,118 ⟶ 2,550:
| k, x::xs ->
List.map (fun ys -> x::ys) (combs_with_rep (k-1) xxs)
@ combs_with_rep k xs</
in the interactive loop:
Line 1,134 ⟶ 2,566:
===Dynamic programming===
<
let arr = Array.make (m+1) [] in
arr.(0) <- [[]];
Line 1,142 ⟶ 2,574:
done
) xs;
arr.(m)</
in the interactive loop:
Line 1,157 ⟶ 2,589:
=={{header|PARI/GP}}==
<
if(k==0,return([]));
if(k==1,return(vector(#v,i,concat(s,[v[i]]))));
Line 1,165 ⟶ 2,597:
};
xc(k,v)=binomial(#v+k-1,k);
ways(2, ["iced","jam","plain"])</
=={{header|Pascal}}==
used in [[Munchausen_numbers]] or [[Own_digits_power_sum]]
<syntaxhighlight lang="pascal">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.</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Perl}}==
The highly readable version:
<
sub f { $_[0] ? $_[0] * f($_[0] - 1) : 1 }
sub pn{ f($_[0] + $_[1] - 1) / f($_[0]) / f($_[1] - 1) }
Line 1,178 ⟶ 2,723:
printf "\nThere are %d ways to pick 7 out of 10\n", pn(7,10);
</syntaxhighlight>
Prints:
Line 1,191 ⟶ 2,736:
With a module:
<
my $iter = combinations_with_repetition([qw/iced jam plain/], 2);
while (my $p = $iter->next) {
Line 1,198 ⟶ 2,743:
# 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";</
=={{header|
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">show_choices</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">set</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">at</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">={})</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">n</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">res</span>
<span style="color: #008080;">else</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">at</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">set</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">show_choices</span><span style="color: #0000FF;">(</span><span style="color: #000000;">set</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">),</span><span style="color: #000000;">set</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">show_choices</span><span style="color: #0000FF;">({</span><span style="color: #008000;">"iced"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"jam"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"plain"</span><span style="color: #0000FF;">},</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
{"iced","iced"}
{"iced","jam"}
</pre>
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:
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">count_choices</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">set_size</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">at</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">taken</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">taken</span><span style="color: #0000FF;">=</span><span style="color: #000000;">n</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">taken</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">at</span> <span style="color: #008080;">to</span> <span style="color: #000000;">set_size</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">count_choices</span><span style="color: #0000FF;">(</span><span style="color: #000000;">set_size</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">taken</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">count</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">count_choices</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
220
</pre>
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:
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">combinations_with_repetitions</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"ijp"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">),</span><span style="color: #008000;">','</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">combinations_with_repetitions</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">),</span><span style="color: #000000;">3</span><span style="color: #0000FF;">))</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
"ii,ij,ip,jj,jp,pp"
220
</pre>
=={{header|PHP}}==
<
function combos($arr, $k) {
if ($k == 0) {
Line 1,259 ⟶ 2,832:
$num_donut_combos = count(combos($donuts, 3));
echo "$num_donut_combos ways to order 3 donuts given 10 types";
?></
<
iced iced
iced jam
Line 1,269 ⟶ 2,842:
plain plain
220 ways to order 3 donuts given 10 types
</
Non-recursive algorithm to generate all combinations with repetitons. Taken from here: [https://habrahabr.ru/post/311934/]
You must set k n variables and fill arrays b and c.
<syntaxhighlight lang="php">
<?php
//Author Ivan Gavryushin @dcc0
$k=3;
$n=5;
//set amount of elements as in $n var
$c=array(1,2,3,4,5);
//set amount of 1 as in $k var
$b=array(1,1,1);
$j=$k-1;
//Вывод
function printt($b,$k) {
$z=0;
while ($z < $k) print $b[$z++].' ';
print '<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--;
}
}
}
?>
</syntaxhighlight>
=={{header|PicoLisp}}==
<
(cond
((=0 N) '(NIL))
Line 1,281 ⟶ 2,921:
'((X) (cons (car Lst) X))
(combrep (dec N) Lst) )
(combrep N (cdr Lst)) ) ) ) )</
{{out}}
<pre>: (combrep 2 '(iced jam plain))
-> ((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))
Line 1,288 ⟶ 2,928:
: (length (combrep 3 (range 1 10)))
-> 220</pre>
=={{header|Prolog}}==
<syntaxhighlight lang="prolog">
combinations_of_length(_,[]).
combinations_of_length([X|T],[X|Combinations]):-
combinations_of_length([X|T],Combinations).
combinations_of_length([_|T],[X|Combinations]):-
combinations_of_length(T,[X|Combinations]).
</syntaxhighlight>
<pre>
?- [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,
.
.
.
</pre>
=={{header|PureBasic}}==
<
;combIndex() must be dimensioned to 'k' - 1, elementCount equals 'n' - 1
;combination produced includes repetition of elements and is represented by the array combIndex()
Line 1,341 ⟶ 3,024:
For i = 0 To n - 1: Read.s dougnut(i): Next
PrintN("Combinations of " + Str(
combinationCount = 0
Repeat
Line 1,358 ⟶ 3,041:
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()
EndIf </
{{out}}
<pre>Combinations of
iced + iced
iced + jam
Line 1,371 ⟶ 3,054:
Ways to select 3 items from 10 types: 220</pre>
=={{header|Python}}==
<
>>> n, k = 'iced jam plain'.split(), 2
>>> list(combinations_with_replacement(n,k))
Line 1,380 ⟶ 3,065:
>>> len(list(combinations_with_replacement(range(10), 3)))
220
>>> </
'''References:'''
* [http://docs.python.org/py3k/library/itertools.html#itertools.combinations_with_replacement Python documentation]
Or, assembling our own '''combsWithRep''', by composition of functional primitives:
{{Trans|Haskell}}
{{Works with|Python|3.7}}
<syntaxhighlight lang="python">'''Combinations with repetitions'''
from itertools import (accumulate, chain, islice, repeat)
from functools import (reduce)
# combsWithRep :: Int -> [a] -> [kTuple a]
def combsWithRep(k):
'''A list of tuples, representing
sets of cardinality k,
with elements drawn from xs.
'''
def f(a, x):
def go(ys, xs):
return xs + [[x] + y for y in ys]
return accumulate(a, go)
def combsBySize(xs):
return reduce(
f, xs, chain(
[[[]]],
islice(repeat([]), k)
)
)
return lambda xs: [
tuple(x) for x in next(islice(
combsBySize(xs), k, None
))
]
# TEST ----------------------------------------------------
def main():
'''Test the generation of sets of cardinality
k with elements drawn from xs.
'''
print(
combsWithRep(2)(['iced', 'jam', 'plain'])
)
print(
len(combsWithRep(3)(enumFromTo(0)(9)))
)
# GENERIC -------------------------------------------------
# enumFromTo :: (Int, Int) -> [Int]
def enumFromTo(m):
'''Integer enumeration from m to n.'''
return lambda n: list(range(m, 1 + n))
# showLog :: a -> IO String
def showLog(*s):
'''Arguments printed with
intercalated arrows.'''
print(
' -> '.join(map(str, s))
)
# MAIN ---
if __name__ == '__main__':
main()</syntaxhighlight>
{{Out}}
<pre>[('iced', 'iced'), ('jam', 'iced'), ('jam', 'jam'), ('plain', 'iced'), ('plain', 'jam'), ('plain', 'plain')]
220</pre>
=={{header|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.
<syntaxhighlight lang="quackery">( nextplain generates the next plaindrome in the
current base by adding one to a given plaindrome,
then replacing each trailing zero with the least
significant non-zero digit of the number
See: https://oeis.org/search?q=plaindromes
4 base put
-1
10 times
[ nextplain
dup echo sp ]
drop
base release
prints "0 1 2 3 11 12 13 22 23 33"
i.e. decimal "0 1 2 3 5 6 7 10 11 15"
Right padding the base 4 representations with
zeros gives all the combinations with repetitions
for selecting two doughnuts in a store selling
four types of doughnut, numbered 0, 1, 2, and 3.
00 01 02 03 11 12 13 22 23 33 )
[ 1+ dup 0 = if done
0 swap
[ base share /mod
dup 0 = while
drop dip 1+
again ]
swap rot 1+ times
[ base share * over + ]
nip ] is nextplain ( n --> n )
[ dup base put
swap ** 1 -
[] swap -1
[ 2dup > while
nextplain
rot over join
unrot
again ]
base release
2drop ] is kcombnums ( n n --> [ )
[ [] unrot times
[ base share /mod
rot join swap ]
drop ] is ndigits ( n n --> [ )
[ [] unrot
witheach
[ dip dup peek
nested rot swap join
swap ]
drop ] is [peek] ( [ [ --> [ )
[ dup temp put
size dup base put
dip dup kcombnums
[] unrot witheach
[ over ndigits
temp share swap [peek]
nested rot swap join
swap ]
temp release
base release
drop ] is kcombs ( n [ --> [ )
2
$ "jam iced plain" nest$
kcombs
witheach
[ witheach
[ echo$ sp ] cr ]
cr
3 10 kcombnums size echo</syntaxhighlight>
{{out}}
<pre>jam jam
iced jam
plain jam
iced iced
plain iced
plain plain
220
</pre>
=={{header|R}}==
The idiomatic solution is to just use a library.
<syntaxhighlight lang="rsplus">library(gtools)
combinations(3, 2, c("iced", "jam", "plain"), set = FALSE, repeats.allowed = TRUE)
nrow(combinations(10, 3, repeats.allowed = TRUE))</syntaxhighlight>
{{out}}
<pre>> 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</pre>
=={{header|Racket}}==
<
#lang racket
(define (combinations xs k)
Line 1,394 ⟶ 3,266:
(map (λ(x) (cons (first xs) x))
(combinations xs (- k 1))))]))
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
One could simply generate all [[Permutations_with_repetitions#Raku|permutations]], and then remove "duplicates":
{{works with|Rakudo|2016.07}}
<syntaxhighlight lang="raku" line>my @S = <iced jam plain>;
my $k = 2;
.put for [X](@S xx $k).unique(as => *.sort.cache, with => &[eqv])</syntaxhighlight>
{{out}}
<pre>
iced iced
iced jam
iced plain
jam jam
jam plain
plain plain
</pre>
Alternatively, a recursive solution:
{{trans|Haskell}}
<syntaxhighlight lang="raku" line>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 );</syntaxhighlight>
{{out}}
<pre>(iced iced)
(iced jam)
(iced plain)
(jam jam)
(jam plain)
(plain plain)
220</pre>
=={{header|REXX}}==
===version 1===
This REXX version uses a type of anonymous recursion.
<syntaxhighlight lang="rexx">/*REXX pgm displays combination sets with repetitions for X things taken Y at a time*/
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</syntaxhighlight>
{{out|output}}
<pre>
─────────────── 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.
</pre>
===version 2===
recursive (taken from version 1)
Reformatted and variable names suitable for OoRexx.
<syntaxhighlight lang="rexx">/*REXX compute (and show) combination sets for nt things in ns places*/
debug=0
Call time 'R'
Call RcombN 3,2,'iced,jam,plain' /* The 1st part of the task */
Call RcombN -10,3,'iced,jam,plain,d,e,f,g,h,i,j' /* 2nd part */
Call RcombN -10,9,'iced,jam,plain,d,e,f,g,h,i,j' /* extra part */
Say time('E') 'seconds'
Exit
/*-------------------------------------------------------------------*/
Rcombn: Procedure Expose thing. debug
Parse Arg nt,ns,thinglist
tell=nt>0
nt=abs(nt)
Say '------------' nt 'doughnut selection taken' ns 'at a time:'
If tell=0 Then
Say ' list output suppressed'
Do i=1 By 1 While thinglist>''
Parse Var thinglist thing.i ',' thinglist /* assign things. */
End
index.=1
Do cmb=1 By 1
If tell Then /* display combinations */
Call show /* show this one */
index.ns=index.ns+1
Call show_index 'A'
If index.ns==nt+1 Then
If proc(ns-1) Then
Leave
End
Say '------------' cmb 'combinations.'
Say
Return
/*-------------------------------------------------------------------*/
proc: Procedure Expose nt ns thing. index. debug
Parse Arg recnt
If recnt>0 Then Do
p=index.recnt+1
If p=nt+1 Then
Return proc(recnt-1)
Do i=recnt To ns
index.i=p
End
Call show_index 'C'
End
Return recnt=0
/*-------------------------------------------------------------------*/
show: Procedure Expose index. thing. ns debug
l=''
Call show_index 'B----------------------->'
Do i=1 To ns
j=index.i
l=l thing.j
End
Say l
Return
show_index: Procedure Expose index. ns debug
If debug Then Do
Parse Arg tag
l=tag
Do i=1 To ns
l=l index.i
End
Say l
End
Return</syntaxhighlight>
{{out}}
<pre>----------- 3 doughnut selection taken 2 at a time:
iced iced
iced jam
Line 1,436 ⟶ 3,434:
jam plain
plain plain
list output suppressed
------------ 220 combinations.
------------ 10 doughnut selection taken 9 at a time:
list output suppressed
------------ 48620 combinations.
0.125000 seconds</pre>
===version 3===
iterative (transformed from version 1)
<syntaxhighlight lang="rexx">/*REXX compute (and show) combination sets for nt things in ns places*/
Numeric Digits 20
debug=0
Call time 'R'
Call IcombN 3,2,'iced,jam,plain' /* The 1st part of the task */
Call IcombN -10,3,'iced,jam,plain,d,e,f,g,h,i,j' /* 2nd part */
Call IcombN -10,9,'iced,jam,plain,d,e,f,g,h,i,j' /* extra part */
Say time('E') 'seconds'
Exit
IcombN: Procedure Expose thing. debug
Parse Arg nt,ns,thinglist
tell=nt>0
nt=abs(nt)
Say '------------' nt 'doughnut selection taken' ns 'at a time:'
If tell=0 Then
Say ' list output suppressed'
Do i=1 By 1 While thinglist>''
Parse Var thinglist thing.i ',' thinglist /* assign things. */
End
index.=1
cmb=0
Call show
i=ns+1
Do While i>1
i=i-1
Do j=1 By 1 While index.i<nt
index.i=index.i+1
Call show
End
i1=i-1
If index.i1<nt Then Do
index.i1=index.i1+1
Do ii=i To ns
index.ii=index.i1
End
Call show
i=ns+1
End
If index.1=nt Then Leave
End
Say cmb
Return
show: Procedure Expose ns index. thing. tell cmb
cmb=cmb+1
If tell Then Do
l=''
Do i=1 To ns
j=index.i
l=l thing.j
End
Say l
End
Return</syntaxhighlight>
{{out}}
<pre>------------ 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</pre>
Slightly faster
=={{header|Ring}}==
<syntaxhighlight lang="ring">
# Project : Combinations with repetitions
n = 2
k = 3
temp = []
comb = []
num = com(n, k)
combinations(n, k)
comb = sortfirst(comb, 1)
see showarray(comb) + nl
func combinations(n, k)
while true
temp = []
for nr = 1 to k
tm = random(n-1) + 1
add(temp, tm)
next
add(comb, temp)
for p = 1 to len(comb) - 1
for q = p + 1 to len(comb)
if (comb[p][1] = comb[q][1]) and (comb[p][2] = comb[q][2]) and (comb[p][3] = comb[q][3])
del(comb, p)
ok
next
next
if len(comb) = num
exit
ok
end
func com(n, k)
res = pow(n, k)
return res
func showarray(vect)
svect = ""
for nrs = 1 to len(vect)
svect = "[" + vect[nrs][1] + " " + vect[nrs][2] + " " + vect[nrs][3] + "]" + nl
see svect
next
Func sortfirst(alist, ind)
aList = sort(aList,ind)
for n = 1 to len(alist)-1
for m= n + 1 to len(aList)
if alist[n][1] = alist[m][1] and alist[m][2] < alist[n][2]
temp = alist[n]
alist[n] = alist[m]
alist[m] = temp
ok
next
next
for n = 1 to len(alist)-1
for m= n + 1 to len(aList)
if alist[n][1] = alist[m][1] and alist[n][2] = alist[m][2] and alist[m][3] < alist[n][3]
temp = alist[n]
alist[n] = alist[m]
alist[m] = temp
ok
next
next
return aList
</syntaxhighlight>
Output:
<pre>
[1 1 1]
[1 1 2]
[1 2 1]
[1 2 2]
[2 1 1]
[2 1 2]
[2 2 1]
[2 2 2]
</pre>
=={{header|Ruby}}==
{{works with|Ruby
<syntaxhighlight lang="ruby">possible_doughnuts = ['iced', 'jam', 'plain'].repeated_combination(2)
puts "There are #{possible_doughnuts.count} possible doughnuts:"
possible_doughnuts.each{|doughnut_combi| puts doughnut_combi.join(' and ')}
# Extra credit
possible_doughnuts = [*1..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."
</syntaxhighlight>
{{out}}
<pre>
There are 6 possible doughnuts:
Line 1,459 ⟶ 3,620:
jam and plain
plain and plain
5799990040867421088231767567302459508715964845043404147200 ways to order 30 donuts given 1000 types.
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">
// Iterator for the combinations of `arr` with `k` elements with repetitions.
// Yields the combinations in lexicographical order.
struct CombinationsWithRepetitions<'a, T: 'a> {
// source array to get combinations from
arr: &'a [T],
// length of the combinations
k: u32,
// current counts of each object that represent the next combination
counts: Vec<u32>,
// whether there are any combinations left
remaining: bool,
}
impl<'a, T> CombinationsWithRepetitions<'a, T> {
fn new(arr: &[T], k: u32) -> CombinationsWithRepetitions<T> {
let mut counts = vec![0; arr.len()];
counts[arr.len() - 1] = k;
CombinationsWithRepetitions {
arr,
k,
counts,
remaining: true,
}
}
}
impl<'a, T> Iterator for CombinationsWithRepetitions<'a, T> {
type Item = Vec<&'a T>;
fn next(&mut self) -> Option<Vec<&'a T>> {
if !self.remaining {
return None;
}
let mut comb = Vec::new();
for (count, item) in self.counts.iter().zip(self.arr.iter()) {
for _ in 0..*count {
comb.push(item);
}
}
// this is lexicographically largest, and thus the last combination
if self.counts[0] == self.k {
self.remaining = false;
} else {
let n = self.counts.len();
for i in (1..n).rev() {
if self.counts[i] > 0 {
let original_value = self.counts[i];
self.counts[i - 1] += 1;
for j in i..(n - 1) {
self.counts[j] = 0;
}
self.counts[n - 1] = original_value - 1;
break;
}
}
}
Some(comb)
}
}
fn main() {
let collection = vec!["iced", "jam", "plain"];
for comb in CombinationsWithRepetitions::new(&collection, 2) {
for item in &comb {
print!("{} ", item)
}
println!()
}
}
</syntaxhighlight>
{{out}}
<pre>
plain plain
jam plain
jam jam
iced plain
iced jam
iced iced
</pre>
=={{header|Scala}}==
Scala has a combinations method in the standard library.
<
object CombinationsWithRepetition {
Line 1,477 ⟶ 3,723:
}
}
</syntaxhighlight>
{{out}}
<pre>
iced,iced
Line 1,491 ⟶ 3,737:
=={{header|Scheme}}==
{{trans|PicoLisp}}
<
(cond ((= k 0) '(()))
((null? lst) '())
Line 1,503 ⟶ 3,749:
(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)</
{{out}}
<pre>
Line 1,511 ⟶ 3,757:
===Dynamic programming===
<
(define arr (make-vector (+ m 1) '()))
(vector-set! arr 0 '(()))
Line 1,525 ⟶ 3,771:
(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)</
{{out}}
<pre>
((iced iced) (jam iced) (jam jam) (plain iced) (plain jam) (plain plain))
220
</pre>
=={{header|Sidef}}==
{{trans|Perl}}
<syntaxhighlight lang="ruby">func cwr (n, l, a = []) {
n>0 ? (^l -> map {|k| __FUNC__(n-1, l.slice(k), [a..., l[k]]) }) : a
}
cwr(2, %w(iced jam plain)).each {|a|
say a.map{ .join(' ') }.join("\n")
}</syntaxhighlight>
Also built-in:
<syntaxhighlight lang="ruby">%w(iced jam plain).combinations_with_repetition(2, {|*a|
say a.join(' ')
})</syntaxhighlight>
{{out}}
<pre>
iced iced
iced jam
iced plain
jam jam
jam plain
plain plain
</pre>
Efficient count of the total number of combinations with repetition:
<syntaxhighlight lang="ruby">func cwr_count (n, m) { binomial(n + m - 1, m) }
printf("\nThere are %s ways to pick 7 out of 10 with repetition\n", cwr_count(10, 7))</syntaxhighlight>
{{out}}
<pre>
There are 11440 ways to pick 7 out of 10 with repetition
</pre>
Line 1,535 ⟶ 3,815:
{{trans|Haskell}}
<
match k, xxs with
| 0, _ -> [[]]
Line 1,541 ⟶ 3,821:
| k, x::xs ->
List.map (fun ys -> x::ys) (combs_with_rep (k-1) xxs)
@ combs_with_rep k xs</
in the interactive loop:
Line 1,556 ⟶ 3,836:
===Dynamic programming===
<
val arr = Array.array (m+1, [])
in
Line 1,566 ⟶ 3,846:
) xs;
Array.sub (arr, m)
end</
in the interactive loop:
Line 1,578 ⟶ 3,858:
val it = 220 : int
</pre>
=={{header|Stata}}==
<syntaxhighlight lang="stata">function combrep(v,k) {
n = cols(v)
a = J(comb(n+k-1,k),k,v[1])
u = J(1,k,1)
for (i=2; 1; i++) {
for (j=k; j>0; j--) {
if (u[j]<n) break
}
if (j<1) return(a)
m = u[j]+1
for (; j<=k; j++) u[j] = m
a[i,.] = v[u]
}
}
combrep(("iced","jam","plain"),2)
a = combrep(1..10,3)
rows(a)</syntaxhighlight>
'''Output'''
<pre> 1 2
+-----------------+
1 | iced iced |
2 | iced jam |
3 | iced plain |
4 | jam jam |
5 | jam plain |
6 | plain plain |
+-----------------+
220</pre>
=={{header|Swift}}==
<syntaxhighlight lang="swift">func combosWithRep<T>(var objects: [T], n: Int) -> [[T]] {
if n == 0 { return [[]] } else {
var combos = [[T]]()
while let element = objects.last {
combos.appendContentsOf(combosWithRep(objects, n: n - 1).map{ $0 + [element] })
objects.removeLast()
}
return combos
}
}
print(combosWithRep(["iced", "jam", "plain"], n: 2).map {$0.joinWithSeparator(" and ")}.joinWithSeparator("\n"))</syntaxhighlight>
Output:
<pre>plain and plain
jam and plain
iced and plain
jam and jam
iced and jam
iced and iced</pre>
=={{header|Tcl}}==
<
proc combrepl {set n {presorted no}} {
if {!$presorted} {
Line 1,602 ⟶ 3,938:
puts [combrepl {iced jam plain} 2]
puts [llength [combrepl {1 2 3 4 5 6 7 8 9 10} 3]]</
{{out}}
<pre>
{iced iced} {iced jam} {iced plain} {jam jam} {jam plain} {plain plain}
220
</pre>
=={{header|TXR}}==
<syntaxhighlight lang="dos">txr -p "(rcomb '(iced jam plain) 2)"</syntaxhighlight>
{{out}}
<pre>
((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))
</pre>
----
<syntaxhighlight lang="dos">txr -p "(length-list (rcomb '(0 1 2 3 4 5 6 7 8 9) 3))"</syntaxhighlight>
{{out}}
<pre>
220
</pre>
=={{header|Ursala}}==
<
#import nat
Line 1,617 ⟶ 3,966:
#cast %gLSnX
main = ^|(~&,length) cwr~~/(<'iced','jam','plain'>,2) ('1234567890',3)</
{{out}}
<pre>
(
Line 1,629 ⟶ 3,978:
<'plain','plain'>},
220)
</pre>
=={{header|VBScript}}==
<syntaxhighlight lang="vb">' Combinations with repetitions - iterative - VBScript
Sub printc(vi,n,vs)
Dim i, w
For i=0 To n-1
w=w &" "& vs(vi(i))
Next 'i
Wscript.Echo w
End Sub
Sub combine(flavors, draws, xitem, tell)
Dim n, i, j
ReDim v(draws)
If tell Then Wscript.Echo "list of cwr("& flavors &","& draws &") :"
Do While True
For i=0 To draws-1
If v(i)>flavors-1 Then
v(i+1)=v(i+1)+1
For j=i To 0 Step -1
v(j)=v(i+1)
Next 'j
End If
Next 'i
If v(draws)>0 Then Exit Do
n=n+1
If tell Then Call printc(v, draws, xitem)
v(0)=v(0)+1
Loop
Wscript.Echo "cwr("& flavors &","& draws &")="&n
End Sub
items=Array( "iced", "jam", "plain" )
combine 3, 2, items, True
combine 10, 3, , False
combine 10, 7, , False
combine 10, 9, , False </syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Wren}}==
===Concise recursive===
{{trans|Go}}
Produces results in no particular order.
<syntaxhighlight lang="wren">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)</syntaxhighlight>
{{out}}
<pre>
[[plain, plain], [plain, jam], [jam, jam], [plain, iced], [jam, iced], [iced, iced]]
220
</pre>
===Library based===
{{libheader|Wren-seq}}
{{libheader|Wren-perm}}
Produces results in lexicographic order.
<syntaxhighlight lang="wren">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)</syntaxhighlight>
{{out}}
<pre>
[[iced, iced], [iced, jam], [iced, plain], [jam, jam], [jam, plain], [plain, plain]]
220
</pre>
=={{header|XPL0}}==
<
int Count, Array(10);
Line 1,659 ⟶ 4,106:
Combos(0, 0, 3, 10, [0]);
Text(0, "Combos = "); IntOut(0, Count); CrLf(0);
]</
{{out}}
<pre>
iced iced
Line 1,675 ⟶ 4,122:
=={{header|zkl}}==
{{trans|Clojure}}
<
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(3,T(0,1,2,3,4,5,6,7,8,9)).len();</
{{out}}
<pre>
Line 1,687 ⟶ 4,134:
220
</pre>
=={{header|ZX Spectrum Basic}}==
<syntaxhighlight lang="zxbasic">10 READ n
20 DIM d$(n,5)
30 FOR i=1 TO n
40 READ d$(i)
50 NEXT i
60 DATA 3,"iced","jam","plain"
70 FOR i=1 TO n
80 FOR j=i TO n
90 PRINT d$(i);" ";d$(j)
100 NEXT j
110 NEXT i</syntaxhighlight>
| |||