Combinations with repetitions: Difference between revisions
(→Concise recursive: Changed to Wren S/H) |
|||
(53 intermediate revisions by 28 users not shown) | |||
Line 24: | Line 24: | ||
{{Template:Combinations and permutations}} |
{{Template:Combinations and permutations}} |
||
<br><br> |
<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}}== |
=={{header|Ada}}== |
||
Line 29: | Line 299: | ||
combinations.adb: |
combinations.adb: |
||
< |
<syntaxhighlight lang="ada">with Ada.Text_IO; |
||
procedure Combinations is |
procedure Combinations is |
||
Line 92: | Line 362: | ||
Ada.Text_IO.Put_Line ("Total Donuts:" & Natural'Image (Donut_Count)); |
Ada.Text_IO.Put_Line ("Total Donuts:" & Natural'Image (Donut_Count)); |
||
Ada.Text_IO.Put_Line ("Total Tens:" & Natural'Image (Ten_Count)); |
Ada.Text_IO.Put_Line ("Total Tens:" & Natural'Image (Ten_Count)); |
||
end Combinations;</ |
end Combinations;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 103: | Line 373: | ||
Total Donuts: 6 |
Total Donuts: 6 |
||
Total Tens: 220</pre> |
Total Tens: 220</pre> |
||
=={{header|AppleScript}}== |
=={{header|AppleScript}}== |
||
{{Trans|Haskell}} |
{{Trans|Haskell}} |
||
{{Trans|Python}} |
{{Trans|Python}} |
||
< |
<syntaxhighlight lang="applescript">--------------- COMBINATIONS WITH REPETITION ------------- |
||
on combsWithRep(k, xs) |
|||
-- combinationsWithRepetition :: Int -> [a] -> [kTuple a] |
|||
-- A list of lists, representing |
|||
on combinationsWithRepetition(k, xs) |
|||
-- A list of lists, representing |
|||
-- sets of cardinality k, with |
-- sets of cardinality k, with |
||
-- members drawn from xs. |
-- members drawn from xs. |
||
script |
script combinationsBySize |
||
script f |
script f |
||
on |λ|(a, x) |
on |λ|(a, x) |
||
Line 126: | Line 399: | ||
end |λ| |
end |λ| |
||
end script |
end script |
||
scanl1(go, a) |
scanl1(go, a) |
||
end |λ| |
end |λ| |
||
Line 135: | Line 409: | ||
end script |
end script |
||
|Just| of |index|(|λ|(xs) of |
|Just| of |index|(|λ|(xs) of combinationsBySize, 1 + k) |
||
end combinationsWithRepetition |
|||
end combsWithRep |
|||
- |
--------------------------- TEST ------------------------- |
||
on run |
on run |
||
{length of |
{length of combinationsWithRepetition(3, enumFromTo(0, 9)), ¬ |
||
combinationsWithRepetition(2, {"iced", "jam", "plain"})} |
|||
end run |
end run |
||
- |
------------------------- GENERIC ------------------------ |
||
-- Just :: a -> Maybe a |
-- Just :: a -> Maybe a |
||
Line 152: | Line 426: | ||
{type:"Maybe", Nothing:false, Just:x} |
{type:"Maybe", Nothing:false, Just:x} |
||
end Just |
end Just |
||
-- Nothing :: Maybe a |
-- Nothing :: Maybe a |
||
Line 157: | Line 432: | ||
{type:"Maybe", Nothing:true} |
{type:"Maybe", Nothing:true} |
||
end Nothing |
end Nothing |
||
-- enumFromTo :: (Int, Int) -> [Int] |
-- enumFromTo :: (Int, Int) -> [Int] |
||
Line 170: | Line 446: | ||
end if |
end if |
||
end enumFromTo |
end enumFromTo |
||
-- foldl :: (a -> b -> a) -> a -> [b] -> a |
-- foldl :: (a -> b -> a) -> a -> [b] -> a |
||
Line 182: | Line 459: | ||
end tell |
end tell |
||
end foldl |
end foldl |
||
-- index (!!) :: [a] -> Int -> Maybe a |
-- index (!!) :: [a] -> Int -> Maybe a |
||
Line 204: | Line 482: | ||
end if |
end if |
||
end |index| |
end |index| |
||
-- map :: (a -> b) -> [a] -> [b] |
-- map :: (a -> b) -> [a] -> [b] |
||
Line 216: | Line 495: | ||
end tell |
end tell |
||
end map |
end map |
||
-- min :: Ord a => a -> a -> a |
-- min :: Ord a => a -> a -> a |
||
Line 225: | Line 505: | ||
end if |
end if |
||
end min |
end min |
||
-- Lift 2nd class handler function into 1st class script wrapper |
-- Lift 2nd class handler function into 1st class script wrapper |
||
Line 237: | Line 518: | ||
end if |
end if |
||
end mReturn |
end mReturn |
||
-- repeat :: a -> Generator [a] |
-- repeat :: a -> Generator [a] |
||
Line 261: | Line 543: | ||
end tell |
end tell |
||
end scanl |
end scanl |
||
-- scanl1 :: (a -> a -> a) -> [a] -> [a] |
-- scanl1 :: (a -> a -> a) -> [a] -> [a] |
||
Line 302: | Line 585: | ||
missing value |
missing value |
||
end if |
end if |
||
end take</ |
end take</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>{220, {{"iced", "iced"}, {"jam", "iced"}, {"jam", "jam"}, {"plain", "iced"}, {"plain", "jam"}, {"plain", "plain"}}}</pre> |
<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}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f COMBINATIONS_WITH_REPETITIONS.AWK |
# syntax: GAWK -f COMBINATIONS_WITH_REPETITIONS.AWK |
||
BEGIN { |
BEGIN { |
||
Line 331: | Line 661: | ||
exit(0) |
exit(0) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
<p>output:</p> |
<p>output:</p> |
||
<pre> |
<pre> |
||
Line 343: | Line 673: | ||
</pre> |
</pre> |
||
=={{header| |
=={{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}} |
{{works with|BBC BASIC for Windows}} |
||
< |
<syntaxhighlight lang="bbcbasic"> DIM list$(2), chosen%(2) |
||
list$() = "iced", "jam", "plain" |
list$() = "iced", "jam", "plain" |
||
PRINT "Choices of 2 from 3:" |
PRINT "Choices of 2 from 3:" |
||
Line 371: | Line 728: | ||
c% += FNchoose(n% + 1, l%, i%, m%, g%(), n$()) |
c% += FNchoose(n% + 1, l%, i%, m%, g%(), n$()) |
||
NEXT |
NEXT |
||
= c%</ |
= c%</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 386: | Line 743: | ||
Total choices = 220 |
Total choices = 220 |
||
</pre> |
</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}}== |
=={{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. |
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. |
||
< |
<syntaxhighlight lang="bracmat">( ( choices |
||
= n things thing result |
= n things thing result |
||
. !arg:(?n.?things) |
. !arg:(?n.?things) |
||
Line 407: | Line 778: | ||
& out$(choices$(2.iced jam plain)) |
& out$(choices$(2.iced jam plain)) |
||
& out$(choices$(3.iced jam plain butter marmite tahin fish salad onion grass):?+[?N&!N) |
& out$(choices$(3.iced jam plain butter marmite tahin fish salad onion grass):?+[?N&!N) |
||
);</ |
);</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>iced^2+jam^2+plain^2+iced*jam+iced*plain+jam*plain |
<pre>iced^2+jam^2+plain^2+iced*jam+iced*plain+jam*plain |
||
Line 413: | Line 784: | ||
=={{header|C}}== |
=={{header|C}}== |
||
Non recursive solution |
|||
<lang C>#include <stdio.h> |
|||
<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" }; |
const char * donuts[] = { "iced", "jam", "plain", "something completely different" }; |
||
Line 445: | Line 854: | ||
return 0; |
return 0; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}}<pre>iced iced |
{{out}}<pre>iced iced |
||
iced jam |
iced jam |
||
Line 454: | Line 863: | ||
Were there ten donuts, we'd have had 220 choices of three</pre> |
Were there ten donuts, we'd have had 220 choices of three</pre> |
||
=={{header|C++}}== |
|||
Non recursive version. |
|||
<lang cpp> |
|||
#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; |
|||
} |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
iced iced |
|||
jam iced |
|||
plain iced |
|||
jam jam |
|||
plain jam |
|||
plain plain |
|||
</pre> |
|||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
{{trans|PHP}} |
{{trans|PHP}} |
||
< |
<syntaxhighlight lang="csharp"> |
||
using System; |
using System; |
||
using System.Collections.Generic; |
using System.Collections.Generic; |
||
Line 571: | Line 926: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 584: | Line 939: | ||
Recursive version |
Recursive version |
||
< |
<syntaxhighlight lang="csharp"> |
||
using System; |
using System; |
||
class MultiCombination |
class MultiCombination |
||
Line 608: | Line 963: | ||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{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}}== |
=={{header|Clojure}}== |
||
{{trans|Scheme}} |
{{trans|Scheme}} |
||
< |
<syntaxhighlight lang="clojure"> |
||
(defn combinations [coll k] |
(defn combinations [coll k] |
||
(when-let [[x & xs] coll] |
(when-let [[x & xs] coll] |
||
Line 620: | Line 1,027: | ||
(concat (map (partial cons x) (combinations coll (dec k))) |
(concat (map (partial cons x) (combinations coll (dec k))) |
||
(combinations xs k))))) |
(combinations xs k))))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 629: | Line 1,036: | ||
=={{header|CoffeeScript}}== |
=={{header|CoffeeScript}}== |
||
< |
<syntaxhighlight lang="coffeescript"> |
||
combos = (arr, k) -> |
combos = (arr, k) -> |
||
return [ [] ] if k == 0 |
return [ [] ] if k == 0 |
||
Line 642: | Line 1,049: | ||
console.log combos arr, 2 |
console.log combos arr, 2 |
||
console.log "#{combos([1..10], 3).length} ways to order 3 donuts given 10 types" |
console.log "#{combos([1..10], 3).length} ways to order 3 donuts given 10 types" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 658: | Line 1,065: | ||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
The code below is a modified version of the Clojure solution. |
The code below is a modified version of the Clojure solution. |
||
< |
<syntaxhighlight lang="lisp">(defun combinations (xs k) |
||
(let ((x (car xs))) |
(let ((x (car xs))) |
||
(cond |
(cond |
||
Line 666: | Line 1,073: | ||
(combinations xs (1- k))) |
(combinations xs (1- k))) |
||
(combinations (cdr xs) k)))))) |
(combinations (cdr xs) k)))))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 674: | Line 1,081: | ||
=={{header|Crystal}}== |
=={{header|Crystal}}== |
||
{{trans|Ruby}} |
{{trans|Ruby}} |
||
< |
<syntaxhighlight lang="ruby">possible_doughnuts = ["iced", "jam", "plain"].repeated_combinations(2) |
||
puts "There are #{possible_doughnuts.size} possible doughnuts:" |
puts "There are #{possible_doughnuts.size} possible doughnuts:" |
||
possible_doughnuts.each{|doughnut_combi| puts doughnut_combi.join(" and ")} |
possible_doughnuts.each{|doughnut_combi| puts doughnut_combi.join(" and ")} |
||
Line 681: | Line 1,088: | ||
possible_doughnuts = (1..10).to_a.repeated_combinations(3) |
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. |
# 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."</ |
puts "", "#{possible_doughnuts.size} ways to order 3 donuts given 10 types."</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 697: | Line 1,104: | ||
=={{header|D}}== |
=={{header|D}}== |
||
Using [http://www.graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation lexicographic next bit permutation] to generate combinations with repetitions. |
Using [http://www.graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation lexicographic next bit permutation] to generate combinations with repetitions. |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.range; |
||
const struct CombRep { |
const struct CombRep { |
||
Line 785: | Line 1,192: | ||
writeln("Ways to select 3 from 10 types is ", |
writeln("Ways to select 3 from 10 types is ", |
||
CombRep(10, 3).length); |
CombRep(10, 3).length); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> iced iced |
<pre> iced iced |
||
Line 796: | Line 1,203: | ||
===Short Recursive Version=== |
===Short Recursive Version=== |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.range, std.algorithm; |
||
T[][] combsRep(T)(T[] lst, in int k) { |
T[][] combsRep(T)(T[] lst, in int k) { |
||
Line 811: | Line 1,218: | ||
["iced", "jam", "plain"].combsRep(2).writeln; |
["iced", "jam", "plain"].combsRep(2).writeln; |
||
10.iota.array.combsRep(3).length.writeln; |
10.iota.array.combsRep(3).length.writeln; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[["iced", "iced"], ["iced", "jam"], ["iced", "plain"], ["jam", "jam"], ["jam", "plain"], ["plain", "plain"]] |
<pre>[["iced", "iced"], ["iced", "jam"], ["iced", "plain"], ["jam", "jam"], ["jam", "plain"], ["plain", "plain"]] |
||
Line 818: | Line 1,225: | ||
=={{header|EasyLang}}== |
=={{header|EasyLang}}== |
||
<syntaxhighlight lang="text"> |
|||
<lang>items$[] = [ "iced" "jam" "plain" ] |
|||
items$[] = [ "iced" "jam" "plain" ] |
|||
n = len items$[] |
n = len items$[] |
||
k = 2 |
k = 2 |
||
Line 824: | Line 1,232: | ||
n_results = 0 |
n_results = 0 |
||
# |
# |
||
proc output . . |
|||
n_results += 1 |
n_results += 1 |
||
if len items$[] > 0 |
if len items$[] > 0 |
||
s$ = "" |
s$ = "" |
||
for i |
for i = 1 to k |
||
s$ &= items$[result[i]] & " " |
s$ &= items$[result[i]] & " " |
||
. |
. |
||
print s$ |
print s$ |
||
. |
. |
||
. |
. |
||
proc combine pos val . . |
|||
if pos |
if pos > k |
||
output |
|||
else |
else |
||
for i = val to n |
for i = val to n |
||
result[pos] = i |
result[pos] = i |
||
combine pos + 1 i |
|||
. |
. |
||
. |
. |
||
. |
. |
||
combine 1 1 |
|||
# |
# |
||
n = 10 |
n = 10 |
||
Line 851: | Line 1,259: | ||
items$[] = [ ] |
items$[] = [ ] |
||
n_results = 0 |
n_results = 0 |
||
combine 1 1 |
|||
print "" |
print "" |
||
print n_results & " results with 10 donuts" |
print n_results & " results with 10 donuts" |
||
</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
Line 869: | Line 1,278: | ||
=={{header|EchoLisp}}== |
=={{header|EchoLisp}}== |
||
We can use the native '''combinations/rep''' function, or use a '''combinator''' iterator, or implement the function. |
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 |
;; native function : combinations/rep in list.lib |
||
Line 912: | Line 1,321: | ||
→ 220 |
→ 220 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Egison}}== |
=={{header|Egison}}== |
||
< |
<syntaxhighlight lang="egison"> |
||
(define $comb/rep |
(define $comb/rep |
||
(lambda [$n $xs] |
(lambda [$n $xs] |
||
Line 923: | Line 1,332: | ||
(test (comb/rep 2 {"iced" "jam" "plain"})) |
(test (comb/rep 2 {"iced" "jam" "plain"})) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 931: | Line 1,340: | ||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
{{trans|Erlang}} |
{{trans|Erlang}} |
||
< |
<syntaxhighlight lang="elixir">defmodule RC do |
||
def comb_rep(0, _), do: [[]] |
def comb_rep(0, _), do: [[]] |
||
def comb_rep(_, []), do: [] |
def comb_rep(_, []), do: [] |
||
Line 942: | Line 1,351: | ||
Enum.each(RC.comb_rep(2, s), fn x -> IO.inspect x end) |
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)))}"</ |
IO.puts "\nExtra credit: #{length(RC.comb_rep(3, Enum.to_list(1..10)))}"</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 957: | Line 1,366: | ||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
< |
<syntaxhighlight lang="erlang"> |
||
-module(comb). |
-module(comb). |
||
-compile(export_all). |
-compile(export_all). |
||
Line 967: | Line 1,376: | ||
comb_rep(N,[H|T]=S) -> |
comb_rep(N,[H|T]=S) -> |
||
[[H|L] || L <- comb_rep(N-1,S)]++comb_rep(N,T). |
[[H|L] || L <- comb_rep(N-1,S)]++comb_rep(N,T). |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 979: | Line 1,388: | ||
95> length(comb:comb_rep(3,lists:seq(1,10))). |
95> length(comb:comb_rep(3,lists:seq(1,10))). |
||
220 |
220 |
||
</pre> |
|||
=={{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> |
</pre> |
||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
<syntaxhighlight lang="fortran"> |
|||
<lang Fortran> |
|||
program main |
program main |
||
integer :: chosen(4) |
integer :: chosen(4) |
||
Line 1,036: | Line 1,463: | ||
end program main |
end program main |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,046: | Line 1,473: | ||
plain plain |
plain plain |
||
Total = 6 |
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> |
</pre> |
||
=={{header|GAP}}== |
=={{header|GAP}}== |
||
< |
<syntaxhighlight lang="gap"># Built-in |
||
UnorderedTuples(["iced", "jam", "plain"], 2);</ |
UnorderedTuples(["iced", "jam", "plain"], 2);</syntaxhighlight> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
===Concise recursive=== |
===Concise recursive=== |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 1,076: | Line 1,544: | ||
fmt.Println(len(combrep(3, |
fmt.Println(len(combrep(3, |
||
[]string{"1", "2", "3", "4", "5", "6", "7", "8", "9", "10"}))) |
[]string{"1", "2", "3", "4", "5", "6", "7", "8", "9", "10"}))) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,085: | Line 1,553: | ||
===Channel=== |
===Channel=== |
||
Using channel and goroutine, showing how to use synced or unsynced communication. |
Using channel and goroutine, showing how to use synced or unsynced communication. |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 1,142: | Line 1,610: | ||
} |
} |
||
fmt.Printf("\npicking 3 of 10: %d\n", count) |
fmt.Printf("\npicking 3 of 10: %d\n", count) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,156: | Line 1,624: | ||
===Multiset=== |
===Multiset=== |
||
This version has proper representation of sets and multisets. |
This version has proper representation of sets and multisets. |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 1,257: | Line 1,725: | ||
} |
} |
||
fmt.Println(len(combrep(3, ten))) |
fmt.Println(len(combrep(3, ten))) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,270: | Line 1,738: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">-- Return the combinations, with replacement, of k items from the |
||
-- list. We ignore the case where k is greater than the length of |
-- list. We ignore the case where k is greater than the length of |
||
-- the list. |
-- the list. |
||
Line 1,293: | Line 1,761: | ||
main = do |
main = do |
||
print $ combsWithRep 2 ["iced", "jam", "plain"] |
print $ combsWithRep 2 ["iced", "jam", "plain"] |
||
print $ countCombsWithRep 3 [1 .. 10]</ |
print $ countCombsWithRep 3 [1 .. 10]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[["iced","iced"],["iced","jam"],["iced","plain"],["jam","jam"],["jam","plain"],["plain","plain"]] |
<pre>[["iced","iced"],["iced","jam"],["iced","plain"],["jam","jam"],["jam","plain"],["plain","plain"]] |
||
Line 1,302: | Line 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: |
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: |
||
< |
<syntaxhighlight lang="haskell">combsWithRep :: Int -> [a] -> [[a]] |
||
combsWithRep k xs = combsBySize xs !! k |
combsWithRep k xs = combsBySize xs !! k |
||
where |
where |
||
Line 1,309: | Line 1,777: | ||
main :: IO () |
main :: IO () |
||
main = print $ combsWithRep 2 ["iced", "jam", "plain"]</ |
main = print $ combsWithRep 2 ["iced", "jam", "plain"]</syntaxhighlight> |
||
and another approach, using manual recursion: |
and another approach, using manual recursion: |
||
<syntaxhighlight lang="haskell">--------------- COMBINATIONS WITH REPETITION ------------- |
|||
<lang haskell>combsWithRep |
|||
:: (Eq a) |
|||
combinationsWithRepetition :: |
|||
=> Int -> [a] -> [[a]] |
|||
(Eq a) => |
|||
combsWithRep k xs = comb k [] |
|||
Int -> |
|||
[a] -> |
|||
[[a]] |
|||
combinationsWithRepetition k xs = cmb k [] |
|||
where |
where |
||
cmb 0 ys = ys |
|||
cmb n [] = cmb (pred n) (pure <$> xs) |
|||
cmb n peers = cmb (pred n) (peers >>= nextLayer) |
|||
where |
|||
let nextLayer ys@(h:_) = (: ys) <$> dropWhile (/= h) xs |
|||
nextLayer [] = [] |
|||
in comb (n - 1) (foldMap nextLayer peers) |
|||
nextLayer ys@(h : _) = |
|||
(: ys) <$> dropWhile (/= h) xs |
|||
-------------------------- TESTS ------------------------- |
|||
main :: IO () |
main :: IO () |
||
main = do |
main = do |
||
print $ |
|||
print $ combsWithRep 2 ["iced", "jam", "plain"] |
|||
combinationsWithRepetition |
|||
print $ length $ combsWithRep 3 [0 .. 9]</lang> |
|||
2 |
|||
["iced", "jam", "plain"] |
|||
print $ length $ combinationsWithRepetition 3 [0 .. 9]</syntaxhighlight> |
|||
{{Out}} |
{{Out}} |
||
<pre>[["iced","iced"],["jam","iced"],["plain","iced"],["jam","jam"],["plain","jam"],["plain","plain"]] |
<pre>[["iced","iced"],["jam","iced"],["plain","iced"],["jam","jam"],["plain","jam"],["plain","plain"]] |
||
Line 1,334: | Line 1,813: | ||
Following procedure is a generator, which generates each combination of length n in turn: |
Following procedure is a generator, which generates each combination of length n in turn: |
||
<syntaxhighlight lang="icon"> |
|||
<lang Icon> |
|||
# generate all combinations of length n from list L, |
# generate all combinations of length n from list L, |
||
# including repetitions |
# including repetitions |
||
Line 1,352: | Line 1,831: | ||
} |
} |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
Test procedure: |
Test procedure: |
||
<syntaxhighlight lang="icon"> |
|||
<lang Icon> |
|||
# convenience function |
# convenience function |
||
procedure write_list (l) |
procedure write_list (l) |
||
Line 1,373: | Line 1,852: | ||
write ("There are " || count || " possible combinations of 3 from 10") |
write ("There are " || count || " possible combinations of 3 from 10") |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 1,385: | Line 1,864: | ||
There are 220 possible combinations of 3 from 10 |
There are 220 possible combinations of 3 from 10 |
||
</pre> |
</pre> |
||
=={{header|IS-BASIC}}== |
|||
<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</lang> |
|||
=={{header|J}}== |
=={{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. |
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: |
Example use: |
||
< |
<syntaxhighlight lang="j"> 2 rcomb ;:'iced jam plain' |
||
┌─────┬─────┐ |
┌─────┬─────┐ |
||
│iced │iced │ |
│iced │iced │ |
||
Line 1,422: | Line 1,887: | ||
└─────┴─────┘ |
└─────┴─────┘ |
||
#3 rcomb i.10 NB. # ways to choose 3 items from 10 with repetitions |
#3 rcomb i.10 NB. # ways to choose 3 items from 10 with repetitions |
||
220</ |
220</syntaxhighlight> |
||
===J Alternate implementation=== |
===J Alternate implementation=== |
||
Line 1,428: | Line 1,893: | ||
Considerably faster: |
Considerably faster: |
||
< |
<syntaxhighlight lang="j">require 'stats' |
||
rcomb=: (combrep #) { ]</syntaxhighlight> |
|||
combr=: i.@[ -"1~ [ comb + - 1: |
|||
rcomb=: (combr #) { ]</lang> |
|||
<code>rcomb</code> |
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 0 |
||
0 1 |
0 1 |
||
Line 1,440: | Line 1,904: | ||
1 1 |
1 1 |
||
1 2 |
1 2 |
||
2 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}}== |
=={{header|Java}}== |
||
'''MultiCombinationsTester.java''' |
'''MultiCombinationsTester.java''' |
||
< |
<syntaxhighlight lang="java"> |
||
import com.objectwave.utility.*; |
import com.objectwave.utility.*; |
||
Line 1,473: | Line 1,937: | ||
} |
} |
||
} // class |
} // class |
||
</syntaxhighlight> |
|||
</lang> |
|||
'''MultiCombinations.java''' |
'''MultiCombinations.java''' |
||
< |
<syntaxhighlight lang="java"> |
||
import com.objectwave.utility.*; |
import com.objectwave.utility.*; |
||
import java.util.*; |
import java.util.*; |
||
Line 1,525: | Line 1,989: | ||
} |
} |
||
} // class |
} // class |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 1,538: | Line 2,002: | ||
The ways to choose 3 items from 10 with replacement = 220 |
The ways to choose 3 items from 10 with replacement = 220 |
||
</pre> |
</pre> |
||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
===ES5=== |
===ES5=== |
||
====Imperative==== |
====Imperative==== |
||
< |
<syntaxhighlight lang="javascript"><html><head><title>Donuts</title></head> |
||
<body><pre id='x'></pre><script type="application/javascript"> |
<body><pre id='x'></pre><script type="application/javascript"> |
||
function disp(x) { |
function disp(x) { |
||
Line 1,564: | Line 2,029: | ||
disp(pick(2, [], 0, ["iced", "jam", "plain"], true) + " combos"); |
disp(pick(2, [], 0, ["iced", "jam", "plain"], true) + " combos"); |
||
disp("pick 3 out of 10: " + pick(3, [], 0, "a123456789".split(''), false) + " combos"); |
disp("pick 3 out of 10: " + pick(3, [], 0, "a123456789".split(''), false) + " combos"); |
||
</script></body></html></ |
</script></body></html></syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>iced iced |
<pre>iced iced |
||
Line 1,576: | Line 2,041: | ||
====Functional==== |
====Functional==== |
||
< |
<syntaxhighlight lang="javascript">(function () { |
||
// n -> [a] -> [[a]] |
// n -> [a] -> [[a]] |
||
Line 1,620: | Line 2,085: | ||
]; |
]; |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<syntaxhighlight lang="javascript">[ |
|||
<lang JavaScript>[ |
|||
[["iced", "iced"], ["iced", "jam"], ["iced", "plain"], |
[["iced", "iced"], ["iced", "jam"], ["iced", "plain"], |
||
["jam", "jam"], ["jam", "plain"], ["plain", "plain"]], |
["jam", "jam"], ["jam", "plain"], ["plain", "plain"]], |
||
220 |
220 |
||
]</ |
]</syntaxhighlight> |
||
===ES6=== |
===ES6=== |
||
{{Trans|Haskell}} |
{{Trans|Haskell}} |
||
< |
<syntaxhighlight lang="javascript">(() => { |
||
'use strict'; |
'use strict'; |
||
Line 1,693: | Line 2,158: | ||
threeFromTen: length(combsWithRep(3, enumFromTo(0, 9))) |
threeFromTen: length(combsWithRep(3, enumFromTo(0, 9))) |
||
}); |
}); |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>{ |
<pre>{ |
||
Line 1,726: | Line 2,191: | ||
=={{header|jq}}== |
=={{header|jq}}== |
||
< |
<syntaxhighlight lang="jq">def pick(n): |
||
def pick(n; m): # pick n, from m onwards |
def pick(n; m): # pick n, from m onwards |
||
if n == 0 then [] |
if n == 0 then [] |
||
Line 1,733: | Line 2,198: | ||
else ([.[m]] + pick(n-1; m)), pick(n; m+1) |
else ([.[m]] + pick(n-1; m)), pick(n; m+1) |
||
end; |
end; |
||
pick(n;0) ;</ |
pick(n;0) ;</syntaxhighlight> |
||
'''The task''': |
'''The task''': |
||
< |
<syntaxhighlight lang="jq"> "Pick 2:", |
||
(["iced", "jam", "plain"] | pick(2)), |
(["iced", "jam", "plain"] | pick(2)), |
||
([[range(0;10)] | pick(3)] | length) as $n |
([[range(0;10)] | pick(3)] | length) as $n |
||
| "There are \($n) ways to pick 3 objects with replacement from 10." |
| "There are \($n) ways to pick 3 objects with replacement from 10." |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{Out}} |
{{Out}} |
||
<pre>$ jq -n -r -c -f pick.jq |
<pre>$ jq -n -r -c -f pick.jq |
||
Line 1,754: | Line 2,219: | ||
{{works with|Julia|0.6}} |
{{works with|Julia|0.6}} |
||
< |
<syntaxhighlight lang="julia">using Combinatorics |
||
l = ["iced", "jam", "plain"] |
l = ["iced", "jam", "plain"] |
||
Line 1,762: | Line 2,227: | ||
end |
end |
||
@show length(with_replacement_combinations(1:10, 3))</ |
@show length(with_replacement_combinations(1:10, 3))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,776: | Line 2,241: | ||
=={{header|Kotlin}}== |
=={{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) { |
class CombsWithReps<T>(val m: Int, val n: Int, val items: List<T>, val countOnly: Boolean = false) { |
||
Line 1,810: | Line 2,275: | ||
CombsWithReps(2, 3, doughnuts) |
CombsWithReps(2, 3, doughnuts) |
||
println() |
println() |
||
val generic10 = "0123456789". |
val generic10 = "0123456789".chunked(1) |
||
CombsWithReps(3, 10, generic10, true) |
CombsWithReps(3, 10, generic10, true) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,834: | Line 2,299: | ||
===With List Comprehension=== |
===With List Comprehension=== |
||
< |
<syntaxhighlight lang="lisp"> |
||
(defun combinations |
(defun combinations |
||
(('() _) |
(('() _) |
||
Line 1,844: | Line 2,309: | ||
(cons head subcoll)) |
(cons head subcoll)) |
||
(combinations tail n)))) |
(combinations tail n)))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
===With Map=== |
===With Map=== |
||
< |
<syntaxhighlight lang="lisp"> |
||
(defun combinations |
(defun combinations |
||
(('() _) |
(('() _) |
||
Line 1,857: | Line 2,322: | ||
(combinations coll (- n 1))) |
(combinations coll (- n 1))) |
||
(combinations tail n)))) |
(combinations tail n)))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output is the same for both: |
Output is the same for both: |
||
< |
<syntaxhighlight lang="lisp"> |
||
> (combinations '(iced jam plain) 2) |
> (combinations '(iced jam plain) 2) |
||
((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain)) |
((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{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}}== |
=={{header|Lua}}== |
||
< |
<syntaxhighlight lang="lua">function GenerateCombinations(tList, nMaxElements, tOutput, nStartIndex, nChosen, tCurrentCombination) |
||
if not nStartIndex then |
if not nStartIndex then |
||
nStartIndex = 1 |
nStartIndex = 1 |
||
Line 1,913: | Line 2,416: | ||
end |
end |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Maple}}== |
|||
<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}}== |
=={{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). |
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). |
||
< |
<syntaxhighlight lang="mathematica">DeleteDuplicates[Tuples[{"iced", "jam", "plain"}, 2],Sort[#1] == Sort[#2] &] |
||
->{{"iced", "iced"}, {"iced", "jam"}, {"iced", "plain"}, {"jam", "jam"}, {"jam", "plain"}, {"plain", "plain"}} |
->{{"iced", "iced"}, {"iced", "jam"}, {"iced", "plain"}, {"jam", "jam"}, {"jam", "plain"}, {"plain", "plain"}} |
||
Line 1,926: | Line 2,437: | ||
Combi[10, 3] |
Combi[10, 3] |
||
->220 |
->220 |
||
</syntaxhighlight> |
|||
</lang> |
|||
A better method therefore: |
A better method therefore: |
||
< |
<syntaxhighlight lang="mathematica">CombinWithRep[S_List, k_] := Module[{occupation, assignment}, |
||
occupation = |
occupation = |
||
Flatten[Permutations /@ |
Flatten[Permutations /@ |
||
Line 1,944: | Line 2,455: | ||
Out[2]= {{"iced", "iced"}, {"jam", "jam"}, {"plain", |
Out[2]= {{"iced", "iced"}, {"jam", "jam"}, {"plain", |
||
"plain"}, {"iced", "jam"}, {"iced", "plain"}, {"jam", "plain"}} |
"plain"}, {"iced", "jam"}, {"iced", "plain"}, {"jam", "plain"}} |
||
</syntaxhighlight> |
|||
</lang> |
|||
Which can handle the Length[S] = 10, k=10 situation in still only seconds. |
Which can handle the Length[S] = 10, k=10 situation in still only seconds. |
||
Line 1,953: | Line 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. |
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. |
||
< |
<syntaxhighlight lang="mercury">:- module comb. |
||
:- interface. |
:- interface. |
||
:- import_module list, int, bag. |
:- import_module list, int, bag. |
||
Line 1,984: | Line 2,495: | ||
:- pred count(T::in, int::in, int::out) is det. |
:- pred count(T::in, int::in, int::out) is det. |
||
count(_, N0, N) :- N0 + 1 = N.</ |
count(_, N0, N) :- N0 + 1 = N.</syntaxhighlight> |
||
Usage: |
Usage: |
||
< |
<syntaxhighlight lang="mercury">:- module comb_ex. |
||
:- interface. |
:- interface. |
||
:- import_module io. |
:- import_module io. |
||
Line 2,005: | Line 2,516: | ||
mystery, cubed, cream_covered, explosive], 3, N), |
mystery, cubed, cream_covered, explosive], 3, N), |
||
io.write(L, !IO), io.nl(!IO), |
io.write(L, !IO), io.nl(!IO), |
||
io.write_string(from_int(N) ++ " choices.\n", !IO).</ |
io.write_string(from_int(N) ++ " choices.\n", !IO).</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,013: | Line 2,524: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
{{trans|D}} |
{{trans|D}} |
||
< |
<syntaxhighlight lang="nim">import sugar, sequtils |
||
proc combsReps[T](lst: seq[T], k: int): seq[seq[T]] = |
proc combsReps[T](lst: seq[T], k: int): seq[seq[T]] = |
||
Line 2,022: | Line 2,533: | ||
else: |
else: |
||
lst.combsReps(k - 1).map((x: seq[T]) => lst[0] & x) & |
lst.combsReps(k - 1).map((x: seq[T]) => lst[0] & x) & |
||
lst[1 .. |
lst[1 .. ^1].combsReps(k) |
||
echo(@["iced", "jam", "plain"].combsReps(2)) |
echo(@["iced", "jam", "plain"].combsReps(2)) |
||
echo toSeq(1..10).combsReps(3).len</ |
echo toSeq(1..10).combsReps(3).len</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>@[@[iced, iced], @[iced, jam], @[iced, plain], @[jam, jam], @[jam, plain], @[plain, plain]] |
<pre>@[@[iced, iced], @[iced, jam], @[iced, plain], @[jam, jam], @[jam, plain], @[plain, plain]] |
||
Line 2,033: | Line 2,544: | ||
{{trans|Haskell}} |
{{trans|Haskell}} |
||
< |
<syntaxhighlight lang="ocaml">let rec combs_with_rep k xxs = |
||
match k, xxs with |
match k, xxs with |
||
| 0, _ -> [[]] |
| 0, _ -> [[]] |
||
Line 2,039: | Line 2,550: | ||
| k, x::xs -> |
| k, x::xs -> |
||
List.map (fun ys -> x::ys) (combs_with_rep (k-1) xxs) |
List.map (fun ys -> x::ys) (combs_with_rep (k-1) xxs) |
||
@ combs_with_rep k xs</ |
@ combs_with_rep k xs</syntaxhighlight> |
||
in the interactive loop: |
in the interactive loop: |
||
Line 2,055: | Line 2,566: | ||
===Dynamic programming=== |
===Dynamic programming=== |
||
< |
<syntaxhighlight lang="ocaml">let combs_with_rep m xs = |
||
let arr = Array.make (m+1) [] in |
let arr = Array.make (m+1) [] in |
||
arr.(0) <- [[]]; |
arr.(0) <- [[]]; |
||
Line 2,063: | Line 2,574: | ||
done |
done |
||
) xs; |
) xs; |
||
arr.(m)</ |
arr.(m)</syntaxhighlight> |
||
in the interactive loop: |
in the interactive loop: |
||
Line 2,078: | Line 2,589: | ||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
< |
<syntaxhighlight lang="parigp">ways(k,v,s=[])={ |
||
if(k==0,return([])); |
if(k==0,return([])); |
||
if(k==1,return(vector(#v,i,concat(s,[v[i]])))); |
if(k==1,return(vector(#v,i,concat(s,[v[i]])))); |
||
Line 2,086: | Line 2,597: | ||
}; |
}; |
||
xc(k,v)=binomial(#v+k-1,k); |
xc(k,v)=binomial(#v+k-1,k); |
||
ways(2, ["iced","jam","plain"])</ |
ways(2, ["iced","jam","plain"])</syntaxhighlight> |
||
=={{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}}== |
=={{header|Perl}}== |
||
The highly readable version: |
The highly readable version: |
||
< |
<syntaxhighlight lang="perl">sub p { $_[0] ? map p($_[0] - 1, [@{$_[1]}, $_[$_]], @_[$_ .. $#_]), 2 .. $#_ : $_[1] } |
||
sub f { $_[0] ? $_[0] * f($_[0] - 1) : 1 } |
sub f { $_[0] ? $_[0] * f($_[0] - 1) : 1 } |
||
sub pn{ f($_[0] + $_[1] - 1) / f($_[0]) / f($_[1] - 1) } |
sub pn{ f($_[0] + $_[1] - 1) / f($_[0]) / f($_[1] - 1) } |
||
Line 2,099: | Line 2,723: | ||
printf "\nThere are %d ways to pick 7 out of 10\n", pn(7,10); |
printf "\nThere are %d ways to pick 7 out of 10\n", pn(7,10); |
||
</syntaxhighlight> |
|||
</lang> |
|||
Prints: |
Prints: |
||
Line 2,112: | Line 2,736: | ||
With a module: |
With a module: |
||
< |
<syntaxhighlight lang="perl">use Algorithm::Combinatorics qw/combinations_with_repetition/; |
||
my $iter = combinations_with_repetition([qw/iced jam plain/], 2); |
my $iter = combinations_with_repetition([qw/iced jam plain/], 2); |
||
while (my $p = $iter->next) { |
while (my $p = $iter->next) { |
||
Line 2,119: | Line 2,743: | ||
# Not an efficient way: generates them all in an array! |
# Not an efficient way: generates them all in an array! |
||
my $count =()= combinations_with_repetition([1..10],7); |
my $count =()= combinations_with_repetition([1..10],7); |
||
print "There are $count ways to pick 7 out of 10\n";</ |
print "There are $count ways to pick 7 out of 10\n";</syntaxhighlight> |
||
=={{header|Perl 6}}== |
|||
One could simply generate all [[Permutations_with_repetitions#Perl_6|permutations]], and then remove "duplicates": |
|||
{{works with|Rakudo|2016.07}} |
|||
<lang perl6>my @S = <iced jam plain>; |
|||
my $k = 2; |
|||
.put for [X](@S xx $k).unique(as => *.sort.cache, with => &[eqv])</lang> |
|||
{{out}} |
|||
<pre> |
|||
iced iced |
|||
iced jam |
|||
iced plain |
|||
jam jam |
|||
jam plain |
|||
plain plain |
|||
</pre> |
|||
Alternatively, a recursive solution: |
|||
{{trans|Haskell}} |
|||
<lang perl6>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 );</lang> |
|||
{{out}} |
|||
<pre>(iced iced) |
|||
(iced jam) |
|||
(iced plain) |
|||
(jam jam) |
|||
(jam plain) |
|||
(plain plain) |
|||
220</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<lang Phix>procedure choose(sequence from, integer n, at=1, sequence res={}) |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
if length(res)=n then |
|||
<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> |
|||
?res |
|||
<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> |
|||
else |
|||
<span style="color: #0000FF;">?</span><span style="color: #000000;">res</span> |
|||
for i=at to length(from) do |
|||
<span style="color: #008080;">else</span> |
|||
choose(from,n,i,append(res,from[i])) |
|||
<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> |
|||
end for |
|||
<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> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end procedure |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
choose({"iced","jam","plain"},2)</lang> |
|||
<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}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,193: | Line 2,771: | ||
The second part suggests enough differences (collecting and showing vs only counting) to strike me as ugly and confusing. |
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: |
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)--> |
|||
<lang Phix>function choices(integer from, n, at=1, taken=0) |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
integer count = 0 |
|||
<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> |
|||
if taken=n then return 1 end if |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
taken += 1 |
|||
<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> |
|||
for i=at to from do |
|||
<span style="color: #000000;">taken</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
count += choices(from,n,i,taken) |
|||
<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> |
|||
end for |
|||
<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> |
|||
return count |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">count</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
?choices(10,3)</lang> |
|||
<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}} |
{{out}} |
||
<pre> |
<pre> |
||
220 |
220 |
||
</pre> |
</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}}== |
=={{header|PHP}}== |
||
<syntaxhighlight lang="php"><?php |
|||
function combos($arr, $k) { |
|||
if ($k == 0) { |
|||
return array(array()); |
|||
} |
|||
if (count($arr) == 0) { |
|||
return array(); |
|||
} |
|||
$head = $arr[0]; |
|||
$combos = array(); |
|||
$subcombos = combos($arr, $k-1); |
|||
foreach ($subcombos as $subcombo) { |
|||
array_unshift($subcombo, $head); |
|||
$combos[] = $subcombo; |
|||
} |
|||
array_shift($arr); |
|||
$combos = array_merge($combos, combos($arr, $k)); |
|||
return $combos; |
|||
} |
|||
$arr = array("iced", "jam", "plain"); |
|||
$result = combos($arr, 2); |
|||
foreach($result as $combo) { |
|||
echo implode(' ', $combo), "<br>"; |
|||
} |
|||
$donuts = range(1, 10); |
|||
$num_donut_combos = count(combos($donuts, 3)); |
|||
echo "$num_donut_combos ways to order 3 donuts given 10 types"; |
|||
?></syntaxhighlight> |
|||
{{out}} in the browser: |
|||
<pre> |
|||
iced iced |
|||
iced jam |
|||
iced plain |
|||
jam jam |
|||
jam plain |
|||
plain plain |
|||
220 ways to order 3 donuts given 10 types |
|||
</pre> |
|||
Non-recursive algorithm to generate all combinations with repetitons. Taken from here: [https://habrahabr.ru/post/311934/] |
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. |
You must set k n variables and fill arrays b and c. |
||
<syntaxhighlight lang="php"> |
|||
<lang PHP> |
|||
<?php |
<?php |
||
//Author Ivan Gavryushin @dcc0 |
//Author Ivan Gavryushin @dcc0 |
||
Line 2,270: | Line 2,904: | ||
} |
} |
||
} |
} |
||
} |
} |
||
?> |
?> |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|PHP}}== |
|||
<lang PHP><?php |
|||
function combos($arr, $k) { |
|||
if ($k == 0) { |
|||
return array(array()); |
|||
} |
|||
if (count($arr) == 0) { |
|||
return array(); |
|||
} |
|||
$head = $arr[0]; |
|||
$combos = array(); |
|||
$subcombos = combos($arr, $k-1); |
|||
foreach ($subcombos as $subcombo) { |
|||
array_unshift($subcombo, $head); |
|||
$combos[] = $subcombo; |
|||
} |
|||
array_shift($arr); |
|||
$combos = array_merge($combos, combos($arr, $k)); |
|||
return $combos; |
|||
} |
|||
$arr = array("iced", "jam", "plain"); |
|||
$result = combos($arr, 2); |
|||
foreach($result as $combo) { |
|||
echo implode(' ', $combo), "<br>"; |
|||
} |
|||
$donuts = range(1, 10); |
|||
$num_donut_combos = count(combos($donuts, 3)); |
|||
echo "$num_donut_combos ways to order 3 donuts given 10 types"; |
|||
?></lang> |
|||
{{out}} in the browser: |
|||
<pre> |
|||
iced iced |
|||
iced jam |
|||
iced plain |
|||
jam jam |
|||
jam plain |
|||
plain plain |
|||
220 ways to order 3 donuts given 10 types |
|||
</pre> |
|||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<syntaxhighlight lang="picolisp">(de combrep (N Lst) |
||
(cond |
(cond |
||
((=0 N) '(NIL)) |
((=0 N) '(NIL)) |
||
Line 2,333: | Line 2,921: | ||
'((X) (cons (car Lst) X)) |
'((X) (cons (car Lst) X)) |
||
(combrep (dec N) Lst) ) |
(combrep (dec N) Lst) ) |
||
(combrep N (cdr Lst)) ) ) ) )</ |
(combrep N (cdr Lst)) ) ) ) )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>: (combrep 2 '(iced jam plain)) |
<pre>: (combrep 2 '(iced jam plain)) |
||
Line 2,340: | Line 2,928: | ||
: (length (combrep 3 (range 1 10))) |
: (length (combrep 3 (range 1 10))) |
||
-> 220</pre> |
-> 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}}== |
=={{header|PureBasic}}== |
||
< |
<syntaxhighlight lang="purebasic">Procedure nextCombination(Array combIndex(1), elementCount) |
||
;combIndex() must be dimensioned to 'k' - 1, elementCount equals 'n' - 1 |
;combIndex() must be dimensioned to 'k' - 1, elementCount equals 'n' - 1 |
||
;combination produced includes repetition of elements and is represented by the array combIndex() |
;combination produced includes repetition of elements and is represented by the array combIndex() |
||
Line 2,410: | Line 3,041: | ||
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input() |
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input() |
||
CloseConsole() |
CloseConsole() |
||
EndIf </ |
EndIf </syntaxhighlight>The nextCombination() procedure operates on an array of indexes to produce the next combination. This generalization allows producing a combination from any collection of elements. nextCombination() returns the value #False when the indexes have reach their maximum values and are then reset. |
||
{{out}} |
{{out}} |
||
Line 2,423: | Line 3,054: | ||
Ways to select 3 items from 10 types: 220</pre> |
Ways to select 3 items from 10 types: 220</pre> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang="python">>>> from itertools import combinations_with_replacement |
||
>>> n, k = 'iced jam plain'.split(), 2 |
>>> n, k = 'iced jam plain'.split(), 2 |
||
>>> list(combinations_with_replacement(n,k)) |
>>> list(combinations_with_replacement(n,k)) |
||
Line 2,432: | Line 3,065: | ||
>>> len(list(combinations_with_replacement(range(10), 3))) |
>>> len(list(combinations_with_replacement(range(10), 3))) |
||
220 |
220 |
||
>>> </ |
>>> </syntaxhighlight> |
||
'''References:''' |
'''References:''' |
||
Line 2,442: | Line 3,075: | ||
{{Trans|Haskell}} |
{{Trans|Haskell}} |
||
{{Works with|Python|3.7}} |
{{Works with|Python|3.7}} |
||
< |
<syntaxhighlight lang="python">'''Combinations with repetitions''' |
||
from itertools import (accumulate, chain, islice, repeat) |
from itertools import (accumulate, chain, islice, repeat) |
||
Line 2,505: | Line 3,138: | ||
# MAIN --- |
# MAIN --- |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>[('iced', 'iced'), ('jam', 'iced'), ('jam', 'jam'), ('plain', 'iced'), ('plain', 'jam'), ('plain', 'plain')] |
<pre>[('iced', 'iced'), ('jam', 'iced'), ('jam', 'jam'), ('plain', 'iced'), ('plain', 'jam'), ('plain', 'plain')] |
||
220</pre> |
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}}== |
=={{header|Racket}}== |
||
< |
<syntaxhighlight lang="racket"> |
||
#lang racket |
#lang racket |
||
(define (combinations xs k) |
(define (combinations xs k) |
||
Line 2,519: | Line 3,266: | ||
(map (λ(x) (cons (first xs) x)) |
(map (λ(x) (cons (first xs) x)) |
||
(combinations xs (- k 1))))])) |
(combinations xs (- k 1))))])) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{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}}== |
=={{header|REXX}}== |
||
===version 1=== |
===version 1=== |
||
This REXX version uses a type of anonymous recursion. |
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 3, 2, 'iced jam plain' /*The 1st part of Rosetta Code task. */ |
call RcombN 3, 2, 'iced jam plain' /*The 1st part of Rosetta Code task. */ |
||
call RcombN -10, 3, 'Iced jam plain' /* " 2nd " " " " " */ |
call RcombN -10, 3, 'Iced jam plain' /* " 2nd " " " " " */ |
||
Line 2,543: | Line 3,340: | ||
if p==z then return .(? -1); do j=? to y; @.j=p; end /*j*/; return 0 |
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</ |
show: L=; do c=1 for y; _=@.c; L=L $._; end /*c*/; say L; return</syntaxhighlight> |
||
{{out|output}} |
{{out|output}} |
||
<pre> |
<pre> |
||
Line 2,563: | Line 3,360: | ||
recursive (taken from version 1) |
recursive (taken from version 1) |
||
Reformatted and variable names suitable for OoRexx. |
Reformatted and variable names suitable for OoRexx. |
||
< |
<syntaxhighlight lang="rexx">/*REXX compute (and show) combination sets for nt things in ns places*/ |
||
debug=0 |
debug=0 |
||
Call time 'R' |
Call time 'R' |
||
Line 2,628: | Line 3,425: | ||
Say l |
Say l |
||
End |
End |
||
Return</ |
Return</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>----------- 3 doughnut selection taken 2 at a time: |
<pre>----------- 3 doughnut selection taken 2 at a time: |
||
Line 2,651: | Line 3,448: | ||
===version 3=== |
===version 3=== |
||
iterative (transformed from version 1) |
iterative (transformed from version 1) |
||
< |
<syntaxhighlight lang="rexx">/*REXX compute (and show) combination sets for nt things in ns places*/ |
||
Numeric Digits 20 |
Numeric Digits 20 |
||
debug=0 |
debug=0 |
||
Line 2,705: | Line 3,502: | ||
Say l |
Say l |
||
End |
End |
||
Return</ |
Return</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,726: | Line 3,523: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
# Project : Combinations with repetitions |
# Project : Combinations with repetitions |
||
Line 2,790: | Line 3,587: | ||
next |
next |
||
return aList |
return aList |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 2,805: | Line 3,602: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
{{works with|Ruby|2.0}} |
{{works with|Ruby|2.0}} |
||
< |
<syntaxhighlight lang="ruby">possible_doughnuts = ['iced', 'jam', 'plain'].repeated_combination(2) |
||
puts "There are #{possible_doughnuts.count} possible doughnuts:" |
puts "There are #{possible_doughnuts.count} possible doughnuts:" |
||
possible_doughnuts.each{|doughnut_combi| puts doughnut_combi.join(' and ')} |
possible_doughnuts.each{|doughnut_combi| puts doughnut_combi.join(' and ')} |
||
# Extra credit |
# Extra credit |
||
possible_doughnuts = [*1.. |
possible_doughnuts = [*1..1000].repeated_combination(30) |
||
# size returns the size of the enumerator, or nil if it can’t be calculated lazily. |
# size returns the size of the enumerator, or nil if it can’t be calculated lazily. |
||
puts "", "#{possible_doughnuts.size} ways to order |
puts "", "#{possible_doughnuts.size} ways to order 30 donuts given 1000 types." |
||
</syntaxhighlight> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,823: | Line 3,621: | ||
plain 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> |
</pre> |
||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
Scala has a combinations method in the standard library. |
Scala has a combinations method in the standard library. |
||
< |
<syntaxhighlight lang="scala"> |
||
object CombinationsWithRepetition { |
object CombinationsWithRepetition { |
||
Line 2,842: | Line 3,723: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 2,856: | Line 3,737: | ||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
{{trans|PicoLisp}} |
{{trans|PicoLisp}} |
||
< |
<syntaxhighlight lang="scheme">(define (combs-with-rep k lst) |
||
(cond ((= k 0) '(())) |
(cond ((= k 0) '(())) |
||
((null? lst) '()) |
((null? lst) '()) |
||
Line 2,868: | Line 3,749: | ||
(display (combs-with-rep 2 (list "iced" "jam" "plain"))) (newline) |
(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)</ |
(display (length (combs-with-rep 3 '(1 2 3 4 5 6 7 8 9 10)))) (newline)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,876: | Line 3,757: | ||
===Dynamic programming=== |
===Dynamic programming=== |
||
< |
<syntaxhighlight lang="scheme">(define (combs-with-rep m lst) |
||
(define arr (make-vector (+ m 1) '())) |
(define arr (make-vector (+ m 1) '())) |
||
(vector-set! arr 0 '(())) |
(vector-set! arr 0 '(())) |
||
Line 2,890: | Line 3,771: | ||
(display (combs-with-rep 2 (list "iced" "jam" "plain"))) (newline) |
(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)</ |
(display (length (combs-with-rep 3 '(1 2 3 4 5 6 7 8 9 10)))) (newline)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,899: | Line 3,780: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
{{trans|Perl}} |
{{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 |
n>0 ? (^l -> map {|k| __FUNC__(n-1, l.slice(k), [a..., l[k]]) }) : a |
||
} |
} |
||
Line 2,905: | Line 3,786: | ||
cwr(2, %w(iced jam plain)).each {|a| |
cwr(2, %w(iced jam plain)).each {|a| |
||
say a.map{ .join(' ') }.join("\n") |
say a.map{ .join(' ') }.join("\n") |
||
}</ |
}</syntaxhighlight> |
||
Also built-in: |
Also built-in: |
||
< |
<syntaxhighlight lang="ruby">%w(iced jam plain).combinations_with_repetition(2, {|*a| |
||
say a.join(' ') |
say a.join(' ') |
||
})</ |
})</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,924: | Line 3,805: | ||
Efficient count of the total number of combinations with repetition: |
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))</ |
printf("\nThere are %s ways to pick 7 out of 10 with repetition\n", cwr_count(10, 7))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,934: | Line 3,815: | ||
{{trans|Haskell}} |
{{trans|Haskell}} |
||
< |
<syntaxhighlight lang="sml">let rec combs_with_rep k xxs = |
||
match k, xxs with |
match k, xxs with |
||
| 0, _ -> [[]] |
| 0, _ -> [[]] |
||
Line 2,940: | Line 3,821: | ||
| k, x::xs -> |
| k, x::xs -> |
||
List.map (fun ys -> x::ys) (combs_with_rep (k-1) xxs) |
List.map (fun ys -> x::ys) (combs_with_rep (k-1) xxs) |
||
@ combs_with_rep k xs</ |
@ combs_with_rep k xs</syntaxhighlight> |
||
in the interactive loop: |
in the interactive loop: |
||
Line 2,955: | Line 3,836: | ||
===Dynamic programming=== |
===Dynamic programming=== |
||
< |
<syntaxhighlight lang="sml">fun combs_with_rep (m, xs) = let |
||
val arr = Array.array (m+1, []) |
val arr = Array.array (m+1, []) |
||
in |
in |
||
Line 2,965: | Line 3,846: | ||
) xs; |
) xs; |
||
Array.sub (arr, m) |
Array.sub (arr, m) |
||
end</ |
end</syntaxhighlight> |
||
in the interactive loop: |
in the interactive loop: |
||
Line 2,980: | Line 3,861: | ||
=={{header|Stata}}== |
=={{header|Stata}}== |
||
< |
<syntaxhighlight lang="stata">function combrep(v,k) { |
||
n = cols(v) |
n = cols(v) |
||
a = J(comb(n+k-1,k),k,v[1]) |
a = J(comb(n+k-1,k),k,v[1]) |
||
Line 2,998: | Line 3,879: | ||
a = combrep(1..10,3) |
a = combrep(1..10,3) |
||
rows(a)</ |
rows(a)</syntaxhighlight> |
||
'''Output''' |
'''Output''' |
||
Line 3,015: | Line 3,896: | ||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
< |
<syntaxhighlight lang="swift">func combosWithRep<T>(var objects: [T], n: Int) -> [[T]] { |
||
if n == 0 { return [[]] } else { |
if n == 0 { return [[]] } else { |
||
var combos = [[T]]() |
var combos = [[T]]() |
||
Line 3,025: | Line 3,906: | ||
} |
} |
||
} |
} |
||
print(combosWithRep(["iced", "jam", "plain"], n: 2).map {$0.joinWithSeparator(" and ")}.joinWithSeparator("\n"))</ |
print(combosWithRep(["iced", "jam", "plain"], n: 2).map {$0.joinWithSeparator(" and ")}.joinWithSeparator("\n"))</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>plain and plain |
<pre>plain and plain |
||
Line 3,035: | Line 3,916: | ||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
< |
<syntaxhighlight lang="tcl">package require Tcl 8.5 |
||
proc combrepl {set n {presorted no}} { |
proc combrepl {set n {presorted no}} { |
||
if {!$presorted} { |
if {!$presorted} { |
||
Line 3,057: | Line 3,938: | ||
puts [combrepl {iced jam plain} 2] |
puts [combrepl {iced jam plain} 2] |
||
puts [llength [combrepl {1 2 3 4 5 6 7 8 9 10} 3]]</ |
puts [llength [combrepl {1 2 3 4 5 6 7 8 9 10} 3]]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,063: | Line 3,944: | ||
220 |
220 |
||
</pre> |
</pre> |
||
=={{header|TXR}}== |
=={{header|TXR}}== |
||
< |
<syntaxhighlight lang="dos">txr -p "(rcomb '(iced jam plain) 2)"</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,070: | Line 3,952: | ||
</pre> |
</pre> |
||
---- |
---- |
||
< |
<syntaxhighlight lang="dos">txr -p "(length-list (rcomb '(0 1 2 3 4 5 6 7 8 9) 3))"</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,077: | Line 3,959: | ||
=={{header|Ursala}}== |
=={{header|Ursala}}== |
||
< |
<syntaxhighlight lang="ursala">#import std |
||
#import nat |
#import nat |
||
Line 3,084: | Line 3,966: | ||
#cast %gLSnX |
#cast %gLSnX |
||
main = ^|(~&,length) cwr~~/(<'iced','jam','plain'>,2) ('1234567890',3)</ |
main = ^|(~&,length) cwr~~/(<'iced','jam','plain'>,2) ('1234567890',3)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,096: | Line 3,978: | ||
<'plain','plain'>}, |
<'plain','plain'>}, |
||
220) |
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> |
</pre> |
||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
< |
<syntaxhighlight lang="xpl0">code ChOut=8, CrLf=9, IntOut=11, Text=12; |
||
int Count, Array(10); |
int Count, Array(10); |
||
Line 3,126: | Line 4,106: | ||
Combos(0, 0, 3, 10, [0]); |
Combos(0, 0, 3, 10, [0]); |
||
Text(0, "Combos = "); IntOut(0, Count); CrLf(0); |
Text(0, "Combos = "); IntOut(0, Count); CrLf(0); |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,142: | Line 4,122: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{trans|Clojure}} |
{{trans|Clojure}} |
||
< |
<syntaxhighlight lang="zkl">fcn combosK(k,seq){ // repeats, seq is finite |
||
if (k==1) return(seq); |
if (k==1) return(seq); |
||
if (not seq) return(T); |
if (not seq) return(T); |
||
self.fcn(k-1,seq).apply(T.extend.fp(seq[0])).extend(self.fcn(k,seq[1,*])); |
self.fcn(k-1,seq).apply(T.extend.fp(seq[0])).extend(self.fcn(k,seq[1,*])); |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">combosK(2,T("iced","jam","plain")).apply("concat",","); |
||
combosK(3,T(0,1,2,3,4,5,6,7,8,9)).len();</ |
combosK(3,T(0,1,2,3,4,5,6,7,8,9)).len();</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,156: | Line 4,136: | ||
=={{header|ZX Spectrum Basic}}== |
=={{header|ZX Spectrum Basic}}== |
||
< |
<syntaxhighlight lang="zxbasic">10 READ n |
||
20 DIM d$(n,5) |
20 DIM d$(n,5) |
||
30 FOR i=1 TO n |
30 FOR i=1 TO n |
||
Line 3,166: | Line 4,146: | ||
90 PRINT d$(i);" ";d$(j) |
90 PRINT d$(i);" ";d$(j) |
||
100 NEXT j |
100 NEXT j |
||
110 NEXT i</ |
110 NEXT i</syntaxhighlight> |
Latest revision as of 11:29, 20 November 2023
You are encouraged to solve this task according to the task description, using any language you may know.
The set of combinations with repetitions is computed from a set, (of cardinality ), and a size of resulting selection, , by reporting the sets of cardinality where each member of those sets is chosen from . In the real world, it is about choosing sets where there is a “large” supply of each type of element and where the order of choice does not matter. For example:
- Q: How many ways can a person choose two doughnuts from a store selling three types of doughnut: iced, jam, and plain? (i.e., is , , and .)
- A: 6: {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
- See also
The number of samples of size k from n objects.
With combinations and permutations generation tasks.
Order Unimportant Order Important Without replacement Task: Combinations Task: Permutations With replacement Task: Combinations with repetitions Task: Permutations with repetitions
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)
- Output:
[[iced, iced], [iced, jam], [iced, plain], [jam, jam], [jam, plain], [plain, plain]] 220
360 Assembly
* Combinations with repetitions - 16/04/2019
COMBREP CSECT
USING COMBREP,R13 base register
B 72(R15) skip savearea
DC 17F'0' savearea
SAVE (14,12) save previous context
ST R13,4(R15) link backward
ST R15,8(R13) link forward
LR R13,R15 set addressability
MVC FLAVORS(9),SET1 flavors=3,draws=2,tell=1
BAL R14,COMBINE call combine
MVC FLAVORS(9),SET2 flavors=10,draws=3,tell=0
BAL R14,COMBINE call combine
L R13,4(0,R13) restore previous savearea pointer
RETURN (14,12),RC=0 restore registers from calling sav
COMBINE SR R9,R9 n=0
MVI V,X'00' ~
MVC V+1(NN*L'V-1),V v=0
IF CLI,TELL,EQ,X'01' THEN if tell then
XPRNT =C'list:',5 print
ENDIF , endif
LOOP LA R6,1 i=1
DO WHILE=(C,R6,LE,DRAWS) do i=1 to draws
LR R1,R6 i
SLA R1,2 ~
L R2,V-4(R1) v(i)
L R3,FLAVORS flavors
BCTR R3,0 flavors-1
IF CR,R2,GT,R3 THEN if v(i)>flavors-1 then
LR R1,R6 i
SLA R1,2 ~
LA R1,V(R1) @v(i+1)
L R2,0(R1) v(i+1)
LA R2,1(R2) v(i+1)+1
ST R2,0(R1) v(i+1)=v(i+1)+1
LR R7,R6 j=i
DO WHILE=(C,R7,GE,=A(1)) do j=i to 1 by -1
LR R1,R6 i
SLA R1,2 ~
L R2,V(R1) v(i+1)
LR R1,R7 j
SLA R1,2 ~
ST R2,V-4(R1) v(j)=v(i+1)
BCTR R7,0 j--
ENDDO , enddo j
ENDIF , endif
LA R6,1(R6) i++
ENDDO , enddo i
L R1,DRAWS draws
LA R1,1(R1) draws+1
SLA R1,2 ~
L R2,V-4(R1) v(draws+1)
LTR R2,R2 if v(draws+1)>0
BP EXITLOOP then exit loop
LA R9,1(R9) n=n+1
IF CLI,TELL,EQ,X'01' THEN if tell then
MVC BUF,=CL60' ' buf=' '
LA R10,1 ibuf=1
LA R6,1 i=1
DO WHILE=(C,R6,LE,DRAWS) do i=1 to draws
LR R1,R6 i
SLA R1,2 ~
L R1,V-4(R1) v(i)
MH R1,=AL2(L'ITEMS) ~
LA R4,ITEMS(R1) @items(v(i)+1)
LA R5,BUF-1 @buf-1
AR R5,R10 +ibuf
MVC 0(6,R5),0(R4) substr(buf,ibuf,6)=items(v(i)+1)
LA R10,L'ITEMS(R10) ibuf=ibuf+length(items)
LA R6,1(R6) i++
ENDDO , enddo i
XPRNT BUF,L'BUF print buf
ENDIF , endif
L R2,V v(1)
LA R2,1(R2) v(1)+1
ST R2,V v(1)=v(1)+1
B LOOP loop
EXITLOOP L R1,FLAVORS flavors
XDECO R1,XDEC edit flavors
MVC PG+4(2),XDEC+10 output flavors
L R1,DRAWS draws
XDECO R1,XDEC edit draws
MVC PG+7(2),XDEC+10 output draws
XDECO R9,PG+11 edit & output n
XPRNT PG,L'PG print buffer
BR R14 return
NN EQU 16
ITEMS DC CL6'iced',CL6'jam',CL6'plain'
FLAVORS DS F
DRAWS DS F
TELL DS X
SET1 DC F'3',F'2',X'01' flavors=3,draws=2,tell=1
SET2 DC F'10',F'3',X'00' flavors=10,draws=3,tell=0
V DS (NN)F v(nn)
BUF DS CL60 buf
PG DC CL40'cwr(..,..)=............'
XDEC DS CL12 temp for xdeco
REGEQU
END COMBREP
- Output:
list: iced iced jam iced plain iced jam jam plain jam plain plain cwr( 3, 2)= 6 cwr(10, 3)= 220
Acornsoft Lisp
(defun samples (k items)
(cond
((zerop k) '(()))
((null items) '())
(t (append
(mapc '(lambda (c) (cons (car items) c))
(samples (sub1 k) items))
(samples k (cdr items))))))
(defun append (a b)
(cond ((null a) b)
(t (cons (car a) (append (cdr a) b)))))
(defun length (list (len . 0))
(map '(lambda (e) (setq len (add1 len)))
list)
len)
- Output:
Evaluate : (samples 2 '(iced jam plain)) Value is : ((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain)) Evaluate : (length (samples 3 '(1 2 3 4 5 6 7 8 9 10))) Value is : 220
Action!
PROC PrintComb(BYTE ARRAY c BYTE len)
BYTE i,ind
FOR i=0 TO len-1
DO
IF i>0 THEN Put('+) FI
ind=c(i)
IF ind=0 THEN
Print("iced")
ELSEIF ind=1 THEN
Print("jam")
ELSE
Print("plain")
FI
OD
PutE()
RETURN
BYTE FUNC NotDecreasing(BYTE ARRAY c BYTE len)
BYTE i
IF len<2 THEN RETURN (1) FI
FOR i=0 TO len-2
DO
IF c(i)>c(i+1) THEN
RETURN (0)
FI
OD
RETURN (1)
BYTE FUNC NextComb(BYTE ARRAY c BYTE n,k)
INT pos,i
DO
pos=k-1
DO
c(pos)==+1
IF c(pos)<n THEN
EXIT
ELSE
pos==-1
IF pos<0 THEN RETURN (0) FI
FI
FOR i=pos+1 TO k-1
DO
c(i)=c(pos)
OD
OD
UNTIL NotDecreasing(c,k)
OD
RETURN (1)
PROC Comb(BYTE n,k,show)
BYTE ARRAY c(10)
BYTE i,count
IF k>n THEN
Print("Error! k is greater than n.")
Break()
FI
PrintF("Choices of %B from %B:%E",k,n)
FOR i=0 TO k-1
DO
c(i)=0
OD
count=0
DO
count==+1
IF show THEN
PrintF(" %B. ",count)
PrintComb(c,k)
FI
UNTIL NextComb(c,n,k)=0
OD
PrintF("Total choices %B%E%E",count)
RETURN
PROC Main()
Comb(3,2,1)
Comb(10,3,0)
RETURN
- Output:
Screenshot from Atari 8-bit computer
Choices of 2 from 3: 1. iced+iced 2. iced+jam 3. iced+plain 4. jam+jam 5. jam+plain 6. plain+plain Total choices 6 Choices of 3 from 10: Total choices 220
Ada
Should work for any discrete type: integer, modular, or enumeration.
combinations.adb:
with Ada.Text_IO;
procedure Combinations is
generic
type Set is (<>);
function Combinations
(Count : Positive;
Output : Boolean := False)
return Natural;
function Combinations
(Count : Positive;
Output : Boolean := False)
return Natural
is
package Set_IO is new Ada.Text_IO.Enumeration_IO (Set);
type Set_Array is array (Positive range <>) of Set;
Empty_Array : Set_Array (1 .. 0);
function Recurse_Combinations
(Number : Positive;
First : Set;
Prefix : Set_Array)
return Natural
is
Combination_Count : Natural := 0;
begin
for Next in First .. Set'Last loop
if Number = 1 then
Combination_Count := Combination_Count + 1;
if Output then
for Element in Prefix'Range loop
Set_IO.Put (Prefix (Element));
Ada.Text_IO.Put ('+');
end loop;
Set_IO.Put (Next);
Ada.Text_IO.New_Line;
end if;
else
Combination_Count := Combination_Count +
Recurse_Combinations
(Number - 1,
Next,
Prefix & (1 => Next));
end if;
end loop;
return Combination_Count;
end Recurse_Combinations;
begin
return Recurse_Combinations (Count, Set'First, Empty_Array);
end Combinations;
type Donuts is (Iced, Jam, Plain);
function Donut_Combinations is new Combinations (Donuts);
subtype Ten is Positive range 1 .. 10;
function Ten_Combinations is new Combinations (Ten);
Donut_Count : constant Natural :=
Donut_Combinations (Count => 2, Output => True);
Ten_Count : constant Natural := Ten_Combinations (Count => 3);
begin
Ada.Text_IO.Put_Line ("Total Donuts:" & Natural'Image (Donut_Count));
Ada.Text_IO.Put_Line ("Total Tens:" & Natural'Image (Ten_Count));
end Combinations;
- Output:
ICED+ICED ICED+JAM ICED+PLAIN JAM+JAM JAM+PLAIN PLAIN+PLAIN Total Donuts: 6 Total Tens: 220
AppleScript
--------------- COMBINATIONS WITH REPETITION -------------
-- combinationsWithRepetition :: Int -> [a] -> [kTuple a]
on combinationsWithRepetition(k, xs)
-- A list of lists, representing
-- sets of cardinality k, with
-- members drawn from xs.
script combinationsBySize
script f
on |λ|(a, x)
script prefix
on |λ|(z)
{x} & z
end |λ|
end script
script go
on |λ|(ys, xs)
xs & map(prefix, ys)
end |λ|
end script
scanl1(go, a)
end |λ|
end script
on |λ|(xs)
foldl(f, {{{}}} & take(k, |repeat|({})), xs)
end |λ|
end script
|Just| of |index|(|λ|(xs) of combinationsBySize, 1 + k)
end combinationsWithRepetition
--------------------------- TEST -------------------------
on run
{length of combinationsWithRepetition(3, enumFromTo(0, 9)), ¬
combinationsWithRepetition(2, {"iced", "jam", "plain"})}
end run
------------------------- GENERIC ------------------------
-- Just :: a -> Maybe a
on Just(x)
{type:"Maybe", Nothing:false, Just:x}
end Just
-- Nothing :: Maybe a
on Nothing()
{type:"Maybe", Nothing:true}
end Nothing
-- enumFromTo :: (Int, Int) -> [Int]
on enumFromTo(m, n)
if m ≤ n then
set lst to {}
repeat with i from m to n
set end of lst to i
end repeat
return lst
else
return {}
end if
end enumFromTo
-- foldl :: (a -> b -> a) -> a -> [b] -> a
on foldl(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
repeat with i from 1 to lng
set v to |λ|(v, item i of xs, i, xs)
end repeat
return v
end tell
end foldl
-- index (!!) :: [a] -> Int -> Maybe a
-- index (!!) :: Gen [a] -> Int -> Maybe a
-- index (!!) :: String -> Int -> Maybe Char
on |index|(xs, i)
if script is class of xs then
repeat with j from 1 to i
set v to |λ|() of xs
end repeat
if missing value is not v then
Just(v)
else
Nothing()
end if
else
if length of xs < i then
Nothing()
else
Just(item i of xs)
end if
end if
end |index|
-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to |λ|(item i of xs, i, xs)
end repeat
return lst
end tell
end map
-- min :: Ord a => a -> a -> a
on min(x, y)
if y < x then
y
else
x
end if
end min
-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
if script is class of f then
f
else
script
property |λ| : f
end script
end if
end mReturn
-- repeat :: a -> Generator [a]
on |repeat|(x)
script
on |λ|()
return x
end |λ|
end script
end |repeat|
-- scanl :: (b -> a -> b) -> b -> [a] -> [b]
on scanl(f, startValue, xs)
tell mReturn(f)
set v to startValue
set lng to length of xs
set lst to {startValue}
repeat with i from 1 to lng
set v to |λ|(v, item i of xs, i, xs)
set end of lst to v
end repeat
return lst
end tell
end scanl
-- scanl1 :: (a -> a -> a) -> [a] -> [a]
on scanl1(f, xs)
if 0 < length of xs then
scanl(f, item 1 of xs, rest of xs)
else
{}
end if
end scanl1
-- take :: Int -> [a] -> [a]
-- take :: Int -> String -> String
on take(n, xs)
set c to class of xs
if list is c then
if 0 < n then
items 1 thru min(n, length of xs) of xs
else
{}
end if
else if string is c then
if 0 < n then
text 1 thru min(n, length of xs) of xs
else
""
end if
else if script is c then
set ys to {}
repeat with i from 1 to n
set v to |λ|() of xs
if missing value is v then
return ys
else
set end of ys to v
end if
end repeat
return ys
else
missing value
end if
end take
- Output:
{220, {{"iced", "iced"}, {"jam", "iced"}, {"jam", "jam"}, {"plain", "iced"}, {"plain", "jam"}, {"plain", "plain"}}}
Arturo
print combine.repeated.by:2 ["iced" "jam" "plain"]
print combine.count.repeated.by:3 @1..10
- Output:
[iced iced] [iced jam] [iced plain] [jam jam] [jam plain] [plain plain] 220
AutoHotkey
;===========================================================
; based on "https://www.geeksforgeeks.org/combinations-with-repetitions/"
;===========================================================
CombinationRepetition(arr, k:=0, Delim:="") {
CombinationRepetitionUtil(arr, k?k:str.count(), Delim, [k+1], result:=[])
return result
} ;===========================================================
CombinationRepetitionUtil(arr, k, Delim, chosen, result , index:=1, start:=1){
line := [], i:=0, res := ""
if (index = k+1){
while (++i <= k)
res .= arr[chosen[i]] Delim, line.push(arr[chosen[i]])
return result.Push(Trim(res, Delim))
}
i:=start
while (i <= arr.count())
chosen[Index]:=i, CombinationRepetitionUtil(arr, k, Delim, chosen, result, index+1, i++)
} ;===========================================================
Examples:
result := CombinationRepetition(["iced","jam","plain"], 2, " + ")
for k, v in result
res .= v "`n"
res := trim(res, ",") "`n"
MsgBox % result.count() " Combinations with Repetition found:`n" res
MsgBox % CombinationRepetition([0,1,2,3,4,5,6,7,8,9], 3).Count()
Outputs:
--------------------------- 6 Combinations with Repetition found: iced + iced iced + jam iced + plain jam + jam jam + plain plain + plain --------------------------- 220 ---------------------------
AWK
# syntax: GAWK -f COMBINATIONS_WITH_REPETITIONS.AWK
BEGIN {
n = split("iced,jam,plain",donuts,",")
for (i=1; i<=n; i++) {
for (j=1; j<=n; j++) {
if (donuts[i] < donuts[j]) {
key = sprintf("%s %s",donuts[i],donuts[j])
}
else {
key = sprintf("%s %s",donuts[j],donuts[i])
}
arr[key]++
}
}
cmd = "SORT"
for (i in arr) {
printf("%s\n",i) | cmd
choices++
}
close(cmd)
printf("choices = %d\n",choices)
exit(0)
}
output:
iced iced iced jam iced plain jam jam jam plain plain plain choices = 6
BASIC
BASIC256
arraybase 0
print "Enter n comb m. "
input integer "n: ", n
input integer "m: ", m
outstr$ = ""
dim names$(m)
for i = 0 to m - 1
print "Name for item "; i; ": ";
input string names$[i]
next i
call iterate (outstr$, 0, m-1, n-1, names$)
end
subroutine iterate(curr$, start, stp, depth, names$)
for i = start to stp
if depth = 0 then
print curr$; " "; names$[i]
else
call iterate (curr$ & " " & names$[i], i, stp, depth-1, names$)
end if
next i
return
end subroutine
BBC BASIC
DIM list$(2), chosen%(2)
list$() = "iced", "jam", "plain"
PRINT "Choices of 2 from 3:"
choices% = FNchoose(0, 2, 0, 3, chosen%(), list$())
PRINT "Total choices = " ; choices%
PRINT '"Choices of 3 from 10:"
choices% = FNchoose(0, 3, 0, 10, chosen%(), nul$())
PRINT "Total choices = " ; choices%
END
DEF FNchoose(n%, l%, p%, m%, g%(), RETURN n$())
LOCAL i%, c%
IF n% = l% THEN
IF !^n$() THEN
FOR i% = 0 TO n%-1
PRINT " " n$(g%(i%)) ;
NEXT
PRINT
ENDIF
= 1
ENDIF
FOR i% = p% TO m%-1
g%(n%) = i%
c% += FNchoose(n% + 1, l%, i%, m%, g%(), n$())
NEXT
= c%
- Output:
Choices of 2 from 3: iced iced iced jam iced plain jam jam jam plain plain plain Total choices = 6 Choices of 3 from 10: Total choices = 220
IS-BASIC
100 PROGRAM "Combinat.bas"
110 READ N
120 STRING D$(1 TO N)*5
130 FOR I=1 TO N
140 READ D$(I)
150 NEXT
160 FOR I=1 TO N
170 FOR J=I TO N
180 PRINT D$(I);" ";D$(J)
190 NEXT
200 NEXT
210 DATA 3,iced,jam,plain
Bracmat
This minimalist solution expresses the answer as a sum of products. Bracmat automatically normalises such expressions: terms and factors are sorted alphabetically, products containing a sum as a factor are decomposed in a sum of factors (unless the product is not itself term in a multiterm expression). Like factors are converted to a single factor with an appropriate exponent, so ice^2
is to be understood as ice twice.
( ( choices
= n things thing result
. !arg:(?n.?things)
& ( !n:0&1
| 0:?result
& ( !things
: ?
( %?`thing ?:?things
& !thing*choices$(!n+-1.!things)+!result
: ?result
& ~
)
| !result
)
)
)
& out$(choices$(2.iced jam plain))
& out$(choices$(3.iced jam plain butter marmite tahin fish salad onion grass):?+[?N&!N)
);
- Output:
iced^2+jam^2+plain^2+iced*jam+iced*plain+jam*plain 220
C
Non recursive solution
#include <stdio.h>
const char *donuts[] = {"iced", "jam", "plain",
"something completely different"};
int pos[] = {0, 0, 0, 0};
void printDonuts(int k) {
for (size_t i = 1; i < k + 1; i += 1) // offset: i:1..N, N=k+1
printf("%s\t", donuts[pos[i]]); // str:0..N-1
printf("\n");
}
// idea: custom number system with 2s complement like 0b10...0==MIN stop case
void combination_with_repetiton(int n, int k) {
while (1) {
for (int i = k; i > 0; i -= 1) {
if (pos[i] > n - 1) // if number spilled over: xx0(n-1)xx
{
pos[i - 1] += 1; // set xx1(n-1)xx
for (int j = i; j <= k; j += 1)
pos[j] = pos[j - 1]; // set xx11..1
}
}
if (pos[0] > 0) // stop condition: 1xxxx
break;
printDonuts(k);
pos[k] += 1; // xxxxN -> xxxxN+1
}
}
int main() {
combination_with_repetiton(3, 2);
return 0;
}
#include <stdio.h>
const char * donuts[] = { "iced", "jam", "plain", "something completely different" };
long choose(int * got, int n_chosen, int len, int at, int max_types)
{
int i;
long count = 0;
if (n_chosen == len) {
if (!got) return 1;
for (i = 0; i < len; i++)
printf("%s\t", donuts[got[i]]);
printf("\n");
return 1;
}
for (i = at; i < max_types; i++) {
if (got) got[n_chosen] = i;
count += choose(got, n_chosen + 1, len, i, max_types);
}
return count;
}
int main()
{
int chosen[3];
choose(chosen, 0, 2, 0, 3);
printf("\nWere there ten donuts, we'd have had %ld choices of three\n",
choose(0, 0, 3, 0, 10));
return 0;
}
- Output:
iced icediced jam iced plain jam jam jam plain plain plain
Were there ten donuts, we'd have had 220 choices of three
C#
using System;
using System.Collections.Generic;
using System.Linq;
public static class MultiCombinations
{
private static void Main()
{
var set = new List<string> { "iced", "jam", "plain" };
var combinations = GenerateCombinations(set, 2);
foreach (var combination in combinations)
{
string combinationStr = string.Join(" ", combination);
Console.WriteLine(combinationStr);
}
var donuts = Enumerable.Range(1, 10).ToList();
int donutsCombinationsNumber = GenerateCombinations(donuts, 3).Count;
Console.WriteLine("{0} ways to order 3 donuts given 10 types", donutsCombinationsNumber);
}
private static List<List<T>> GenerateCombinations<T>(List<T> combinationList, int k)
{
var combinations = new List<List<T>>();
if (k == 0)
{
var emptyCombination = new List<T>();
combinations.Add(emptyCombination);
return combinations;
}
if (combinationList.Count == 0)
{
return combinations;
}
T head = combinationList[0];
var copiedCombinationList = new List<T>(combinationList);
List<List<T>> subcombinations = GenerateCombinations(copiedCombinationList, k - 1);
foreach (var subcombination in subcombinations)
{
subcombination.Insert(0, head);
combinations.Add(subcombination);
}
combinationList.RemoveAt(0);
combinations.AddRange(GenerateCombinations(combinationList, k));
return combinations;
}
}
- Output:
iced iced iced jam iced plain jam jam jam plain plain plain 220 ways to order 3 donuts given 10 types
Recursive version
using System;
class MultiCombination
{
static string [] set = { "iced", "jam", "plain" };
static int k = 2, n = set.Length;
static string [] buf = new string [k];
static void Main()
{
rec(0, 0);
}
static void rec(int ind, int begin)
{
for (int i = begin; i < n; i++)
{
buf [ind] = set[i];
if (ind + 1 < k) rec(ind + 1, i);
else Console.WriteLine(string.Join(",", buf));
}
}
}
C++
Non recursive version.
#include <iostream>
#include <string>
#include <vector>
void print_vector(const std::vector<int> &pos,
const std::vector<std::string> &str) {
for (size_t i = 1; i < pos.size(); ++i) // offset: i:1..N
printf("%s\t", str[pos[i]].c_str()); // str: 0..N-1
printf("\n");
}
// idea: custom number system with 2s complement like 0b10...0==MIN stop case
void combination_with_repetiton(int n, int k,
const std::vector<std::string> &str) {
std::vector<int> pos(k + 1, 0);
while (true) {
for (int i = k; i > 0; i -= 1) {
if (pos[i] > n - 1) // if number spilled over: xx0(n-1)xx
{
pos[i - 1] += 1; // set xx1(n-1)xx
for (int j = i; j <= k; j += 1)
pos[j] = pos[j - 1]; // set xx11..1
}
}
if (pos[0] > 0) // stop condition: 1xxxx
break;
print_vector(pos, str);
pos[k] += 1; // xxxxN -> xxxxN+1
}
}
int main() {
std::vector<std::string> str{"iced", "jam", "plain"};
combination_with_repetiton(3, 2, str);
return 0;
}
- Output:
iced iced iced jam iced plain jam jam jam plain plain plain
Clojure
(defn combinations [coll k]
(when-let [[x & xs] coll]
(if (= k 1)
(map list coll)
(concat (map (partial cons x) (combinations coll (dec k)))
(combinations xs k)))))
- Output:
user> (combinations '[iced jam plain] 2) ((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))
CoffeeScript
combos = (arr, k) ->
return [ [] ] if k == 0
return [] if arr.length == 0
combos_with_head = ([arr[0]].concat combo for combo in combos arr, k-1)
combos_sans_head = combos arr[1...], k
combos_with_head.concat combos_sans_head
arr = ['iced', 'jam', 'plain']
console.log "valid pairs from #{arr.join ','}:"
console.log combos arr, 2
console.log "#{combos([1..10], 3).length} ways to order 3 donuts given 10 types"
- Output:
jam,plain: [ [ 'iced', 'iced' ], [ 'iced', 'jam' ], [ 'iced', 'plain' ], [ 'jam', 'jam' ], [ 'jam', 'plain' ], [ 'plain', 'plain' ] ] 220 ways to order 3 donuts given 10 types
Common Lisp
The code below is a modified version of the Clojure solution.
(defun combinations (xs k)
(let ((x (car xs)))
(cond
((null xs) nil)
((= k 1) (mapcar #'list xs))
(t (append (mapcar (lambda (ys) (cons x ys))
(combinations xs (1- k)))
(combinations (cdr xs) k))))))
- Output:
((:ICED :ICED) (:ICED :JAM) (:ICED :PLAIN) (:JAM :JAM) (:JAM :PLAIN) (:PLAIN :PLAIN))
Crystal
possible_doughnuts = ["iced", "jam", "plain"].repeated_combinations(2)
puts "There are #{possible_doughnuts.size} possible doughnuts:"
possible_doughnuts.each{|doughnut_combi| puts doughnut_combi.join(" and ")}
# Extra credit
possible_doughnuts = (1..10).to_a.repeated_combinations(3)
# size returns the size of the enumerator, or nil if it can’t be calculated lazily.
puts "", "#{possible_doughnuts.size} ways to order 3 donuts given 10 types."
- Output:
There are 6 possible doughnuts: iced and iced iced and jam iced and plain jam and jam jam and plain plain and plain 220 ways to order 3 donuts given 10 types.
D
Using lexicographic next bit permutation to generate combinations with repetitions.
import std.stdio, std.range;
const struct CombRep {
immutable uint nt, nc;
private const ulong[] combVal;
this(in uint numType, in uint numChoice) pure nothrow @safe
in {
assert(0 < numType && numType + numChoice <= 64,
"Valid only for nt + nc <= 64 (ulong bit size)");
} body {
nt = numType;
nc = numChoice;
if (nc == 0)
return;
ulong v = (1UL << (nt - 1)) - 1;
// Init to smallest number that has nt-1 bit set
// a set bit is metaphored as a _type_ seperator.
immutable limit = v << nc;
ulong[] localCombVal;
// Limit is the largest nt-1 bit set number that has nc
// zero-bit a zero-bit means a _choice_ between _type_
// seperators.
while (v <= limit) {
localCombVal ~= v;
if (v == 0)
break;
// Get next nt-1 bit number.
immutable t = (v | (v - 1)) + 1;
v = t | ((((t & -t) / (v & -v)) >> 1) - 1);
}
this.combVal = localCombVal;
}
uint length() @property const pure nothrow @safe {
return combVal.length;
}
uint[] opIndex(in uint idx) const pure nothrow @safe {
return val2set(combVal[idx]);
}
int opApply(immutable int delegate(in ref uint[]) pure nothrow @safe dg)
pure nothrow @safe {
foreach (immutable v; combVal) {
auto set = val2set(v);
if (dg(set))
break;
}
return 1;
}
private uint[] val2set(in ulong v) const pure nothrow @safe {
// Convert bit pattern to selection set
immutable uint bitLimit = nt + nc - 1;
uint typeIdx = 0;
uint[] set;
foreach (immutable bitNum; 0 .. bitLimit)
if (v & (1 << (bitLimit - bitNum - 1)))
typeIdx++;
else
set ~= typeIdx;
return set;
}
}
// For finite Random Access Range.
auto combRep(R)(R types, in uint numChoice) /*pure*/ nothrow @safe
if (hasLength!R && isRandomAccessRange!R) {
ElementType!R[][] result;
foreach (const s; CombRep(types.length, numChoice)) {
ElementType!R[] r;
foreach (immutable i; s)
r ~= types[i];
result ~= r;
}
return result;
}
void main() @safe {
foreach (const e; combRep(["iced", "jam", "plain"], 2))
writefln("%-(%5s %)", e);
writeln("Ways to select 3 from 10 types is ",
CombRep(10, 3).length);
}
- Output:
iced iced iced jam iced plain jam jam jam plain plain plain Ways to select 3 from 10 types is 220
Short Recursive Version
import std.stdio, std.range, std.algorithm;
T[][] combsRep(T)(T[] lst, in int k) {
if (k == 0)
return [[]];
if (lst.empty)
return null;
return combsRep(lst, k - 1).map!(L => lst[0] ~ L).array
~ combsRep(lst[1 .. $], k);
}
void main() {
["iced", "jam", "plain"].combsRep(2).writeln;
10.iota.array.combsRep(3).length.writeln;
}
- Output:
[["iced", "iced"], ["iced", "jam"], ["iced", "plain"], ["jam", "jam"], ["jam", "plain"], ["plain", "plain"]] 220
EasyLang
items$[] = [ "iced" "jam" "plain" ]
n = len items$[]
k = 2
len result[] k
n_results = 0
#
proc output . .
n_results += 1
if len items$[] > 0
s$ = ""
for i = 1 to k
s$ &= items$[result[i]] & " "
.
print s$
.
.
proc combine pos val . .
if pos > k
output
else
for i = val to n
result[pos] = i
combine pos + 1 i
.
.
.
combine 1 1
#
n = 10
k = 3
len result[] k
items$[] = [ ]
n_results = 0
combine 1 1
print ""
print n_results & " results with 10 donuts"
- Output:
iced iced iced jam iced plain jam jam jam plain plain plain 220 results with 10 donuts
EchoLisp
We can use the native combinations/rep function, or use a combinator iterator, or implement the function.
;;
;; native function : combinations/rep in list.lib
;;
(lib 'list)
(combinations/rep '(iced jam plain) 2)
→ ((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))
;;
;; using a combinator iterator
;;
(lib 'sequences)
(take (combinator/rep '(iced jam plain) 2) 8)
→ ((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))
;;
;; or, implementing the function
;;
(define (comb/rep nums k)
(cond
[(null? nums) null]
[(<= k 0) null]
[(= k 1) (map list nums)]
[else
(for/fold (acc null) ((anum nums))
(append acc
(for/list ((xs (comb/rep nums (1- k))))
#:continue (< (first xs) anum)
(cons anum xs))))]))
(map (curry list-permute '(iced jam plain)) (comb/rep (iota 3) 2))
→ ((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))
;;
;; extra credit
;;
(length (combinator/rep (iota 10) 3))
→ 220
Egison
(define $comb/rep
(lambda [$n $xs]
(match-all xs (list something)
[(loop $i [1 ,n] <join _ (& <cons $a_i _> ...)> _) a])))
(test (comb/rep 2 {"iced" "jam" "plain"}))
- Output:
{[|"iced" "iced"|] [|"iced" "jam"|] [|"jam" "jam"|] [|"iced" "plain"|] [|"jam" "plain"|] [|"plain" "plain"|]}
Elixir
defmodule RC do
def comb_rep(0, _), do: [[]]
def comb_rep(_, []), do: []
def comb_rep(n, [h|t]=s) do
(for l <- comb_rep(n-1, s), do: [h|l]) ++ comb_rep(n, t)
end
end
s = [:iced, :jam, :plain]
Enum.each(RC.comb_rep(2, s), fn x -> IO.inspect x end)
IO.puts "\nExtra credit: #{length(RC.comb_rep(3, Enum.to_list(1..10)))}"
- Output:
[:iced, :iced] [:iced, :jam] [:iced, :plain] [:jam, :jam] [:jam, :plain] [:plain, :plain] Extra credit: 220
Erlang
-module(comb).
-compile(export_all).
comb_rep(0,_) ->
[[]];
comb_rep(_,[]) ->
[];
comb_rep(N,[H|T]=S) ->
[[H|L] || L <- comb_rep(N-1,S)]++comb_rep(N,T).
- Output:
94> comb:comb_rep(2,[iced,jam,plain]). [[iced,iced], [iced,jam], [iced,plain], [jam,jam], [jam,plain], [plain,plain]] 95> length(comb:comb_rep(3,lists:seq(1,10))). 220
Factor
See the implementation of all-combinations-with-replacement
here.
USING: math.combinatorics prettyprint qw ;
qw{ iced jam plain } 2 all-combinations-with-replacement .
- Output:
{ { "iced" "iced" } { "iced" "jam" } { "iced" "plain" } { "jam" "jam" } { "jam" "plain" } { "plain" "plain" } }
Fortran
program main
integer :: chosen(4)
integer :: ssize
character(len=50) :: donuts(4) = [ "iced", "jam", "plain", "something completely different" ]
ssize = choose( chosen, 2, 3 )
write(*,*) "Total = ", ssize
contains
recursive function choose( got, len, maxTypes, nChosen, at ) result ( output )
integer :: got(:)
integer :: len
integer :: maxTypes
integer :: output
integer, optional :: nChosen
integer, optional :: at
integer :: effNChosen
integer :: effAt
integer :: i
integer :: counter
effNChosen = 1
if( present(nChosen) ) effNChosen = nChosen
effAt = 1
if( present(at) ) effAt = at
if ( effNChosen == len+1 ) then
do i=1,len
write(*,"(A10,5X)", advance='no') donuts( got(i)+1 )
end do
write(*,*) ""
output = 1
return
end if
counter = 0
do i=effAt,maxTypes
got(effNChosen) = i-1
counter = counter + choose( got, len, maxTypes, effNChosen + 1, i )
end do
output = counter
return
end function choose
end program main
- Output:
iced iced iced jam iced plain jam jam jam plain plain plain Total = 6
FreeBASIC
sub iterate( byval curr as string, byval start as uinteger,_
byval stp as uinteger, byval depth as uinteger,_
names() as string )
dim as uinteger i
for i = start to stp
if depth = 0 then
print curr + " " + names(i)
else
iterate curr+" "+names(i), i, stp, depth-1, names()
end if
next i
return
end sub
dim as uinteger m, n, o, i
input "Enter n comb m. ", n, m
dim as string outstr = ""
dim as string names(0 to m-1)
for i = 0 to m - 1
print "Name for item ",+i
input names(i)
next i
iterate outstr, 0, m-1, n-1, names()
- Output:
Enter n comb m. 2,3 Name for item 0 ? Iced Name for item 1 ? Jam Name for item 2 ? Plain Iced Iced Iced Jam Iced Plain Jam Jam Jam Plain Plain Plain
GAP
# Built-in
UnorderedTuples(["iced", "jam", "plain"], 2);
Go
Concise recursive
package main
import "fmt"
func combrep(n int, lst []string) [][]string {
if n == 0 {
return [][]string{nil}
}
if len(lst) == 0 {
return nil
}
r := combrep(n, lst[1:])
for _, x := range combrep(n-1, lst) {
r = append(r, append(x, lst[0]))
}
return r
}
func main() {
fmt.Println(combrep(2, []string{"iced", "jam", "plain"}))
fmt.Println(len(combrep(3,
[]string{"1", "2", "3", "4", "5", "6", "7", "8", "9", "10"})))
}
- Output:
[[plain plain] [plain jam] [jam jam] [plain iced] [jam iced] [iced iced]] 220
Channel
Using channel and goroutine, showing how to use synced or unsynced communication.
package main
import "fmt"
func picks(picked []int, pos, need int, c chan[]int, do_wait bool) {
if need == 0 {
if do_wait {
c <- picked
<-c
} else { // if we want only the count, there's no need to
// sync between coroutines; let it clobber the array
c <- []int {}
}
return
}
if pos <= 0 {
if need == len(picked) { c <- nil }
return
}
picked[len(picked) - need] = pos - 1
picks(picked, pos, need - 1, c, do_wait) // choose the current donut
picks(picked, pos - 1, need, c, do_wait) // or don't
}
func main() {
donuts := []string {"iced", "jam", "plain" }
picked := make([]int, 2)
ch := make(chan []int)
// true: tell the channel to wait for each sending, because
// otherwise the picked array may get clobbered before we can do
// anything to it
go picks(picked, len(donuts), len(picked), ch, true)
var cc []int
for {
if cc = <-ch; cc == nil { break }
for _, i := range cc {
fmt.Printf("%s ", donuts[i])
}
fmt.Println()
ch <- nil // sync
}
picked = make([]int, 3)
// this time we only want the count, so tell goroutine to keep going
// and work the channel buffer
go picks(picked, 10, len(picked), ch, false)
count := 0
for {
if cc = <-ch; cc == nil { break }
count++
}
fmt.Printf("\npicking 3 of 10: %d\n", count)
}
- Output:
plain plain plain jam plain iced jam jam jam iced iced iced picking 3 of 10: 220
Multiset
This version has proper representation of sets and multisets.
package main
import (
"fmt"
"sort"
"strconv"
)
// Go maps are an easy representation for sets as long as the element type
// of the set is valid as a key type for maps. Strings are easy.
// We follow the convention of always storing true for the value.
type set map[string]bool
// Multisets of strings are easy in the same way.
// We store the multiplicity of the element as the value.
type multiset map[string]int
// But multisets are not valid as a map key type so we must do something
// more involved to make a set of multisets, which is the desired return
// type for the combrep function required by the task. We can store the
// multiset as the value, but we derive a unique string to use as a key.
type msSet map[string]multiset
// The key method returns this string. The string will simply be a text
// representation of the contents of the multiset. The standard
// printable representation of the multiset cannot be used however, because
// Go maps are not ordered. Instead, the contents are copied to a slice,
// which is sorted to produce something with a printable representation
// that will compare == for mathematically equal multisets.
//
// Of course there is overhead for this and if performance were important,
// a different representation would be used for multisets, one that didn’t
// require sorting to produce a key...
func (m multiset) key() string {
pl := make(pairList, len(m))
i := 0
for k, v := range m {
pl[i] = msPair{k, v}
i++
}
sort.Sort(pl)
return fmt.Sprintf("%v", pl)
}
// Types and methods needed for sorting inside of mulitset.key()
type msPair struct {
string
int
}
type pairList []msPair
func (p pairList) Len() int { return len(p) }
func (p pairList) Swap(i, j int) { p[i], p[j] = p[j], p[i] }
func (p pairList) Less(i, j int) bool { return p[i].string < p[j].string }
// Function required by task.
func combrep(n int, lst set) msSet {
if n == 0 {
var ms multiset
return msSet{ms.key(): ms}
}
if len(lst) == 0 {
return msSet{}
}
var car string
var cdr set
for ele := range lst {
if cdr == nil {
car = ele
cdr = make(set)
} else {
cdr[ele] = true
}
}
r := combrep(n, cdr)
for _, x := range combrep(n-1, lst) {
c := multiset{car: 1}
for k, v := range x {
c[k] += v
}
r[c.key()] = c
}
return r
}
// Driver for examples required by task.
func main() {
// Input is a set.
three := set{"iced": true, "jam": true, "plain": true}
// Output is a set of multisets. The set is a Go map:
// The key is a string representation that compares equal
// for equal multisets. We ignore this here. The value
// is the multiset. We print this.
for _, ms := range combrep(2, three) {
fmt.Println(ms)
}
ten := make(set)
for i := 1; i <= 10; i++ {
ten[strconv.Itoa(i)] = true
}
fmt.Println(len(combrep(3, ten)))
}
- Output:
map[plain:1 jam:1] map[plain:2] map[iced:1 jam:1] map[jam:2] map[iced:1 plain:1] map[iced:2] 220
Haskell
-- Return the combinations, with replacement, of k items from the
-- list. We ignore the case where k is greater than the length of
-- the list.
combsWithRep :: Int -> [a] -> [[a]]
combsWithRep 0 _ = [[]]
combsWithRep _ [] = []
combsWithRep k xxs@(x:xs) =
(x :) <$> combsWithRep (k - 1) xxs ++ combsWithRep k xs
binomial n m = f n `div` f (n - m) `div` f m
where
f n =
if n == 0
then 1
else n * f (n - 1)
countCombsWithRep :: Int -> [a] -> Int
countCombsWithRep k lst = binomial (k - 1 + length lst) k
-- countCombsWithRep k = length . combsWithRep k
main :: IO ()
main = do
print $ combsWithRep 2 ["iced", "jam", "plain"]
print $ countCombsWithRep 3 [1 .. 10]
- Output:
[["iced","iced"],["iced","jam"],["iced","plain"],["jam","jam"],["jam","plain"],["plain","plain"]] 220
Dynamic Programming
The first solution is inefficient because it repeatedly calculates the same subproblem in different branches of recursion. For example, combsWithRep k (x:xs)
involves computing combsWithRep (k-1) (x:xs)
and combsWithRep k xs
, both of which (separately) compute combsWithRep (k-1) xs
. To avoid repeated computation, we can use dynamic programming:
combsWithRep :: Int -> [a] -> [[a]]
combsWithRep k xs = combsBySize xs !! k
where
combsBySize = foldr f ([[]] : repeat [])
f x = scanl1 $ (++) . map (x :)
main :: IO ()
main = print $ combsWithRep 2 ["iced", "jam", "plain"]
and another approach, using manual recursion:
--------------- COMBINATIONS WITH REPETITION -------------
combinationsWithRepetition ::
(Eq a) =>
Int ->
[a] ->
[[a]]
combinationsWithRepetition k xs = cmb k []
where
cmb 0 ys = ys
cmb n [] = cmb (pred n) (pure <$> xs)
cmb n peers = cmb (pred n) (peers >>= nextLayer)
where
nextLayer [] = []
nextLayer ys@(h : _) =
(: ys) <$> dropWhile (/= h) xs
-------------------------- TESTS -------------------------
main :: IO ()
main = do
print $
combinationsWithRepetition
2
["iced", "jam", "plain"]
print $ length $ combinationsWithRepetition 3 [0 .. 9]
- Output:
[["iced","iced"],["jam","iced"],["plain","iced"],["jam","jam"],["plain","jam"],["plain","plain"]] 220
Icon and Unicon
Following procedure is a generator, which generates each combination of length n in turn:
Test procedure:
- Output:
plain plain jam plain jam jam iced plain iced jam iced iced There are 220 possible combinations of 3 from 10
J
Cartesian product, the monadic j verb { solves the problem. The rest of the code handles the various data types, order, and quantity to choose, and makes a set from the result.
rcomb=: >@~.@:(/:~&.>)@,@{@# <
Example use:
2 rcomb ;:'iced jam plain'
┌─────┬─────┐
│iced │iced │
├─────┼─────┤
│iced │jam │
├─────┼─────┤
│iced │plain│
├─────┼─────┤
│jam │jam │
├─────┼─────┤
│jam │plain│
├─────┼─────┤
│plain│plain│
└─────┴─────┘
#3 rcomb i.10 NB. # ways to choose 3 items from 10 with repetitions
220
J Alternate implementation
Considerably faster:
require 'stats'
rcomb=: (combrep #) { ]
This definition of rcomb
behaves identically to the previous one, and combrep
calculates indices:
2 combrep 3
0 0
0 1
0 2
1 1
1 2
2 2
combrep
computes 2 comb 4
(note that 4 = (2 + 3)-1) and then subtracts from each column the minimum value in each column (i. 2
).
Java
MultiCombinationsTester.java
import com.objectwave.utility.*;
public class MultiCombinationsTester {
public MultiCombinationsTester() throws CombinatoricException {
Object[] objects = {"iced", "jam", "plain"};
//Object[] objects = {"abba", "baba", "ab"};
//Object[] objects = {"aaa", "aa", "a"};
//Object[] objects = {(Integer)1, (Integer)2, (Integer)3, (Integer)4};
MultiCombinations mc = new MultiCombinations(objects, 2);
while (mc.hasMoreElements()) {
for (int i = 0; i < mc.nextElement().length; i++) {
System.out.print(mc.nextElement()[i].toString() + " ");
}
System.out.println();
}
// Extra credit:
System.out.println("----------");
System.out.println("The ways to choose 3 items from 10 with replacement = " + MultiCombinations.c(10, 3));
} // constructor
public static void main(String[] args) throws CombinatoricException {
new MultiCombinationsTester();
}
} // class
MultiCombinations.java
import com.objectwave.utility.*;
import java.util.*;
public class MultiCombinations {
private HashSet<String> set = new HashSet<String>();
private Combinations comb = null;
private Object[] nextElem = null;
public MultiCombinations(Object[] objects, int k) throws CombinatoricException {
k = Math.max(0, k);
Object[] myObjects = new Object[objects.length * k];
for (int i = 0; i < objects.length; i++) {
for (int j = 0; j < k; j++) {
myObjects[i * k + j] = objects[i];
}
}
comb = new Combinations(myObjects, k);
} // constructor
boolean hasMoreElements() {
boolean ret = false;
nextElem = null;
int oldCount = set.size();
while (comb.hasMoreElements()) {
Object[] elem = (Object[]) comb.nextElement();
String str = "";
for (int i = 0; i < elem.length; i++) {
str += ("%" + elem[i].toString() + "~");
}
set.add(str);
if (set.size() > oldCount) {
nextElem = elem;
ret = true;
break;
}
}
return ret;
} // hasMoreElements()
Object[] nextElement() {
return nextElem;
}
static java.math.BigInteger c(int n, int k) throws CombinatoricException {
return Combinatoric.c(n + k - 1, k);
}
} // class
- Output:
iced iced iced jam iced plain jam jam jam plain plain plain ---------- The ways to choose 3 items from 10 with replacement = 220
JavaScript
ES5
Imperative
<html><head><title>Donuts</title></head>
<body><pre id='x'></pre><script type="application/javascript">
function disp(x) {
var e = document.createTextNode(x + '\n');
document.getElementById('x').appendChild(e);
}
function pick(n, got, pos, from, show) {
var cnt = 0;
if (got.length == n) {
if (show) disp(got.join(' '));
return 1;
}
for (var i = pos; i < from.length; i++) {
got.push(from[i]);
cnt += pick(n, got, i, from, show);
got.pop();
}
return cnt;
}
disp(pick(2, [], 0, ["iced", "jam", "plain"], true) + " combos");
disp("pick 3 out of 10: " + pick(3, [], 0, "a123456789".split(''), false) + " combos");
</script></body></html>
- Output:
iced iced iced jam iced plain jam jam jam plain plain plain 6 combos pick 3 out of 10: 220 combos
Functional
(function () {
// n -> [a] -> [[a]]
function combsWithRep(n, lst) {
return n ? (
lst.length ? combsWithRep(n - 1, lst).map(function (t) {
return [lst[0]].concat(t);
}).concat(combsWithRep(n, lst.slice(1))) : []
) : [[]];
};
// If needed, we can derive a significantly faster version of
// the simple recursive function above by memoizing it
// f -> f
function memoized(fn) {
m = {};
return function (x) {
var args = [].slice.call(arguments),
strKey = args.join('-');
v = m[strKey];
if ('u' === (typeof v)[0])
m[strKey] = v = fn.apply(null, args);
return v;
}
}
// [m..n]
function range(m, n) {
return Array.apply(null, Array(n - m + 1)).map(function (x, i) {
return m + i;
});
}
return [
combsWithRep(2, ["iced", "jam", "plain"]),
// obtaining and applying a memoized version of the function
memoized(combsWithRep)(3, range(1, 10)).length
];
})();
- Output:
[
[["iced", "iced"], ["iced", "jam"], ["iced", "plain"],
["jam", "jam"], ["jam", "plain"], ["plain", "plain"]],
220
]
ES6
(() => {
'use strict';
// COMBINATIONS WITH REPETITIONS -------------------------------------------
// combsWithRep :: Int -> [a] -> [[a]]
const combsWithRep = (k, xs) => {
const comb = (n, ys) => {
if (0 === n) return ys;
if (isNull(ys)) return comb(n - 1, map(pure, xs));
return comb(n - 1, concatMap(zs => {
const h = head(zs);
return map(x => [x].concat(zs), dropWhile(x => x !== h, xs));
}, ys));
};
return comb(k, []);
};
// GENERIC FUNCTIONS ------------------------------------------------------
// concatMap :: (a -> [b]) -> [a] -> [b]
const concatMap = (f, xs) => [].concat.apply([], xs.map(f));
// dropWhile :: (a -> Bool) -> [a] -> [a]
const dropWhile = (p, xs) => {
let i = 0;
for (let lng = xs.length;
(i < lng) && p(xs[i]); i++) {}
return xs.slice(i);
};
// enumFromTo :: Int -> Int -> [Int]
const enumFromTo = (m, n) =>
Array.from({
length: Math.floor(n - m) + 1
}, (_, i) => m + i);
// head :: [a] -> Maybe a
const head = xs => xs.length ? xs[0] : undefined;
// isNull :: [a] -> Bool
const isNull = xs => (xs instanceof Array) ? xs.length < 1 : undefined;
// length :: [a] -> Int
const length = xs => xs.length;
// map :: (a -> b) -> [a] -> [b]
const map = (f, xs) => xs.map(f);
// pure :: a -> [a]
const pure = x => [x];
// show :: a -> String
const show = x => JSON.stringify(x, null, 2);
// TEST -------------------------------------------------------------------
return show({
twoFromThree: combsWithRep(2, ['iced', 'jam', 'plain']),
threeFromTen: length(combsWithRep(3, enumFromTo(0, 9)))
});
})();
- Output:
{ "twoFromThree": [ [ "iced", "iced" ], [ "jam", "iced" ], [ "plain", "iced" ], [ "jam", "jam" ], [ "plain", "jam" ], [ "plain", "plain" ] ], "threeFromTen": 220 }
jq
def pick(n):
def pick(n; m): # pick n, from m onwards
if n == 0 then []
elif m == length then empty
elif n == 1 then (.[m:][] | [.])
else ([.[m]] + pick(n-1; m)), pick(n; m+1)
end;
pick(n;0) ;
The task:
"Pick 2:",
(["iced", "jam", "plain"] | pick(2)),
([[range(0;10)] | pick(3)] | length) as $n
| "There are \($n) ways to pick 3 objects with replacement from 10."
- Output:
$ jq -n -r -c -f pick.jq Pick 2: ["iced","iced"] ["iced","jam"] ["iced","plain"] ["jam","jam"] ["jam","plain"] ["plain","plain"] There are 220 ways to pick 3 objects with replacement from 10.
Julia
using Combinatorics
l = ["iced", "jam", "plain"]
println("List: ", l, "\nCombinations:")
for c in with_replacement_combinations(l, 2)
println(c)
end
@show length(with_replacement_combinations(1:10, 3))
- Output:
List: String["iced", "jam", "plain"] Combinations: String["iced", "iced"] String["iced", "jam"] String["iced", "plain"] String["jam", "jam"] String["jam", "plain"] String["plain", "plain"] length(with_replacement_combinations(1:10, 3)) = 220
Kotlin
// version 1.0.6
class CombsWithReps<T>(val m: Int, val n: Int, val items: List<T>, val countOnly: Boolean = false) {
private val combination = IntArray(m)
private var count = 0
init {
generate(0)
if (!countOnly) println()
println("There are $count combinations of $n things taken $m at a time, with repetitions")
}
private fun generate(k: Int) {
if (k >= m) {
if (!countOnly) {
for (i in 0 until m) print("${items[combination[i]]}\t")
println()
}
count++
}
else {
for (j in 0 until n)
if (k == 0 || j >= combination[k - 1]) {
combination[k] = j
generate(k + 1)
}
}
}
}
fun main(args: Array<String>) {
val doughnuts = listOf("iced", "jam", "plain")
CombsWithReps(2, 3, doughnuts)
println()
val generic10 = "0123456789".chunked(1)
CombsWithReps(3, 10, generic10, true)
}
- Output:
iced iced iced jam iced plain jam jam jam plain plain plain There are 6 combinations of 3 things taken 2 at a time, with repetitions There are 220 combinations of 10 things taken 3 at a time, with repetitions
LFE
and
With List Comprehension
(defun combinations
(('() _)
'())
((coll 1)
(lists:map #'list/1 coll))
(((= (cons head tail) coll) n)
(++ (lc ((<- subcoll (combinations coll (- n 1))))
(cons head subcoll))
(combinations tail n))))
With Map
(defun combinations
(('() _)
'())
((coll 1)
(lists:map #'list/1 coll))
(((= (cons head tail) coll) n)
(++ (lists:map (lambda (subcoll) (cons head subcoll))
(combinations coll (- n 1)))
(combinations tail n))))
Output is the same for both:
> (combinations '(iced jam plain) 2)
((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))
Lobster
import std
// set S of length n, choose k
def choose(s, k, f):
let got = map(k): s[0]
let n = s.length
def choosi(n_chosen, at):
var count = 0
if n_chosen == k:
f(got)
return 1
var i = at
while i < n:
got[n_chosen] = s[i]
count += choosi(n_chosen + 1, i)
i += 1
return count
return choosi(0, 0)
let count = choose(["iced", "jam", "plain"], 2): print(_)
print count
let extra = choose(map(10):_, 3): _
print extra
- Output:
["iced", "iced"] ["iced", "jam"] ["iced", "plain"] ["jam", "jam"] ["jam", "plain"] ["plain", "plain"] 6 220
Lua
function GenerateCombinations(tList, nMaxElements, tOutput, nStartIndex, nChosen, tCurrentCombination)
if not nStartIndex then
nStartIndex = 1
end
if not nChosen then
nChosen = 0
end
if not tOutput then
tOutput = {}
end
if not tCurrentCombination then
tCurrentCombination = {}
end
if nChosen == nMaxElements then
-- Must copy the table to avoid all elements referring to a single reference
local tCombination = {}
for k,v in pairs(tCurrentCombination) do
tCombination[k] = v
end
table.insert(tOutput, tCombination)
return
end
local nIndex = 1
for k,v in pairs(tList) do
if nIndex >= nStartIndex then
tCurrentCombination[nChosen + 1] = tList[nIndex]
GenerateCombinations(tList, nMaxElements, tOutput, nIndex, nChosen + 1, tCurrentCombination)
end
nIndex = nIndex + 1
end
return tOutput
end
tDonuts = {"iced", "jam", "plain"}
tCombinations = GenerateCombinations(tDonuts, #tDonuts)
for nCombination,tCombination in ipairs(tCombinations) do
print("Combination " .. tostring(nCombination))
for nIndex,strFlavor in ipairs(tCombination) do
print("+" .. strFlavor)
end
end
Maple
with(combinat):
chooserep:=(s,k)->choose([seq(op(s),i=1..k)],k):
chooserep({iced,jam,plain},2);
# [[iced, iced], [iced, jam], [iced, plain], [jam, jam], [jam, plain], [plain, plain]]
numbchooserep:=(s,k)->binomial(nops(s)+k-1,k);
numbchooserep({iced,jam,plain},2);
# 6
Mathematica / Wolfram Language
This method will only work for small set and sample sizes (as it generates all Tuples then filters duplicates - Length[Tuples[Range[10],10]] is already bigger than Mathematica can handle).
DeleteDuplicates[Tuples[{"iced", "jam", "plain"}, 2],Sort[#1] == Sort[#2] &]
->{{"iced", "iced"}, {"iced", "jam"}, {"iced", "plain"}, {"jam", "jam"}, {"jam", "plain"}, {"plain", "plain"}}
Combi[x_, y_] := Binomial[(x + y) - 1, y]
Combi[3, 2]
-> 6
Combi[10, 3]
->220
A better method therefore:
CombinWithRep[S_List, k_] := Module[{occupation, assignment},
occupation =
Flatten[Permutations /@
IntegerPartitions[k, {Length[S]}, Range[0, k]], 1];
assignment =
Flatten[Table[ConstantArray[z, {#[[z]]}], {z, Length[#]}]] & /@
occupation;
Thread[S[[#]]] & /@ assignment
]
In[2]:= CombinWithRep[{"iced", "jam", "plain"}, 2]
Out[2]= {{"iced", "iced"}, {"jam", "jam"}, {"plain",
"plain"}, {"iced", "jam"}, {"iced", "plain"}, {"jam", "plain"}}
Which can handle the Length[S] = 10, k=10 situation in still only seconds.
Mercury
comb.choose uses a nondeterministic list.member/2 to pick values from the list, and just puts them into a bag (a multiset). comb.choose_all gathers all of the possible bags that comb.choose would produce for a given list and number of picked values, and turns them into lists (for readability).
comb.count_choices shows off solutions.aggregate (which allows you to fold over solutions as they're found) rather than list.length and the factorial function.
:- module comb.
:- interface.
:- import_module list, int, bag.
:- pred choose(list(T)::in, int::in, bag(T)::out) is nondet.
:- pred choose_all(list(T)::in, int::in, list(list(T))::out) is det.
:- pred count_choices(list(T)::in, int::in, int::out) is det.
:- implementation.
:- import_module solutions.
choose(L, N, R) :- choose(L, N, bag.init, R).
:- pred choose(list(T)::in, int::in, bag(T)::in, bag(T)::out) is nondet.
choose(L, N, !R) :-
( N = 0 ->
true
;
member(X, L),
bag.insert(!.R, X, !:R),
choose(L, N - 1, !R)
).
choose_all(L, N, R) :-
solutions(choose(L, N), R0),
list.map(bag.to_list, R0, R).
count_choices(L, N, Count) :-
aggregate(choose(L, N), count, 0, Count).
:- pred count(T::in, int::in, int::out) is det.
count(_, N0, N) :- N0 + 1 = N.
Usage:
:- module comb_ex.
:- interface.
:- import_module io.
:- pred main(io::di, io::uo) is det.
:- implementation.
:- import_module comb, list, string.
:- type doughtnuts
---> iced ; jam ; plain
; glazed ; chocolate ; cream_filled ; mystery
; cubed ; cream_covered ; explosive.
main(!IO) :-
choose_all([iced, jam, plain], 2, L),
count_choices([iced, jam, plain, glazed, chocolate, cream_filled,
mystery, cubed, cream_covered, explosive], 3, N),
io.write(L, !IO), io.nl(!IO),
io.write_string(from_int(N) ++ " choices.\n", !IO).
- Output:
[[iced, iced], [jam, jam], [plain, plain], [iced, jam], [iced, plain], [jam, plain]] 220 choices.
Nim
import sugar, sequtils
proc combsReps[T](lst: seq[T], k: int): seq[seq[T]] =
if k == 0:
@[newSeq[T]()]
elif lst.len == 0:
@[]
else:
lst.combsReps(k - 1).map((x: seq[T]) => lst[0] & x) &
lst[1 .. ^1].combsReps(k)
echo(@["iced", "jam", "plain"].combsReps(2))
echo toSeq(1..10).combsReps(3).len
- Output:
@[@[iced, iced], @[iced, jam], @[iced, plain], @[jam, jam], @[jam, plain], @[plain, plain]] 220
OCaml
let rec combs_with_rep k xxs =
match k, xxs with
| 0, _ -> [[]]
| _, [] -> []
| k, x::xs ->
List.map (fun ys -> x::ys) (combs_with_rep (k-1) xxs)
@ combs_with_rep k xs
in the interactive loop:
# combs_with_rep 2 ["iced"; "jam"; "plain"] ;; - : string list list = [["iced"; "iced"]; ["iced"; "jam"]; ["iced"; "plain"]; ["jam"; "jam"]; ["jam"; "plain"]; ["plain"; "plain"]] # List.length (combs_with_rep 3 [1;2;3;4;5;6;7;8;9;10]) ;; - : int = 220
Dynamic programming
let combs_with_rep m xs =
let arr = Array.make (m+1) [] in
arr.(0) <- [[]];
List.iter (fun x ->
for i = 1 to m do
arr.(i) <- arr.(i) @ List.map (fun xs -> x::xs) arr.(i-1)
done
) xs;
arr.(m)
in the interactive loop:
# combs_with_rep 2 ["iced"; "jam"; "plain"] ;; - : string list list = [["iced"; "iced"]; ["jam"; "iced"]; ["jam"; "jam"]; ["plain"; "iced"]; ["plain"; "jam"]; ["plain"; "plain"]] # List.length (combs_with_rep 3 [1;2;3;4;5;6;7;8;9;10]) ;; - : int = 220
PARI/GP
ways(k,v,s=[])={
if(k==0,return([]));
if(k==1,return(vector(#v,i,concat(s,[v[i]]))));
if(#v==1,return(ways(k-1,v,concat(s,v))));
my(u=vecextract(v,2^#v-2));
concat(ways(k-1,v,concat(s,[v[1]])),ways(k,u,s))
};
xc(k,v)=binomial(#v+k-1,k);
ways(2, ["iced","jam","plain"])
Pascal
used in Munchausen_numbers or Own_digits_power_sum
program CombWithRep;
//combinations with repetitions
//Limit = count of elements
//Maxval = value of top , lowest is always 0
//so 0..Maxvalue => maxValue+1 elements
{$IFDEF FPC}
// {$R+,O+}
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$COPERATORS ON}
{$ELSE}{$APPTYPE CONSOLE}{$ENDIF}
uses
SysUtils;//GetTickCount64
var
CombIdx: array of byte;
function InitCombIdx(ElemCount: Int32): pbyte;
begin
setlength(CombIdx, ElemCount + 1);
Fillchar(CombIdx[0], sizeOf(CombIdx[0]) * (ElemCount + 1), #0);
Result := @CombIdx[0];
end;
function NextCombWithRep(pComb: pByte; MaxVal, ElemCount: UInt32): boolean;
var
i, dgt: NativeInt;
begin
i := -1;
repeat
i += 1;
dgt := pComb[i];
if dgt < MaxVal then
break;
until i > ElemCount;
Result := i >= ElemCount;
dgt +=1;
repeat
pComb[i] := dgt;
i -= 1;
until i < 0;
end;
procedure GetDoughnuts(ElemCount: NativeInt);
const
doughnuts: array[0..2] of string = ('iced', 'jam', 'plain');
var
pComb: pByte;
MaxVal, i: Uint32;
begin
if ElemCount < 1 then
EXIT;
MaxVal := High(doughnuts);
writeln('Getting ', ElemCount, ' elements of ', MaxVal + 1, ' different');
pComb := InitCombIdx(ElemCount);
repeat
Write('[');
for i := 0 to ElemCount - 2 do
Write(pComb[i], ',');
Write(pComb[ElemCount - 1], ']');
Write('{');
for i := 0 to ElemCount - 2 do
Write(doughnuts[pComb[i]], ',');
Write(doughnuts[pComb[ElemCount - 1]], '}');
until NextCombWithRep(pComb, MaxVal, ElemCount);
writeln(#10);
end;
procedure Check(ElemCount: Int32; ElemRange: Uint32);
var
pComb: pByte;
T0: int64;
rec_cnt: NativeInt;
begin
T0 := GetTickCount64;
rec_cnt := 0;
ElemRange -= 1;
pComb := InitCombIdx(ElemCount);
repeat
Inc(rec_cnt);
until NextCombWithRep(pComb, ElemRange, ElemCount);
T0 := GetTickCount64 - T0;
writeln('Getting ', ElemCount, ' elements of ', ElemRange + 1, ' different');
writeln(rec_cnt: 10, t0: 10,' ms');
end;
begin
GetDoughnuts(2);
GetDoughnuts(3);
Check(3, 10);
Check(9, 10);
Check(15, 16);
{$IFDEF WINDOWS}
readln;
{$ENDIF}
end.
- Output:
TIO.RUN Getting 2 elements of 3 different [0,0]{iced,iced}[1,0]{jam,iced}[2,0]{plain,iced}[1,1]{jam,jam}[2,1]{plain,jam}[2,2]{plain,plain} Getting 3 elements of 3 different [0,0,0]{iced,iced,iced}[1,0,0]{jam,iced,iced}[2,0,0]{plain,iced,iced}[1,1,0]{jam,jam,iced}[2,1,0]{plain,jam,iced}[2,2,0]{plain,plain,iced}[1,1,1]{jam,jam,jam}[2,1,1]{plain,jam,jam}[2,2,1]{plain,plain,jam}[2,2,2]{plain,plain,plain} Getting 3 elements of 10 different 220 0 ms Getting 9 elements of 10 different 48620 0 ms Getting 15 elements of 16 different 155117520 735 ms
Perl
The highly readable version:
sub p { $_[0] ? map p($_[0] - 1, [@{$_[1]}, $_[$_]], @_[$_ .. $#_]), 2 .. $#_ : $_[1] }
sub f { $_[0] ? $_[0] * f($_[0] - 1) : 1 }
sub pn{ f($_[0] + $_[1] - 1) / f($_[0]) / f($_[1] - 1) }
for (p(2, [], qw(iced jam plain))) {
print "@$_\n";
}
printf "\nThere are %d ways to pick 7 out of 10\n", pn(7,10);
Prints:
iced iced iced jam iced plain jam jam jam plain plain plain There are 11440 ways to pick 7 out of 10
With a module:
use Algorithm::Combinatorics qw/combinations_with_repetition/;
my $iter = combinations_with_repetition([qw/iced jam plain/], 2);
while (my $p = $iter->next) {
print "@$p\n";
}
# Not an efficient way: generates them all in an array!
my $count =()= combinations_with_repetition([1..10],7);
print "There are $count ways to pick 7 out of 10\n";
Phix
with javascript_semantics procedure show_choices(sequence set, integer n, at=1, sequence res={}) if length(res)=n then ?res else for i=at to length(set) do show_choices(set,n,i,append(deep_copy(res),set[i])) end for end if end procedure show_choices({"iced","jam","plain"},2)
- Output:
{"iced","iced"} {"iced","jam"} {"iced","plain"} {"jam","jam"} {"jam","plain"} {"plain","plain"}
The second part suggests enough differences (collecting and showing vs only counting) to strike me as ugly and confusing. While I could easily, say, translate the C version, I'd rather forego the extra credit and use a completely different routine:
with javascript_semantics function count_choices(integer set_size, n, at=1, taken=0) integer count = 0 if taken=n then return 1 end if taken += 1 for i=at to set_size do count += count_choices(set_size,n,i,taken) end for return count end function ?count_choices(10,3)
- Output:
220
As of 1.0.2 there is a builtin combinations_with_repetitions() function. Using a string here for simplicity and neater output, but it works with any sequence:
?join(combinations_with_repetitions("ijp",2),',') ?length(combinations_with_repetitions(tagset(10),3))
- Output:
"ii,ij,ip,jj,jp,pp" 220
PHP
<?php
function combos($arr, $k) {
if ($k == 0) {
return array(array());
}
if (count($arr) == 0) {
return array();
}
$head = $arr[0];
$combos = array();
$subcombos = combos($arr, $k-1);
foreach ($subcombos as $subcombo) {
array_unshift($subcombo, $head);
$combos[] = $subcombo;
}
array_shift($arr);
$combos = array_merge($combos, combos($arr, $k));
return $combos;
}
$arr = array("iced", "jam", "plain");
$result = combos($arr, 2);
foreach($result as $combo) {
echo implode(' ', $combo), "<br>";
}
$donuts = range(1, 10);
$num_donut_combos = count(combos($donuts, 3));
echo "$num_donut_combos ways to order 3 donuts given 10 types";
?>
- Output:
in the browser
iced iced iced jam iced plain jam jam jam plain plain plain 220 ways to order 3 donuts given 10 types
Non-recursive algorithm to generate all combinations with repetitons. Taken from here: [1]
You must set k n variables and fill arrays b and c.
<?php
//Author Ivan Gavryushin @dcc0
$k=3;
$n=5;
//set amount of elements as in $n var
$c=array(1,2,3,4,5);
//set amount of 1 as in $k var
$b=array(1,1,1);
$j=$k-1;
//Вывод
function printt($b,$k) {
$z=0;
while ($z < $k) print $b[$z++].' ';
print '<br>';
}
printt ($b,$k);
while (1) {
//Увеличение на позиции K до N
if (array_search($b[$j]+1,$c)!==false ) {
$b[$j]=$b[$j]+1;
printt ($b,$k);
}
if ($b[$k-1]==$n) {
$i=$k-1;
//Просмотр массива справа налево
while ($i >= 0) {
//Условие выхода
if ( $i == 0 && $b[$i] == $n) break 2;
//Поиск элемента для увеличения
$m=array_search($b[$i]+1,$c);
if ($m!==false) {
$c[$m]=$c[$m]-1;
$b[$i]=$b[$i]+1;
$g=$i;
//Сортировка массива B
while ($g != $k-1) {
array_unshift ($c, $b[$g+1]);
$b[$g+1]=$b[$i];
$g++;
}
//Удаление повторяющихся значений из C
$c=array_diff($c,$b);
printt ($b,$k);
array_unshift ($c, $n);
break;
}
$i--;
}
}
}
?>
PicoLisp
(de combrep (N Lst)
(cond
((=0 N) '(NIL))
((not Lst))
(T
(conc
(mapcar
'((X) (cons (car Lst) X))
(combrep (dec N) Lst) )
(combrep N (cdr Lst)) ) ) ) )
- Output:
: (combrep 2 '(iced jam plain)) -> ((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain)) : (length (combrep 3 (range 1 10))) -> 220
Prolog
combinations_of_length(_,[]).
combinations_of_length([X|T],[X|Combinations]):-
combinations_of_length([X|T],Combinations).
combinations_of_length([_|T],[X|Combinations]):-
combinations_of_length(T,[X|Combinations]).
?- [user]. |: combinations_of_length(_,[]). |: combinations_of_length([X|T],[X|Combinations]):- |: combinations_of_length([X|T],Combinations). |: combinations_of_length([_|T],[X|Combinations]):- |: combinations_of_length(T,[X|Combinations]). |: ^D% user://1 compiled 0.01 sec, 3 clauses true. ?- combinations_of_length([0,1,2,4],[L0, L1, L2, L3, L4, L5]). L0 = L1, L1 = L2, L2 = L3, L3 = L4, L4 = L5, L5 = 0 ; L0 = L1, L1 = L2, L2 = L3, L3 = L4, L4 = 0, L5 = 1 ; L0 = L1, L1 = L2, L2 = L3, L3 = L4, L4 = 0, L5 = 2 ; L0 = L1, L1 = L2, L2 = L3, L3 = L4, L4 = 0, L5 = 4 ; L0 = L1, L1 = L2, L2 = L3, L3 = 0, L4 = L5, L5 = 1 ; L0 = L1, L1 = L2, L2 = L3, L3 = 0, L4 = 1, L5 = 2 ; L0 = L1, L1 = L2, L2 = L3, L3 = 0, L4 = 1, L5 = 4 ; L0 = L1, L1 = L2, L2 = L3, L3 = 0, L4 = L5, L5 = 2 ; L0 = L1, L1 = L2, L2 = L3, L3 = 0, L4 = 2, . . .
PureBasic
Procedure nextCombination(Array combIndex(1), elementCount)
;combIndex() must be dimensioned to 'k' - 1, elementCount equals 'n' - 1
;combination produced includes repetition of elements and is represented by the array combIndex()
Protected i, indexValue, combSize = ArraySize(combIndex()), curIndex
;update indexes
curIndex = combSize
Repeat
combIndex(curIndex) + 1
If combIndex(curIndex) > elementCount
curIndex - 1
If curIndex < 0
For i = 0 To combSize
combIndex(i) = 0
Next
ProcedureReturn #False ;array reset to first combination
EndIf
ElseIf curIndex < combSize
indexValue = combIndex(curIndex)
Repeat
curIndex + 1
combIndex(curIndex) = indexValue
Until curIndex = combSize
EndIf
Until curIndex = combSize
ProcedureReturn #True ;array contains next combination
EndProcedure
Procedure.s display(Array combIndex(1), Array dougnut.s(1))
Protected i, elementCount = ArraySize(combIndex()), output.s = " "
For i = 0 To elementCount
output + dougnut(combIndex(i)) + " + "
Next
ProcedureReturn Left(output, Len(output) - 3)
EndProcedure
DataSection
Data.s "iced", "jam", "plain"
EndDataSection
If OpenConsole()
Define n = 3, k = 2, i, combinationCount
Dim combIndex(k - 1)
Dim dougnut.s(n - 1)
For i = 0 To n - 1: Read.s dougnut(i): Next
PrintN("Combinations of " + Str(n) + " dougnut types taken " + Str(k) + " at a time with repetitions.")
combinationCount = 0
Repeat
PrintN(display(combIndex(), dougnut()))
combinationCount + 1
Until Not nextCombination(combIndex(), n - 1)
PrintN("Total combination count: " + Str(combinationCount))
;extra credit
n = 10: k = 3
Dim combIndex(k - 1)
combinationCount = 0
Repeat: combinationCount + 1: Until Not nextCombination(combIndex(), n - 1)
PrintN(#CRLF$ + "Ways to select " + Str(k) + " items from " + Str(n) + " types: " + Str(combinationCount))
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()
EndIf
The nextCombination() procedure operates on an array of indexes to produce the next combination. This generalization allows producing a combination from any collection of elements. nextCombination() returns the value #False when the indexes have reach their maximum values and are then reset.
- Output:
Combinations of 3 dougnut types taken 2 at a time with repetitions. iced + iced iced + jam iced + plain jam + jam jam + plain plain + plain Total combination count: 6 Ways to select 3 items from 10 types: 220
Python
>>> from itertools import combinations_with_replacement
>>> n, k = 'iced jam plain'.split(), 2
>>> list(combinations_with_replacement(n,k))
[('iced', 'iced'), ('iced', 'jam'), ('iced', 'plain'), ('jam', 'jam'), ('jam', 'plain'), ('plain', 'plain')]
>>> # Extra credit
>>> len(list(combinations_with_replacement(range(10), 3)))
220
>>>
References:
Or, assembling our own combsWithRep, by composition of functional primitives:
'''Combinations with repetitions'''
from itertools import (accumulate, chain, islice, repeat)
from functools import (reduce)
# combsWithRep :: Int -> [a] -> [kTuple a]
def combsWithRep(k):
'''A list of tuples, representing
sets of cardinality k,
with elements drawn from xs.
'''
def f(a, x):
def go(ys, xs):
return xs + [[x] + y for y in ys]
return accumulate(a, go)
def combsBySize(xs):
return reduce(
f, xs, chain(
[[[]]],
islice(repeat([]), k)
)
)
return lambda xs: [
tuple(x) for x in next(islice(
combsBySize(xs), k, None
))
]
# TEST ----------------------------------------------------
def main():
'''Test the generation of sets of cardinality
k with elements drawn from xs.
'''
print(
combsWithRep(2)(['iced', 'jam', 'plain'])
)
print(
len(combsWithRep(3)(enumFromTo(0)(9)))
)
# GENERIC -------------------------------------------------
# enumFromTo :: (Int, Int) -> [Int]
def enumFromTo(m):
'''Integer enumeration from m to n.'''
return lambda n: list(range(m, 1 + n))
# showLog :: a -> IO String
def showLog(*s):
'''Arguments printed with
intercalated arrows.'''
print(
' -> '.join(map(str, s))
)
# MAIN ---
if __name__ == '__main__':
main()
- Output:
[('iced', 'iced'), ('jam', 'iced'), ('jam', 'jam'), ('plain', 'iced'), ('plain', 'jam'), ('plain', 'plain')] 220
Quackery
Regarding the extra credit portion of the task, while this is clearly not the most efficient way of computing the number, it does serve to illustrate that, at the very least, the algorithm generates the correct number of choices, so I am content to comply with the specification rather than demonstrate a more efficient method.
"plaindrome" is not a typo. It is however, a neologism that appears to have little to no currency outside of The On-Line Encyclopedia of Integer Sequences.
( nextplain generates the next plaindrome in the
current base by adding one to a given plaindrome,
then replacing each trailing zero with the least
significant non-zero digit of the number
See: https://oeis.org/search?q=plaindromes
4 base put
-1
10 times
[ nextplain
dup echo sp ]
drop
base release
prints "0 1 2 3 11 12 13 22 23 33"
i.e. decimal "0 1 2 3 5 6 7 10 11 15"
Right padding the base 4 representations with
zeros gives all the combinations with repetitions
for selecting two doughnuts in a store selling
four types of doughnut, numbered 0, 1, 2, and 3.
00 01 02 03 11 12 13 22 23 33 )
[ 1+ dup 0 = if done
0 swap
[ base share /mod
dup 0 = while
drop dip 1+
again ]
swap rot 1+ times
[ base share * over + ]
nip ] is nextplain ( n --> n )
[ dup base put
swap ** 1 -
[] swap -1
[ 2dup > while
nextplain
rot over join
unrot
again ]
base release
2drop ] is kcombnums ( n n --> [ )
[ [] unrot times
[ base share /mod
rot join swap ]
drop ] is ndigits ( n n --> [ )
[ [] unrot
witheach
[ dip dup peek
nested rot swap join
swap ]
drop ] is [peek] ( [ [ --> [ )
[ dup temp put
size dup base put
dip dup kcombnums
[] unrot witheach
[ over ndigits
temp share swap [peek]
nested rot swap join
swap ]
temp release
base release
drop ] is kcombs ( n [ --> [ )
2
$ "jam iced plain" nest$
kcombs
witheach
[ witheach
[ echo$ sp ] cr ]
cr
3 10 kcombnums size echo
- Output:
jam jam iced jam plain jam iced iced plain iced plain plain 220
R
The idiomatic solution is to just use a library.
library(gtools)
combinations(3, 2, c("iced", "jam", "plain"), set = FALSE, repeats.allowed = TRUE)
nrow(combinations(10, 3, repeats.allowed = TRUE))
- Output:
> combinations(3, 2, c("iced", "jam", "plain"), set = FALSE, repeats.allowed = TRUE) [,1] [,2] [1,] "iced" "iced" [2,] "iced" "jam" [3,] "iced" "plain" [4,] "jam" "jam" [5,] "jam" "plain" [6,] "plain" "plain" > nrow(combinations(10, 3, repeats.allowed = TRUE)) [1] 220
Racket
#lang racket
(define (combinations xs k)
(cond [(= k 0) '(())]
[(empty? xs) '()]
[(append (combinations (rest xs) k)
(map (λ(x) (cons (first xs) x))
(combinations xs (- k 1))))]))
Raku
(formerly Perl 6)
One could simply generate all permutations, and then remove "duplicates":
my @S = <iced jam plain>;
my $k = 2;
.put for [X](@S xx $k).unique(as => *.sort.cache, with => &[eqv])
- Output:
iced iced iced jam iced plain jam jam jam plain plain plain
Alternatively, a recursive solution:
proto combs_with_rep (UInt, @) {*}
multi combs_with_rep (0, @) { () }
multi combs_with_rep (1, @a) { map { $_, }, @a }
multi combs_with_rep ($, []) { () }
multi combs_with_rep ($n, [$head, *@tail]) {
|combs_with_rep($n - 1, ($head, |@tail)).map({ $head, |@_ }),
|combs_with_rep($n, @tail);
}
.say for combs_with_rep( 2, [< iced jam plain >] );
# Extra credit:
sub postfix:<!> { [*] 1..$^n }
sub combs_with_rep_count ($k, $n) { ($n + $k - 1)! / $k! / ($n - 1)! }
say combs_with_rep_count( 3, 10 );
- Output:
(iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain) 220
REXX
version 1
This REXX version uses a type of anonymous recursion.
/*REXX pgm displays combination sets with repetitions for X things taken Y at a time*/
call RcombN 3, 2, 'iced jam plain' /*The 1st part of Rosetta Code task. */
call RcombN -10, 3, 'Iced jam plain' /* " 2nd " " " " " */
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
RcombN: procedure; parse arg x,y,syms; tell= x>0; x=abs(x); z=x+1 /*X>0? Show combo*/
say copies('─',15) x "doughnut selection taken" y 'at a time:' /*display title. */
do i=1 for words(syms); $.i=word(syms, i) /*assign symbols.*/
end /*i*/
@.=1 /*assign default.*/
do #=1; if tell then call show /*display combos?*/
@.y=@.y + 1; if @.y==z then if .(y-1) then leave /* ◄─── recursive*/
end /*#*/
say copies('═',15) # "combinations."; say; say /*display answer.*/
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
.: procedure expose @. y z; parse arg ?; if ?==0 then return 1; p=@.? +1
if p==z then return .(? -1); do j=? to y; @.j=p; end /*j*/; return 0
/*──────────────────────────────────────────────────────────────────────────────────────*/
show: L=; do c=1 for y; _=@.c; L=L $._; end /*c*/; say L; return
- output:
─────────────── 3 doughnut selection taken 2 at a time: iced iced iced jam iced plain jam jam jam plain plain plain ═══════════════ 6 combinations. ─────────────── 10 doughnut selection taken 3 at a time: ═══════════════ 220 combinations.
version 2
recursive (taken from version 1) Reformatted and variable names suitable for OoRexx.
/*REXX compute (and show) combination sets for nt things in ns places*/
debug=0
Call time 'R'
Call RcombN 3,2,'iced,jam,plain' /* The 1st part of the task */
Call RcombN -10,3,'iced,jam,plain,d,e,f,g,h,i,j' /* 2nd part */
Call RcombN -10,9,'iced,jam,plain,d,e,f,g,h,i,j' /* extra part */
Say time('E') 'seconds'
Exit
/*-------------------------------------------------------------------*/
Rcombn: Procedure Expose thing. debug
Parse Arg nt,ns,thinglist
tell=nt>0
nt=abs(nt)
Say '------------' nt 'doughnut selection taken' ns 'at a time:'
If tell=0 Then
Say ' list output suppressed'
Do i=1 By 1 While thinglist>''
Parse Var thinglist thing.i ',' thinglist /* assign things. */
End
index.=1
Do cmb=1 By 1
If tell Then /* display combinations */
Call show /* show this one */
index.ns=index.ns+1
Call show_index 'A'
If index.ns==nt+1 Then
If proc(ns-1) Then
Leave
End
Say '------------' cmb 'combinations.'
Say
Return
/*-------------------------------------------------------------------*/
proc: Procedure Expose nt ns thing. index. debug
Parse Arg recnt
If recnt>0 Then Do
p=index.recnt+1
If p=nt+1 Then
Return proc(recnt-1)
Do i=recnt To ns
index.i=p
End
Call show_index 'C'
End
Return recnt=0
/*-------------------------------------------------------------------*/
show: Procedure Expose index. thing. ns debug
l=''
Call show_index 'B----------------------->'
Do i=1 To ns
j=index.i
l=l thing.j
End
Say l
Return
show_index: Procedure Expose index. ns debug
If debug Then Do
Parse Arg tag
l=tag
Do i=1 To ns
l=l index.i
End
Say l
End
Return
- Output:
----------- 3 doughnut selection taken 2 at a time: iced iced iced jam iced plain jam jam jam plain plain plain ------------ 6 combinations. ------------ 10 doughnut selection taken 3 at a time: list output suppressed ------------ 220 combinations. ------------ 10 doughnut selection taken 9 at a time: list output suppressed ------------ 48620 combinations. 0.125000 seconds
version 3
iterative (transformed from version 1)
/*REXX compute (and show) combination sets for nt things in ns places*/
Numeric Digits 20
debug=0
Call time 'R'
Call IcombN 3,2,'iced,jam,plain' /* The 1st part of the task */
Call IcombN -10,3,'iced,jam,plain,d,e,f,g,h,i,j' /* 2nd part */
Call IcombN -10,9,'iced,jam,plain,d,e,f,g,h,i,j' /* extra part */
Say time('E') 'seconds'
Exit
IcombN: Procedure Expose thing. debug
Parse Arg nt,ns,thinglist
tell=nt>0
nt=abs(nt)
Say '------------' nt 'doughnut selection taken' ns 'at a time:'
If tell=0 Then
Say ' list output suppressed'
Do i=1 By 1 While thinglist>''
Parse Var thinglist thing.i ',' thinglist /* assign things. */
End
index.=1
cmb=0
Call show
i=ns+1
Do While i>1
i=i-1
Do j=1 By 1 While index.i<nt
index.i=index.i+1
Call show
End
i1=i-1
If index.i1<nt Then Do
index.i1=index.i1+1
Do ii=i To ns
index.ii=index.i1
End
Call show
i=ns+1
End
If index.1=nt Then Leave
End
Say cmb
Return
show: Procedure Expose ns index. thing. tell cmb
cmb=cmb+1
If tell Then Do
l=''
Do i=1 To ns
j=index.i
l=l thing.j
End
Say l
End
Return
- Output:
------------ 3 doughnut selection taken 2 at a time: iced iced iced jam iced plain jam jam jam plain plain plain 6 ------------ 10 doughnut selection taken 3 at a time: list output suppressed 220 ------------ 10 doughnut selection taken 9 at a time: list output suppressed 48620 0.109000 seconds
Slightly faster
Ring
# Project : Combinations with repetitions
n = 2
k = 3
temp = []
comb = []
num = com(n, k)
combinations(n, k)
comb = sortfirst(comb, 1)
see showarray(comb) + nl
func combinations(n, k)
while true
temp = []
for nr = 1 to k
tm = random(n-1) + 1
add(temp, tm)
next
add(comb, temp)
for p = 1 to len(comb) - 1
for q = p + 1 to len(comb)
if (comb[p][1] = comb[q][1]) and (comb[p][2] = comb[q][2]) and (comb[p][3] = comb[q][3])
del(comb, p)
ok
next
next
if len(comb) = num
exit
ok
end
func com(n, k)
res = pow(n, k)
return res
func showarray(vect)
svect = ""
for nrs = 1 to len(vect)
svect = "[" + vect[nrs][1] + " " + vect[nrs][2] + " " + vect[nrs][3] + "]" + nl
see svect
next
Func sortfirst(alist, ind)
aList = sort(aList,ind)
for n = 1 to len(alist)-1
for m= n + 1 to len(aList)
if alist[n][1] = alist[m][1] and alist[m][2] < alist[n][2]
temp = alist[n]
alist[n] = alist[m]
alist[m] = temp
ok
next
next
for n = 1 to len(alist)-1
for m= n + 1 to len(aList)
if alist[n][1] = alist[m][1] and alist[n][2] = alist[m][2] and alist[m][3] < alist[n][3]
temp = alist[n]
alist[n] = alist[m]
alist[m] = temp
ok
next
next
return aList
Output:
[1 1 1] [1 1 2] [1 2 1] [1 2 2] [2 1 1] [2 1 2] [2 2 1] [2 2 2]
Ruby
possible_doughnuts = ['iced', 'jam', 'plain'].repeated_combination(2)
puts "There are #{possible_doughnuts.count} possible doughnuts:"
possible_doughnuts.each{|doughnut_combi| puts doughnut_combi.join(' and ')}
# Extra credit
possible_doughnuts = [*1..1000].repeated_combination(30)
# size returns the size of the enumerator, or nil if it can’t be calculated lazily.
puts "", "#{possible_doughnuts.size} ways to order 30 donuts given 1000 types."
- Output:
There are 6 possible doughnuts: iced and iced iced and jam iced and plain jam and jam jam and plain plain and plain 5799990040867421088231767567302459508715964845043404147200 ways to order 30 donuts given 1000 types.
Rust
// Iterator for the combinations of `arr` with `k` elements with repetitions.
// Yields the combinations in lexicographical order.
struct CombinationsWithRepetitions<'a, T: 'a> {
// source array to get combinations from
arr: &'a [T],
// length of the combinations
k: u32,
// current counts of each object that represent the next combination
counts: Vec<u32>,
// whether there are any combinations left
remaining: bool,
}
impl<'a, T> CombinationsWithRepetitions<'a, T> {
fn new(arr: &[T], k: u32) -> CombinationsWithRepetitions<T> {
let mut counts = vec![0; arr.len()];
counts[arr.len() - 1] = k;
CombinationsWithRepetitions {
arr,
k,
counts,
remaining: true,
}
}
}
impl<'a, T> Iterator for CombinationsWithRepetitions<'a, T> {
type Item = Vec<&'a T>;
fn next(&mut self) -> Option<Vec<&'a T>> {
if !self.remaining {
return None;
}
let mut comb = Vec::new();
for (count, item) in self.counts.iter().zip(self.arr.iter()) {
for _ in 0..*count {
comb.push(item);
}
}
// this is lexicographically largest, and thus the last combination
if self.counts[0] == self.k {
self.remaining = false;
} else {
let n = self.counts.len();
for i in (1..n).rev() {
if self.counts[i] > 0 {
let original_value = self.counts[i];
self.counts[i - 1] += 1;
for j in i..(n - 1) {
self.counts[j] = 0;
}
self.counts[n - 1] = original_value - 1;
break;
}
}
}
Some(comb)
}
}
fn main() {
let collection = vec!["iced", "jam", "plain"];
for comb in CombinationsWithRepetitions::new(&collection, 2) {
for item in &comb {
print!("{} ", item)
}
println!()
}
}
- Output:
plain plain jam plain jam jam iced plain iced jam iced iced
Scala
Scala has a combinations method in the standard library.
object CombinationsWithRepetition {
def multi[A](as: List[A], k: Int): List[List[A]] =
(List.fill(k)(as)).flatten.combinations(k).toList
def main(args: Array[String]): Unit = {
val doughnuts = multi(List("iced", "jam", "plain"), 2)
for (combo <- doughnuts) println(combo.mkString(","))
val bonus = multi(List(0,1,2,3,4,5,6,7,8,9), 3).size
println("There are "+bonus+" ways to choose 3 items from 10 choices")
}
}
- Output:
iced,iced iced,jam iced,plain jam,jam jam,plain plain,plain There are 220 ways to choose 3 items from 10 choices
Scheme
(define (combs-with-rep k lst)
(cond ((= k 0) '(()))
((null? lst) '())
(else
(append
(map
(lambda (x)
(cons (car lst) x))
(combs-with-rep (- k 1) lst))
(combs-with-rep k (cdr lst))))))
(display (combs-with-rep 2 (list "iced" "jam" "plain"))) (newline)
(display (length (combs-with-rep 3 '(1 2 3 4 5 6 7 8 9 10)))) (newline)
- Output:
((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain)) 220
Dynamic programming
(define (combs-with-rep m lst)
(define arr (make-vector (+ m 1) '()))
(vector-set! arr 0 '(()))
(for-each (lambda (x)
(do ((i 1 (+ i 1)))
((> i m))
(vector-set! arr i (append (vector-ref arr i)
(map (lambda (xs) (cons x xs))
(vector-ref arr (- i 1)))))
)
) lst)
(vector-ref arr m))
(display (combs-with-rep 2 (list "iced" "jam" "plain"))) (newline)
(display (length (combs-with-rep 3 '(1 2 3 4 5 6 7 8 9 10)))) (newline)
- Output:
((iced iced) (jam iced) (jam jam) (plain iced) (plain jam) (plain plain)) 220
Sidef
func cwr (n, l, a = []) {
n>0 ? (^l -> map {|k| __FUNC__(n-1, l.slice(k), [a..., l[k]]) }) : a
}
cwr(2, %w(iced jam plain)).each {|a|
say a.map{ .join(' ') }.join("\n")
}
Also built-in:
%w(iced jam plain).combinations_with_repetition(2, {|*a|
say a.join(' ')
})
- Output:
iced iced iced jam iced plain jam jam jam plain plain plain
Efficient count of the total number of combinations with repetition:
func cwr_count (n, m) { binomial(n + m - 1, m) }
printf("\nThere are %s ways to pick 7 out of 10 with repetition\n", cwr_count(10, 7))
- Output:
There are 11440 ways to pick 7 out of 10 with repetition
Standard ML
let rec combs_with_rep k xxs =
match k, xxs with
| 0, _ -> [[]]
| _, [] -> []
| k, x::xs ->
List.map (fun ys -> x::ys) (combs_with_rep (k-1) xxs)
@ combs_with_rep k xs
in the interactive loop:
- combs_with_rep (2, ["iced", "jam", "plain"]) ; val it = [["iced","iced"],["iced","jam"],["iced","plain"],["jam","jam"], ["jam","plain"],["plain","plain"]] : string list list - length (combs_with_rep (3, [1,2,3,4,5,6,7,8,9,10])) ; val it = 220 : int
Dynamic programming
fun combs_with_rep (m, xs) = let
val arr = Array.array (m+1, [])
in
Array.update (arr, 0, [[]]);
app (fn x =>
Array.modifyi (fn (i, y) =>
if i = 0 then y else y @ map (fn xs => x::xs) (Array.sub (arr, i-1))
) arr
) xs;
Array.sub (arr, m)
end
in the interactive loop:
- combs_with_rep (2, ["iced", "jam", "plain"]) ; val it = [["iced","iced"],["jam","iced"],["jam","jam"],["plain","iced"], ["plain","jam"],["plain","plain"]] : string list list - length (combs_with_rep (3, [1,2,3,4,5,6,7,8,9,10])) ; val it = 220 : int
Stata
function combrep(v,k) {
n = cols(v)
a = J(comb(n+k-1,k),k,v[1])
u = J(1,k,1)
for (i=2; 1; i++) {
for (j=k; j>0; j--) {
if (u[j]<n) break
}
if (j<1) return(a)
m = u[j]+1
for (; j<=k; j++) u[j] = m
a[i,.] = v[u]
}
}
combrep(("iced","jam","plain"),2)
a = combrep(1..10,3)
rows(a)
Output
1 2 +-----------------+ 1 | iced iced | 2 | iced jam | 3 | iced plain | 4 | jam jam | 5 | jam plain | 6 | plain plain | +-----------------+ 220
Swift
func combosWithRep<T>(var objects: [T], n: Int) -> [[T]] {
if n == 0 { return [[]] } else {
var combos = [[T]]()
while let element = objects.last {
combos.appendContentsOf(combosWithRep(objects, n: n - 1).map{ $0 + [element] })
objects.removeLast()
}
return combos
}
}
print(combosWithRep(["iced", "jam", "plain"], n: 2).map {$0.joinWithSeparator(" and ")}.joinWithSeparator("\n"))
Output:
plain and plain jam and plain iced and plain jam and jam iced and jam iced and iced
Tcl
package require Tcl 8.5
proc combrepl {set n {presorted no}} {
if {!$presorted} {
set set [lsort $set]
}
if {[incr n 0] < 1} {
return {}
} elseif {$n < 2} {
return $set
}
# Recursive call
set res [combrepl $set [incr n -1] yes]
set result {}
foreach item $set {
foreach inner $res {
dict set result [lsort [list $item {*}$inner]] {}
}
}
return [dict keys $result]
}
puts [combrepl {iced jam plain} 2]
puts [llength [combrepl {1 2 3 4 5 6 7 8 9 10} 3]]
- Output:
{iced iced} {iced jam} {iced plain} {jam jam} {jam plain} {plain plain} 220
TXR
txr -p "(rcomb '(iced jam plain) 2)"
- Output:
((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))
txr -p "(length-list (rcomb '(0 1 2 3 4 5 6 7 8 9) 3))"
- Output:
220
Ursala
#import std
#import nat
cwr = ~&s+ -<&*+ ~&K0=>&^|DlS/~& iota # takes a set and a selection size
#cast %gLSnX
main = ^|(~&,length) cwr~~/(<'iced','jam','plain'>,2) ('1234567890',3)
- Output:
( { <'iced','iced'>, <'iced','jam'>, <'iced','plain'>, <'jam','jam'>, <'jam','plain'>, <'plain','plain'>}, 220)
VBScript
' Combinations with repetitions - iterative - VBScript
Sub printc(vi,n,vs)
Dim i, w
For i=0 To n-1
w=w &" "& vs(vi(i))
Next 'i
Wscript.Echo w
End Sub
Sub combine(flavors, draws, xitem, tell)
Dim n, i, j
ReDim v(draws)
If tell Then Wscript.Echo "list of cwr("& flavors &","& draws &") :"
Do While True
For i=0 To draws-1
If v(i)>flavors-1 Then
v(i+1)=v(i+1)+1
For j=i To 0 Step -1
v(j)=v(i+1)
Next 'j
End If
Next 'i
If v(draws)>0 Then Exit Do
n=n+1
If tell Then Call printc(v, draws, xitem)
v(0)=v(0)+1
Loop
Wscript.Echo "cwr("& flavors &","& draws &")="&n
End Sub
items=Array( "iced", "jam", "plain" )
combine 3, 2, items, True
combine 10, 3, , False
combine 10, 7, , False
combine 10, 9, , False
- Output:
list of cwr(3,2) : iced iced jam iced plain iced jam jam plain jam plain plain cwr(3,2)=6 cwr(10,3)=220 cwr(10,7)=11440 cwr(10,9)=48620
Wren
Concise recursive
Produces results in no particular order.
var Combrep = Fn.new { |n, lst|
if (n == 0 ) return [[]]
if (lst.count == 0) return []
var r = Combrep.call(n, lst[1..-1])
for (x in Combrep.call(n-1, lst)) {
var y = x.toList
y.add(lst[0])
r.add(y)
}
return r
}
System.print(Combrep.call(2, ["iced", "jam", "plain"]))
System.print(Combrep.call(3, (1..10).toList).count)
- Output:
[[plain, plain], [plain, jam], [jam, jam], [plain, iced], [jam, iced], [iced, iced]] 220
Library based
Produces results in lexicographic order.
import "./seq" for Lst
import "./perm" for Comb
var a = ["iced", "jam", "plain"]
a = Lst.flatten(Lst.zip(a, a))
System.print(Comb.listDistinct(a, 2))
a = (1..10).toList
a = Lst.flatten(Lst.zip(Lst.zip(a, a), a))
System.print(Comb.listDistinct(a, 3).count)
- Output:
[[iced, iced], [iced, jam], [iced, plain], [jam, jam], [jam, plain], [plain, plain]] 220
XPL0
code ChOut=8, CrLf=9, IntOut=11, Text=12;
int Count, Array(10);
proc Combos(D, S, K, N, Names); \Generate all size K combinations of N objects
int D, S, K, N, Names; \depth of recursion, starting value of N, etc.
int I;
[if D<K then \depth < size
[for I:= S to N-1 do
[Array(D):= I;
Combos(D+1, I, K, N, Names);
];
]
else [Count:= Count+1;
if Names(0) then
[for I:= 0 to K-1 do
[Text(0, Names(Array(I))); ChOut(0, ^ )];
CrLf(0);
];
];
];
[Count:= 0;
Combos(0, 0, 2, 3, ["iced", "jam", "plain"]);
Text(0, "Combos = "); IntOut(0, Count); CrLf(0);
Count:= 0;
Combos(0, 0, 3, 10, [0]);
Text(0, "Combos = "); IntOut(0, Count); CrLf(0);
]
- Output:
iced iced iced jam iced plain jam jam jam plain plain plain Combos = 6 Combos = 220
zkl
fcn combosK(k,seq){ // repeats, seq is finite
if (k==1) return(seq);
if (not seq) return(T);
self.fcn(k-1,seq).apply(T.extend.fp(seq[0])).extend(self.fcn(k,seq[1,*]));
}
combosK(2,T("iced","jam","plain")).apply("concat",",");
combosK(3,T(0,1,2,3,4,5,6,7,8,9)).len();
- Output:
L("iced,iced","iced,jam","iced,plain","jam,jam","jam,plain","plain,plain") 220
ZX Spectrum Basic
10 READ n
20 DIM d$(n,5)
30 FOR i=1 TO n
40 READ d$(i)
50 NEXT i
60 DATA 3,"iced","jam","plain"
70 FOR i=1 TO n
80 FOR j=i TO n
90 PRINT d$(i);" ";d$(j)
100 NEXT j
110 NEXT i
- Programming Tasks
- Discrete math
- 11l
- 360 Assembly
- Acornsoft Lisp
- Action!
- Ada
- AppleScript
- Arturo
- AutoHotkey
- AWK
- BASIC
- BASIC256
- BBC BASIC
- IS-BASIC
- Bracmat
- C
- C sharp
- C++
- Clojure
- CoffeeScript
- Common Lisp
- Crystal
- D
- EasyLang
- EchoLisp
- Egison
- Elixir
- Erlang
- Factor
- Fortran
- FreeBASIC
- GAP
- Go
- Haskell
- Icon
- Unicon
- J
- Java
- JavaScript
- Jq
- Julia
- Kotlin
- LFE
- Lobster
- Lua
- Maple
- Mathematica
- Wolfram Language
- Mercury
- Nim
- OCaml
- PARI/GP
- Pascal
- Perl
- Phix
- PHP
- PicoLisp
- Prolog
- PureBasic
- Python
- Quackery
- R
- Racket
- Raku
- REXX
- Ring
- Ruby
- Rust
- Scala
- Scheme
- Sidef
- Standard ML
- Stata
- Swift
- Tcl
- TXR
- Ursala
- VBScript
- Wren
- Wren-seq
- Wren-perm
- XPL0
- Zkl
- ZX Spectrum Basic