Combinations with repetitions: Difference between revisions
→Concise recursive: Changed to Wren S/H
(→Concise recursive: Changed to Wren S/H) |
|||
(47 intermediate revisions by 26 users not shown) | |||
Line 24:
{{Template:Combinations and permutations}}
<br><br>
=={{header|11l}}==
{{trans|Nim}}
<syntaxhighlight lang="11l">F combsReps(lst, k)
T Ty = T(lst[0])
I k == 0
R [[Ty]()]
I lst.empty
R [[Ty]]()
R combsReps(lst, k - 1).map(x -> @lst[0] [+] x) [+] combsReps(lst[1..], k)
print(combsReps([‘iced’, ‘jam’, ‘plain’], 2))
print(combsReps(Array(1..10), 3).len)</syntaxhighlight>
{{out}}
<pre>
[[iced, iced], [iced, jam], [iced, plain], [jam, jam], [jam, plain], [plain, plain]]
220
</pre>
=={{header|360 Assembly}}==
<syntaxhighlight lang="360asm">* Combinations with repetitions - 16/04/2019
COMBREP CSECT
USING COMBREP,R13 base register
B 72(R15) skip savearea
DC 17F'0' savearea
SAVE (14,12) save previous context
ST R13,4(R15) link backward
ST R15,8(R13) link forward
LR R13,R15 set addressability
MVC FLAVORS(9),SET1 flavors=3,draws=2,tell=1
BAL R14,COMBINE call combine
MVC FLAVORS(9),SET2 flavors=10,draws=3,tell=0
BAL R14,COMBINE call combine
L R13,4(0,R13) restore previous savearea pointer
RETURN (14,12),RC=0 restore registers from calling sav
COMBINE SR R9,R9 n=0
MVI V,X'00' ~
MVC V+1(NN*L'V-1),V v=0
IF CLI,TELL,EQ,X'01' THEN if tell then
XPRNT =C'list:',5 print
ENDIF , endif
LOOP LA R6,1 i=1
DO WHILE=(C,R6,LE,DRAWS) do i=1 to draws
LR R1,R6 i
SLA R1,2 ~
L R2,V-4(R1) v(i)
L R3,FLAVORS flavors
BCTR R3,0 flavors-1
IF CR,R2,GT,R3 THEN if v(i)>flavors-1 then
LR R1,R6 i
SLA R1,2 ~
LA R1,V(R1) @v(i+1)
L R2,0(R1) v(i+1)
LA R2,1(R2) v(i+1)+1
ST R2,0(R1) v(i+1)=v(i+1)+1
LR R7,R6 j=i
DO WHILE=(C,R7,GE,=A(1)) do j=i to 1 by -1
LR R1,R6 i
SLA R1,2 ~
L R2,V(R1) v(i+1)
LR R1,R7 j
SLA R1,2 ~
ST R2,V-4(R1) v(j)=v(i+1)
BCTR R7,0 j--
ENDDO , enddo j
ENDIF , endif
LA R6,1(R6) i++
ENDDO , enddo i
L R1,DRAWS draws
LA R1,1(R1) draws+1
SLA R1,2 ~
L R2,V-4(R1) v(draws+1)
LTR R2,R2 if v(draws+1)>0
BP EXITLOOP then exit loop
LA R9,1(R9) n=n+1
IF CLI,TELL,EQ,X'01' THEN if tell then
MVC BUF,=CL60' ' buf=' '
LA R10,1 ibuf=1
LA R6,1 i=1
DO WHILE=(C,R6,LE,DRAWS) do i=1 to draws
LR R1,R6 i
SLA R1,2 ~
L R1,V-4(R1) v(i)
MH R1,=AL2(L'ITEMS) ~
LA R4,ITEMS(R1) @items(v(i)+1)
LA R5,BUF-1 @buf-1
AR R5,R10 +ibuf
MVC 0(6,R5),0(R4) substr(buf,ibuf,6)=items(v(i)+1)
LA R10,L'ITEMS(R10) ibuf=ibuf+length(items)
LA R6,1(R6) i++
ENDDO , enddo i
XPRNT BUF,L'BUF print buf
ENDIF , endif
L R2,V v(1)
LA R2,1(R2) v(1)+1
ST R2,V v(1)=v(1)+1
B LOOP loop
EXITLOOP L R1,FLAVORS flavors
XDECO R1,XDEC edit flavors
MVC PG+4(2),XDEC+10 output flavors
L R1,DRAWS draws
XDECO R1,XDEC edit draws
MVC PG+7(2),XDEC+10 output draws
XDECO R9,PG+11 edit & output n
XPRNT PG,L'PG print buffer
BR R14 return
NN EQU 16
ITEMS DC CL6'iced',CL6'jam',CL6'plain'
FLAVORS DS F
DRAWS DS F
TELL DS X
SET1 DC F'3',F'2',X'01' flavors=3,draws=2,tell=1
SET2 DC F'10',F'3',X'00' flavors=10,draws=3,tell=0
V DS (NN)F v(nn)
BUF DS CL60 buf
PG DC CL40'cwr(..,..)=............'
XDEC DS CL12 temp for xdeco
REGEQU
END COMBREP </syntaxhighlight>
{{out}}
<pre>
list:
iced iced
jam iced
plain iced
jam jam
plain jam
plain plain
cwr( 3, 2)= 6
cwr(10, 3)= 220
</pre>
=={{header|Acornsoft Lisp}}==
{{trans|Scheme}}
<syntaxhighlight lang="lisp">
(defun samples (k items)
(cond
((zerop k) '(()))
((null items) '())
(t (append
(mapc '(lambda (c) (cons (car items) c))
(samples (sub1 k) items))
(samples k (cdr items))))))
(defun append (a b)
(cond ((null a) b)
(t (cons (car a) (append (cdr a) b)))))
(defun length (list (len . 0))
(map '(lambda (e) (setq len (add1 len)))
list)
len)
</syntaxhighlight>
{{Out}}
<pre>
Evaluate : (samples 2 '(iced jam plain))
Value is : ((iced iced) (iced jam) (iced plain) (jam jam)
(jam plain) (plain plain))
Evaluate : (length (samples 3 '(1 2 3 4 5 6 7 8 9 10)))
Value is : 220
</pre>
=={{header|Action!}}==
<syntaxhighlight lang="action!">PROC PrintComb(BYTE ARRAY c BYTE len)
BYTE i,ind
FOR i=0 TO len-1
DO
IF i>0 THEN Put('+) FI
ind=c(i)
IF ind=0 THEN
Print("iced")
ELSEIF ind=1 THEN
Print("jam")
ELSE
Print("plain")
FI
OD
PutE()
RETURN
BYTE FUNC NotDecreasing(BYTE ARRAY c BYTE len)
BYTE i
IF len<2 THEN RETURN (1) FI
FOR i=0 TO len-2
DO
IF c(i)>c(i+1) THEN
RETURN (0)
FI
OD
RETURN (1)
BYTE FUNC NextComb(BYTE ARRAY c BYTE n,k)
INT pos,i
DO
pos=k-1
DO
c(pos)==+1
IF c(pos)<n THEN
EXIT
ELSE
pos==-1
IF pos<0 THEN RETURN (0) FI
FI
FOR i=pos+1 TO k-1
DO
c(i)=c(pos)
OD
OD
UNTIL NotDecreasing(c,k)
OD
RETURN (1)
PROC Comb(BYTE n,k,show)
BYTE ARRAY c(10)
BYTE i,count
IF k>n THEN
Print("Error! k is greater than n.")
Break()
FI
PrintF("Choices of %B from %B:%E",k,n)
FOR i=0 TO k-1
DO
c(i)=0
OD
count=0
DO
count==+1
IF show THEN
PrintF(" %B. ",count)
PrintComb(c,k)
FI
UNTIL NextComb(c,n,k)=0
OD
PrintF("Total choices %B%E%E",count)
RETURN
PROC Main()
Comb(3,2,1)
Comb(10,3,0)
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Combinations_with_repetitions.png Screenshot from Atari 8-bit computer]
<pre>
Choices of 2 from 3:
1. iced+iced
2. iced+jam
3. iced+plain
4. jam+jam
5. jam+plain
6. plain+plain
Total choices 6
Choices of 3 from 10:
Total choices 220
</pre>
=={{header|Ada}}==
Line 29 ⟶ 299:
combinations.adb:
<
procedure Combinations is
Line 92 ⟶ 362:
Ada.Text_IO.Put_Line ("Total Donuts:" & Natural'Image (Donut_Count));
Ada.Text_IO.Put_Line ("Total Tens:" & Natural'Image (Ten_Count));
end Combinations;</
{{out}}
Line 107 ⟶ 377:
{{Trans|Haskell}}
{{Trans|Python}}
<
-- combinationsWithRepetition :: Int -> [a] -> [kTuple a]
on combinationsWithRepetition(k, xs)
-- A list of lists, representing
-- sets of cardinality k, with
-- members drawn from xs.
script
script f
on |λ|(a, x)
Line 127 ⟶ 399:
end |λ|
end script
scanl1(go, a)
end |λ|
Line 136 ⟶ 409:
end script
|Just| of |index|(|λ|(xs) of
end combinationsWithRepetition
-
on run
{length of
end run
-
-- Just :: a -> Maybe a
Line 153 ⟶ 426:
{type:"Maybe", Nothing:false, Just:x}
end Just
-- Nothing :: Maybe a
Line 158 ⟶ 432:
{type:"Maybe", Nothing:true}
end Nothing
-- enumFromTo :: (Int, Int) -> [Int]
Line 171 ⟶ 446:
end if
end enumFromTo
-- foldl :: (a -> b -> a) -> a -> [b] -> a
Line 183 ⟶ 459:
end tell
end foldl
-- index (!!) :: [a] -> Int -> Maybe a
Line 205 ⟶ 482:
end if
end |index|
-- map :: (a -> b) -> [a] -> [b]
Line 217 ⟶ 495:
end tell
end map
-- min :: Ord a => a -> a -> a
Line 226 ⟶ 505:
end if
end min
-- Lift 2nd class handler function into 1st class script wrapper
Line 238 ⟶ 518:
end if
end mReturn
-- repeat :: a -> Generator [a]
Line 262 ⟶ 543:
end tell
end scanl
-- scanl1 :: (a -> a -> a) -> [a] -> [a]
Line 303 ⟶ 585:
missing value
end if
end take</
{{Out}}
<pre>{220, {{"iced", "iced"}, {"jam", "iced"}, {"jam", "jam"}, {"plain", "iced"}, {"plain", "jam"}, {"plain", "plain"}}}</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">print combine.repeated.by:2 ["iced" "jam" "plain"]
print combine.count.repeated.by:3 @1..10</syntaxhighlight>
{{out}}
<pre>[iced iced] [iced jam] [iced plain] [jam jam] [jam plain] [plain plain]
220</pre>
=={{header|AutoHotkey}}==
<syntaxhighlight lang="autohotkey">;===========================================================
; based on "https://www.geeksforgeeks.org/combinations-with-repetitions/"
;===========================================================
CombinationRepetition(arr, k:=0, Delim:="") {
CombinationRepetitionUtil(arr, k?k:str.count(), Delim, [k+1], result:=[])
return result
} ;===========================================================
CombinationRepetitionUtil(arr, k, Delim, chosen, result , index:=1, start:=1){
line := [], i:=0, res := ""
if (index = k+1){
while (++i <= k)
res .= arr[chosen[i]] Delim, line.push(arr[chosen[i]])
return result.Push(Trim(res, Delim))
}
i:=start
while (i <= arr.count())
chosen[Index]:=i, CombinationRepetitionUtil(arr, k, Delim, chosen, result, index+1, i++)
} ;===========================================================</syntaxhighlight>
Examples:<syntaxhighlight lang="autohotkey">result := CombinationRepetition(["iced","jam","plain"], 2, " + ")
for k, v in result
res .= v "`n"
res := trim(res, ",") "`n"
MsgBox % result.count() " Combinations with Repetition found:`n" res
MsgBox % CombinationRepetition([0,1,2,3,4,5,6,7,8,9], 3).Count()</syntaxhighlight>
Outputs:<pre>---------------------------
6 Combinations with Repetition found:
iced + iced
iced + jam
iced + plain
jam + jam
jam + plain
plain + plain
---------------------------
220
---------------------------</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f COMBINATIONS_WITH_REPETITIONS.AWK
BEGIN {
Line 332 ⟶ 661:
exit(0)
}
</syntaxhighlight>
<p>output:</p>
<pre>
Line 344 ⟶ 673:
</pre>
=={{header|
==={{header|BASIC256}}===
<syntaxhighlight lang="basic256">arraybase 0
print "Enter n comb m. "
input integer "n: ", n
input integer "m: ", m
outstr$ = ""
dim names$(m)
for i = 0 to m - 1
print "Name for item "; i; ": ";
input string names$[i]
next i
call iterate (outstr$, 0, m-1, n-1, names$)
end
subroutine iterate(curr$, start, stp, depth, names$)
for i = start to stp
if depth = 0 then
print curr$; " "; names$[i]
else
call iterate (curr$ & " " & names$[i], i, stp, depth-1, names$)
end if
next i
return
end subroutine</syntaxhighlight>
==={{header|BBC BASIC}}===
{{works with|BBC BASIC for Windows}}
<
list$() = "iced", "jam", "plain"
PRINT "Choices of 2 from 3:"
Line 372 ⟶ 728:
c% += FNchoose(n% + 1, l%, i%, m%, g%(), n$())
NEXT
= c%</
{{out}}
<pre>
Line 387 ⟶ 743:
Total choices = 220
</pre>
==={{header|IS-BASIC}}===
<syntaxhighlight lang="is-basic">100 PROGRAM "Combinat.bas"
110 READ N
120 STRING D$(1 TO N)*5
130 FOR I=1 TO N
140 READ D$(I)
150 NEXT
160 FOR I=1 TO N
170 FOR J=I TO N
180 PRINT D$(I);" ";D$(J)
190 NEXT
200 NEXT
210 DATA 3,iced,jam,plain</syntaxhighlight>
=={{header|Bracmat}}==
This minimalist solution expresses the answer as a sum of products. Bracmat automatically normalises such expressions: terms and factors are sorted alphabetically, products containing a sum as a factor are decomposed in a sum of factors (unless the product is not itself term in a multiterm expression). Like factors are converted to a single factor with an appropriate exponent, so <code>ice^2</code> is to be understood as ice twice.
<
= n things thing result
. !arg:(?n.?things)
Line 408 ⟶ 778:
& out$(choices$(2.iced jam plain))
& out$(choices$(3.iced jam plain butter marmite tahin fish salad onion grass):?+[?N&!N)
);</
{{out}}
<pre>iced^2+jam^2+plain^2+iced*jam+iced*plain+jam*plain
Line 414 ⟶ 784:
=={{header|C}}==
Non recursive solution
<syntaxhighlight lang="c">
#include <stdio.h>
const char *donuts[] = {"iced", "jam", "plain",
"something completely different"};
int pos[] = {0, 0, 0, 0};
void printDonuts(int k) {
for (size_t i = 1; i < k + 1; i += 1) // offset: i:1..N, N=k+1
printf("%s\t", donuts[pos[i]]); // str:0..N-1
printf("\n");
}
// idea: custom number system with 2s complement like 0b10...0==MIN stop case
void combination_with_repetiton(int n, int k) {
while (1) {
for (int i = k; i > 0; i -= 1) {
if (pos[i] > n - 1) // if number spilled over: xx0(n-1)xx
{
pos[i - 1] += 1; // set xx1(n-1)xx
for (int j = i; j <= k; j += 1)
pos[j] = pos[j - 1]; // set xx11..1
}
}
if (pos[0] > 0) // stop condition: 1xxxx
break;
printDonuts(k);
pos[k] += 1; // xxxxN -> xxxxN+1
}
}
int main() {
combination_with_repetiton(3, 2);
return 0;
}
</syntaxhighlight>
<syntaxhighlight lang="c">#include <stdio.h>
const char * donuts[] = { "iced", "jam", "plain", "something completely different" };
Line 446 ⟶ 854:
return 0;
}
</syntaxhighlight>
{{out}}<pre>iced iced
iced jam
Line 459 ⟶ 867:
{{trans|PHP}}
<
using System;
using System.Collections.Generic;
Line 518 ⟶ 926:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 531 ⟶ 939:
Recursive version
<
using System;
class MultiCombination
Line 555 ⟶ 963:
}
</syntaxhighlight>
=={{header|C++}}==
Non recursive version.
<
#include <
#include <
#include <
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
}
// 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
jam
jam plain
plain
</pre>
Line 614 ⟶ 1,020:
{{trans|Scheme}}
<
(defn combinations [coll k]
(when-let [[x & xs] coll]
Line 621 ⟶ 1,027:
(concat (map (partial cons x) (combinations coll (dec k)))
(combinations xs k)))))
</syntaxhighlight>
{{out}}
Line 630 ⟶ 1,036:
=={{header|CoffeeScript}}==
<
combos = (arr, k) ->
return [ [] ] if k == 0
Line 643 ⟶ 1,049:
console.log combos arr, 2
console.log "#{combos([1..10], 3).length} ways to order 3 donuts given 10 types"
</syntaxhighlight>
{{out}}
Line 659 ⟶ 1,065:
=={{header|Common Lisp}}==
The code below is a modified version of the Clojure solution.
<
(let ((x (car xs)))
(cond
Line 667 ⟶ 1,073:
(combinations xs (1- k)))
(combinations (cdr xs) k))))))
</syntaxhighlight>
{{out}}
Line 675 ⟶ 1,081:
=={{header|Crystal}}==
{{trans|Ruby}}
<
puts "There are #{possible_doughnuts.size} possible doughnuts:"
possible_doughnuts.each{|doughnut_combi| puts doughnut_combi.join(" and ")}
Line 682 ⟶ 1,088:
possible_doughnuts = (1..10).to_a.repeated_combinations(3)
# size returns the size of the enumerator, or nil if it can’t be calculated lazily.
puts "", "#{possible_doughnuts.size} ways to order 3 donuts given 10 types."</
{{out}}
<pre>
Line 698 ⟶ 1,104:
=={{header|D}}==
Using [http://www.graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation lexicographic next bit permutation] to generate combinations with repetitions.
<
const struct CombRep {
Line 786 ⟶ 1,192:
writeln("Ways to select 3 from 10 types is ",
CombRep(10, 3).length);
}</
{{out}}
<pre> iced iced
Line 797 ⟶ 1,203:
===Short Recursive Version===
<
T[][] combsRep(T)(T[] lst, in int k) {
Line 812 ⟶ 1,218:
["iced", "jam", "plain"].combsRep(2).writeln;
10.iota.array.combsRep(3).length.writeln;
}</
{{out}}
<pre>[["iced", "iced"], ["iced", "jam"], ["iced", "plain"], ["jam", "jam"], ["jam", "plain"], ["plain", "plain"]]
Line 819 ⟶ 1,225:
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
items$[] = [ "iced" "jam" "plain" ]
n = len items$[]
k = 2
Line 825 ⟶ 1,232:
n_results = 0
#
n_results += 1
if len items$[] > 0
s$ = ""
for i
s$ &= items$[result[i]] & " "
.
print s$
.
.
if pos
else
for i = val to n
result[pos] = i
.
.
.
#
n = 10
Line 852 ⟶ 1,259:
items$[] = [ ]
n_results = 0
print ""
print n_results & " results with 10 donuts"
</syntaxhighlight>
{{out}}
Line 870 ⟶ 1,278:
=={{header|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
Line 913 ⟶ 1,321:
→ 220
</syntaxhighlight>
=={{header|Egison}}==
<
(define $comb/rep
(lambda [$n $xs]
Line 924 ⟶ 1,332:
(test (comb/rep 2 {"iced" "jam" "plain"}))
</syntaxhighlight>
{{out}}
<pre>
Line 932 ⟶ 1,340:
=={{header|Elixir}}==
{{trans|Erlang}}
<
def comb_rep(0, _), do: [[]]
def comb_rep(_, []), do: []
Line 943 ⟶ 1,351:
Enum.each(RC.comb_rep(2, s), fn x -> IO.inspect x end)
IO.puts "\nExtra credit: #{length(RC.comb_rep(3, Enum.to_list(1..10)))}"</
{{out}}
Line 958 ⟶ 1,366:
=={{header|Erlang}}==
<
-module(comb).
-compile(export_all).
Line 968 ⟶ 1,376:
comb_rep(N,[H|T]=S) ->
[[H|L] || L <- comb_rep(N-1,S)]++comb_rep(N,T).
</syntaxhighlight>
{{out}}
<pre>
Line 980 ⟶ 1,388:
95> length(comb:comb_rep(3,lists:seq(1,10))).
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>
=={{header|Fortran}}==
<syntaxhighlight lang="fortran">
program main
integer :: chosen(4)
Line 1,037 ⟶ 1,463:
end program main
</syntaxhighlight>
{{out}}
<pre>
Line 1,047 ⟶ 1,473:
plain plain
Total = 6
</pre>
=={{header|FreeBASIC}}==
<syntaxhighlight lang="freebasic">sub iterate( byval curr as string, byval start as uinteger,_
byval stp as uinteger, byval depth as uinteger,_
names() as string )
dim as uinteger i
for i = start to stp
if depth = 0 then
print curr + " " + names(i)
else
iterate curr+" "+names(i), i, stp, depth-1, names()
end if
next i
return
end sub
dim as uinteger m, n, o, i
input "Enter n comb m. ", n, m
dim as string outstr = ""
dim as string names(0 to m-1)
for i = 0 to m - 1
print "Name for item ",+i
input names(i)
next i
iterate outstr, 0, m-1, n-1, names()</syntaxhighlight>
{{out}}<pre>
Enter n comb m. 2,3
Name for item 0
? Iced
Name for item 1
? Jam
Name for item 2
? Plain
Iced Iced
Iced Jam
Iced Plain
Jam Jam
Jam Plain
Plain Plain
</pre>
=={{header|GAP}}==
<
UnorderedTuples(["iced", "jam", "plain"], 2);</
=={{header|Go}}==
===Concise recursive===
<
import "fmt"
Line 1,077 ⟶ 1,544:
fmt.Println(len(combrep(3,
[]string{"1", "2", "3", "4", "5", "6", "7", "8", "9", "10"})))
}</
{{out}}
<pre>
Line 1,086 ⟶ 1,553:
===Channel===
Using channel and goroutine, showing how to use synced or unsynced communication.
<
import "fmt"
Line 1,143 ⟶ 1,610:
}
fmt.Printf("\npicking 3 of 10: %d\n", count)
}</
{{out}}
<pre>
Line 1,157 ⟶ 1,624:
===Multiset===
This version has proper representation of sets and multisets.
<
import (
Line 1,258 ⟶ 1,725:
}
fmt.Println(len(combrep(3, ten)))
}</
{{out}}
<pre>
Line 1,271 ⟶ 1,738:
=={{header|Haskell}}==
<
-- list. We ignore the case where k is greater than the length of
-- the list.
Line 1,294 ⟶ 1,761:
main = do
print $ combsWithRep 2 ["iced", "jam", "plain"]
print $ countCombsWithRep 3 [1 .. 10]</
{{out}}
<pre>[["iced","iced"],["iced","jam"],["iced","plain"],["jam","jam"],["jam","plain"],["plain","plain"]]
Line 1,303 ⟶ 1,770:
The first solution is inefficient because it repeatedly calculates the same subproblem in different branches of recursion. For example, <code>combsWithRep k (x:xs)</code> involves computing <code>combsWithRep (k-1) (x:xs)</code> and <code>combsWithRep k xs</code>, both of which (separately) compute <code>combsWithRep (k-1) xs</code>. To avoid repeated computation, we can use dynamic programming:
<
combsWithRep k xs = combsBySize xs !! k
where
Line 1,310 ⟶ 1,777:
main :: IO ()
main = print $ combsWithRep 2 ["iced", "jam", "plain"]</
and another approach, using manual recursion:
<syntaxhighlight lang="haskell">--------------- COMBINATIONS WITH REPETITION -------------
combinationsWithRepetition ::
(Eq a) =>
Int ->
[a] ->
[[a]]
combinationsWithRepetition k xs = cmb k []
where
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]</syntaxhighlight>
{{Out}}
<pre>[["iced","iced"],["jam","iced"],["plain","iced"],["jam","jam"],["plain","jam"],["plain","plain"]]
Line 1,335 ⟶ 1,813:
Following procedure is a generator, which generates each combination of length n in turn:
<syntaxhighlight lang="icon">
# generate all combinations of length n from list L,
# including repetitions
Line 1,353 ⟶ 1,831:
}
end
</syntaxhighlight>
Test procedure:
<syntaxhighlight lang="icon">
# convenience function
procedure write_list (l)
Line 1,374 ⟶ 1,852:
write ("There are " || count || " possible combinations of 3 from 10")
end
</syntaxhighlight>
{{out}}
Line 1,386 ⟶ 1,864:
There are 220 possible combinations of 3 from 10
</pre>
=={{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.
<
Example use:
<
┌─────┬─────┐
│iced │iced │
Line 1,423 ⟶ 1,887:
└─────┴─────┘
#3 rcomb i.10 NB. # ways to choose 3 items from 10 with repetitions
220</
===J Alternate implementation===
Line 1,429 ⟶ 1,893:
Considerably faster:
<
rcomb=: (combrep #) { ]</syntaxhighlight>
This definition of <code>rcomb</code>
<
0 0
0 1
Line 1,441 ⟶ 1,904:
1 1
1 2
2 2</
=={{header|Java}}==
'''MultiCombinationsTester.java'''
<
import com.objectwave.utility.*;
Line 1,474 ⟶ 1,937:
}
} // class
</syntaxhighlight>
'''MultiCombinations.java'''
<
import com.objectwave.utility.*;
import java.util.*;
Line 1,526 ⟶ 1,989:
}
} // class
</syntaxhighlight>
{{out}}
Line 1,543 ⟶ 2,006:
===ES5===
====Imperative====
<
<body><pre id='x'></pre><script type="application/javascript">
function disp(x) {
Line 1,566 ⟶ 2,029:
disp(pick(2, [], 0, ["iced", "jam", "plain"], true) + " combos");
disp("pick 3 out of 10: " + pick(3, [], 0, "a123456789".split(''), false) + " combos");
</script></body></html></
{{out}}
<pre>iced iced
Line 1,578 ⟶ 2,041:
====Functional====
<
// n -> [a] -> [[a]]
Line 1,622 ⟶ 2,085:
];
})();</
{{Out}}
<syntaxhighlight lang="javascript">[
[["iced", "iced"], ["iced", "jam"], ["iced", "plain"],
["jam", "jam"], ["jam", "plain"], ["plain", "plain"]],
220
]</
===ES6===
{{Trans|Haskell}}
<
'use strict';
Line 1,695 ⟶ 2,158:
threeFromTen: length(combsWithRep(3, enumFromTo(0, 9)))
});
})();</
{{Out}}
<pre>{
Line 1,728 ⟶ 2,191:
=={{header|jq}}==
<
def pick(n; m): # pick n, from m onwards
if n == 0 then []
Line 1,735 ⟶ 2,198:
else ([.[m]] + pick(n-1; m)), pick(n; m+1)
end;
pick(n;0) ;</
'''The task''':
<
(["iced", "jam", "plain"] | pick(2)),
([[range(0;10)] | pick(3)] | length) as $n
| "There are \($n) ways to pick 3 objects with replacement from 10."
</syntaxhighlight>
{{Out}}
<pre>$ jq -n -r -c -f pick.jq
Line 1,756 ⟶ 2,219:
{{works with|Julia|0.6}}
<
l = ["iced", "jam", "plain"]
Line 1,764 ⟶ 2,227:
end
@show length(with_replacement_combinations(1:10, 3))</
{{out}}
Line 1,778 ⟶ 2,241:
=={{header|Kotlin}}==
<
class CombsWithReps<T>(val m: Int, val n: Int, val items: List<T>, val countOnly: Boolean = false) {
Line 1,814 ⟶ 2,277:
val generic10 = "0123456789".chunked(1)
CombsWithReps(3, 10, generic10, true)
}</
{{out}}
Line 1,836 ⟶ 2,299:
===With List Comprehension===
<
(defun combinations
(('() _)
Line 1,846 ⟶ 2,309:
(cons head subcoll))
(combinations tail n))))
</syntaxhighlight>
===With Map===
<
(defun combinations
(('() _)
Line 1,859 ⟶ 2,322:
(combinations coll (- n 1)))
(combinations tail n))))
</syntaxhighlight>
Output is the same for both:
<
> (combinations '(iced jam plain) 2)
((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))
</syntaxhighlight>
=={{header|Lobster}}==
{{trans|C}}
<
// set S of length n, choose k
Line 1,894 ⟶ 2,357:
print count
let extra = choose(map(10):_, 3): _
print extra</
{{out}}
<pre>["iced", "iced"]
Line 1,907 ⟶ 2,370:
=={{header|Lua}}==
<
if not nStartIndex then
nStartIndex = 1
Line 1,953 ⟶ 2,416:
end
end
</syntaxhighlight>
=={{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}}==
This method will only work for small set and sample sizes (as it generates all Tuples then filters duplicates - Length[Tuples[Range[10],10]] is already bigger than Mathematica can handle).
<
->{{"iced", "iced"}, {"iced", "jam"}, {"iced", "plain"}, {"jam", "jam"}, {"jam", "plain"}, {"plain", "plain"}}
Line 1,966 ⟶ 2,437:
Combi[10, 3]
->220
</syntaxhighlight>
A better method therefore:
<
occupation =
Flatten[Permutations /@
Line 1,984 ⟶ 2,455:
Out[2]= {{"iced", "iced"}, {"jam", "jam"}, {"plain",
"plain"}, {"iced", "jam"}, {"iced", "plain"}, {"jam", "plain"}}
</syntaxhighlight>
Which can handle the Length[S] = 10, k=10 situation in still only seconds.
Line 1,993 ⟶ 2,464:
comb.count_choices shows off solutions.aggregate (which allows you to fold over solutions as they're found) rather than list.length and the factorial function.
<
:- interface.
:- import_module list, int, bag.
Line 2,024 ⟶ 2,495:
:- pred count(T::in, int::in, int::out) is det.
count(_, N0, N) :- N0 + 1 = N.</
Usage:
<
:- interface.
:- import_module io.
Line 2,045 ⟶ 2,516:
mystery, cubed, cream_covered, explosive], 3, N),
io.write(L, !IO), io.nl(!IO),
io.write_string(from_int(N) ++ " choices.\n", !IO).</
{{out}}
Line 2,053 ⟶ 2,524:
=={{header|Nim}}==
{{trans|D}}
<
proc combsReps[T](lst: seq[T], k: int): seq[seq[T]] =
Line 2,062 ⟶ 2,533:
else:
lst.combsReps(k - 1).map((x: seq[T]) => lst[0] & x) &
lst[1 ..
echo(@["iced", "jam", "plain"].combsReps(2))
echo toSeq(1..10).combsReps(3).len</
{{out}}
<pre>@[@[iced, iced], @[iced, jam], @[iced, plain], @[jam, jam], @[jam, plain], @[plain, plain]]
Line 2,073 ⟶ 2,544:
{{trans|Haskell}}
<
match k, xxs with
| 0, _ -> [[]]
Line 2,079 ⟶ 2,550:
| k, x::xs ->
List.map (fun ys -> x::ys) (combs_with_rep (k-1) xxs)
@ combs_with_rep k xs</
in the interactive loop:
Line 2,095 ⟶ 2,566:
===Dynamic programming===
<
let arr = Array.make (m+1) [] in
arr.(0) <- [[]];
Line 2,103 ⟶ 2,574:
done
) xs;
arr.(m)</
in the interactive loop:
Line 2,118 ⟶ 2,589:
=={{header|PARI/GP}}==
<
if(k==0,return([]));
if(k==1,return(vector(#v,i,concat(s,[v[i]]))));
Line 2,126 ⟶ 2,597:
};
xc(k,v)=binomial(#v+k-1,k);
ways(2, ["iced","jam","plain"])</
=={{header|Pascal}}==
used in [[Munchausen_numbers]] or [[Own_digits_power_sum]]
<syntaxhighlight lang="pascal">program CombWithRep;
//combinations with repetitions
//Limit = count of elements
//Maxval = value of top , lowest is always 0
//so 0..Maxvalue => maxValue+1 elements
{$IFDEF FPC}
// {$R+,O+}
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$COPERATORS ON}
{$ELSE}{$APPTYPE CONSOLE}{$ENDIF}
uses
SysUtils;//GetTickCount64
var
CombIdx: array of byte;
function InitCombIdx(ElemCount: Int32): pbyte;
begin
setlength(CombIdx, ElemCount + 1);
Fillchar(CombIdx[0], sizeOf(CombIdx[0]) * (ElemCount + 1), #0);
Result := @CombIdx[0];
end;
function NextCombWithRep(pComb: pByte; MaxVal, ElemCount: UInt32): boolean;
var
i, dgt: NativeInt;
begin
i := -1;
repeat
i += 1;
dgt := pComb[i];
if dgt < MaxVal then
break;
until i > ElemCount;
Result := i >= ElemCount;
dgt +=1;
repeat
pComb[i] := dgt;
i -= 1;
until i < 0;
end;
procedure GetDoughnuts(ElemCount: NativeInt);
const
doughnuts: array[0..2] of string = ('iced', 'jam', 'plain');
var
pComb: pByte;
MaxVal, i: Uint32;
begin
if ElemCount < 1 then
EXIT;
MaxVal := High(doughnuts);
writeln('Getting ', ElemCount, ' elements of ', MaxVal + 1, ' different');
pComb := InitCombIdx(ElemCount);
repeat
Write('[');
for i := 0 to ElemCount - 2 do
Write(pComb[i], ',');
Write(pComb[ElemCount - 1], ']');
Write('{');
for i := 0 to ElemCount - 2 do
Write(doughnuts[pComb[i]], ',');
Write(doughnuts[pComb[ElemCount - 1]], '}');
until NextCombWithRep(pComb, MaxVal, ElemCount);
writeln(#10);
end;
procedure Check(ElemCount: Int32; ElemRange: Uint32);
var
pComb: pByte;
T0: int64;
rec_cnt: NativeInt;
begin
T0 := GetTickCount64;
rec_cnt := 0;
ElemRange -= 1;
pComb := InitCombIdx(ElemCount);
repeat
Inc(rec_cnt);
until NextCombWithRep(pComb, ElemRange, ElemCount);
T0 := GetTickCount64 - T0;
writeln('Getting ', ElemCount, ' elements of ', ElemRange + 1, ' different');
writeln(rec_cnt: 10, t0: 10,' ms');
end;
begin
GetDoughnuts(2);
GetDoughnuts(3);
Check(3, 10);
Check(9, 10);
Check(15, 16);
{$IFDEF WINDOWS}
readln;
{$ENDIF}
end.</syntaxhighlight>
{{out}}
<pre>
TIO.RUN
Getting 2 elements of 3 different
[0,0]{iced,iced}[1,0]{jam,iced}[2,0]{plain,iced}[1,1]{jam,jam}[2,1]{plain,jam}[2,2]{plain,plain}
Getting 3 elements of 3 different
[0,0,0]{iced,iced,iced}[1,0,0]{jam,iced,iced}[2,0,0]{plain,iced,iced}[1,1,0]{jam,jam,iced}[2,1,0]{plain,jam,iced}[2,2,0]{plain,plain,iced}[1,1,1]{jam,jam,jam}[2,1,1]{plain,jam,jam}[2,2,1]{plain,plain,jam}[2,2,2]{plain,plain,plain}
Getting 3 elements of 10 different
220 0 ms
Getting 9 elements of 10 different
48620 0 ms
Getting 15 elements of 16 different
155117520 735 ms
</pre>
=={{header|Perl}}==
The highly readable version:
<
sub f { $_[0] ? $_[0] * f($_[0] - 1) : 1 }
sub pn{ f($_[0] + $_[1] - 1) / f($_[0]) / f($_[1] - 1) }
Line 2,139 ⟶ 2,723:
printf "\nThere are %d ways to pick 7 out of 10\n", pn(7,10);
</syntaxhighlight>
Prints:
Line 2,152 ⟶ 2,736:
With a module:
<
my $iter = combinations_with_repetition([qw/iced jam plain/], 2);
while (my $p = $iter->next) {
Line 2,159 ⟶ 2,743:
# Not an efficient way: generates them all in an array!
my $count =()= combinations_with_repetition([1..10],7);
print "There are $count ways to pick 7 out of 10\n";</
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">show_choices</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">set</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">at</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">={})</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">n</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">res</span>
<span style="color: #008080;">else</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">at</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">set</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">show_choices</span><span style="color: #0000FF;">(</span><span style="color: #000000;">set</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">),</span><span style="color: #000000;">set</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">show_choices</span><span style="color: #0000FF;">({</span><span style="color: #008000;">"iced"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"jam"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"plain"</span><span style="color: #0000FF;">},</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 2,184 ⟶ 2,771:
The second part suggests enough differences (collecting and showing vs only counting) to strike me as ugly and confusing.
While I could easily, say, translate the C version, I'd rather forego the extra credit and use a completely different routine:
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">count_choices</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">set_size</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">at</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">taken</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">taken</span><span style="color: #0000FF;">=</span><span style="color: #000000;">n</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">taken</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">at</span> <span style="color: #008080;">to</span> <span style="color: #000000;">set_size</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">count_choices</span><span style="color: #0000FF;">(</span><span style="color: #000000;">set_size</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">taken</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">count</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">count_choices</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
220
</pre>
As of 1.0.2 there is a builtin combinations_with_repetitions() function. Using a string here for simplicity and neater output, but it works with any sequence:
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">combinations_with_repetitions</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"ijp"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">),</span><span style="color: #008000;">','</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">combinations_with_repetitions</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">),</span><span style="color: #000000;">3</span><span style="color: #0000FF;">))</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
"ii,ij,ip,jj,jp,pp"
220
</pre>
=={{header|PHP}}==
<
function combos($arr, $k) {
if ($k == 0) {
Line 2,232 ⟶ 2,832:
$num_donut_combos = count(combos($donuts, 3));
echo "$num_donut_combos ways to order 3 donuts given 10 types";
?></
{{out}} in the browser:
<pre>
Line 2,247 ⟶ 2,847:
You must set k n variables and fill arrays b and c.
<syntaxhighlight lang="php">
<?php
//Author Ivan Gavryushin @dcc0
Line 2,309 ⟶ 2,909:
?>
</syntaxhighlight>
=={{header|PicoLisp}}==
<
(cond
((=0 N) '(NIL))
Line 2,321 ⟶ 2,921:
'((X) (cons (car Lst) X))
(combrep (dec N) Lst) )
(combrep N (cdr Lst)) ) ) ) )</
{{out}}
<pre>: (combrep 2 '(iced jam plain))
Line 2,328 ⟶ 2,928:
: (length (combrep 3 (range 1 10)))
-> 220</pre>
=={{header|Prolog}}==
<syntaxhighlight lang="prolog">
combinations_of_length(_,[]).
combinations_of_length([X|T],[X|Combinations]):-
combinations_of_length([X|T],Combinations).
combinations_of_length([_|T],[X|Combinations]):-
combinations_of_length(T,[X|Combinations]).
</syntaxhighlight>
<pre>
?- [user].
|: combinations_of_length(_,[]).
|: combinations_of_length([X|T],[X|Combinations]):-
|: combinations_of_length([X|T],Combinations).
|: combinations_of_length([_|T],[X|Combinations]):-
|: combinations_of_length(T,[X|Combinations]).
|: ^D% user://1 compiled 0.01 sec, 3 clauses
true.
?- combinations_of_length([0,1,2,4],[L0, L1, L2, L3, L4, L5]).
L0 = L1, L1 = L2, L2 = L3, L3 = L4, L4 = L5, L5 = 0 ;
L0 = L1, L1 = L2, L2 = L3, L3 = L4, L4 = 0,
L5 = 1 ;
L0 = L1, L1 = L2, L2 = L3, L3 = L4, L4 = 0,
L5 = 2 ;
L0 = L1, L1 = L2, L2 = L3, L3 = L4, L4 = 0,
L5 = 4 ;
L0 = L1, L1 = L2, L2 = L3, L3 = 0,
L4 = L5, L5 = 1 ;
L0 = L1, L1 = L2, L2 = L3, L3 = 0,
L4 = 1,
L5 = 2 ;
L0 = L1, L1 = L2, L2 = L3, L3 = 0,
L4 = 1,
L5 = 4 ;
L0 = L1, L1 = L2, L2 = L3, L3 = 0,
L4 = L5, L5 = 2 ;
L0 = L1, L1 = L2, L2 = L3, L3 = 0,
L4 = 2,
.
.
.
</pre>
=={{header|PureBasic}}==
<
;combIndex() must be dimensioned to 'k' - 1, elementCount equals 'n' - 1
;combination produced includes repetition of elements and is represented by the array combIndex()
Line 2,398 ⟶ 3,041:
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
CloseConsole()
EndIf </
{{out}}
Line 2,411 ⟶ 3,054:
Ways to select 3 items from 10 types: 220</pre>
=={{header|Python}}==
<
>>> n, k = 'iced jam plain'.split(), 2
>>> list(combinations_with_replacement(n,k))
Line 2,420 ⟶ 3,065:
>>> len(list(combinations_with_replacement(range(10), 3)))
220
>>> </
'''References:'''
Line 2,430 ⟶ 3,075:
{{Trans|Haskell}}
{{Works with|Python|3.7}}
<
from itertools import (accumulate, chain, islice, repeat)
Line 2,493 ⟶ 3,138:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>[('iced', 'iced'), ('jam', 'iced'), ('jam', 'jam'), ('plain', 'iced'), ('plain', 'jam'), ('plain', 'plain')]
220</pre>
=={{header|Quackery}}==
Regarding the extra credit portion of the task, while this is clearly not the most efficient way of computing the number, it does serve to illustrate that, at the very least, the algorithm generates the correct number of choices, so I am content to comply with the specification rather than demonstrate a more efficient method.
"plaindrome" is ''not'' a typo. It is however, a neologism that appears to have little to no currency outside of The On-Line Encyclopedia of Integer Sequences.
<syntaxhighlight lang="quackery">( nextplain generates the next plaindrome in the
current base by adding one to a given plaindrome,
then replacing each trailing zero with the least
significant non-zero digit of the number
See: https://oeis.org/search?q=plaindromes
4 base put
-1
10 times
[ nextplain
dup echo sp ]
drop
base release
prints "0 1 2 3 11 12 13 22 23 33"
i.e. decimal "0 1 2 3 5 6 7 10 11 15"
Right padding the base 4 representations with
zeros gives all the combinations with repetitions
for selecting two doughnuts in a store selling
four types of doughnut, numbered 0, 1, 2, and 3.
00 01 02 03 11 12 13 22 23 33 )
[ 1+ dup 0 = if done
0 swap
[ base share /mod
dup 0 = while
drop dip 1+
again ]
swap rot 1+ times
[ base share * over + ]
nip ] is nextplain ( n --> n )
[ dup base put
swap ** 1 -
[] swap -1
[ 2dup > while
nextplain
rot over join
unrot
again ]
base release
2drop ] is kcombnums ( n n --> [ )
[ [] unrot times
[ base share /mod
rot join swap ]
drop ] is ndigits ( n n --> [ )
[ [] unrot
witheach
[ dip dup peek
nested rot swap join
swap ]
drop ] is [peek] ( [ [ --> [ )
[ dup temp put
size dup base put
dip dup kcombnums
[] unrot witheach
[ over ndigits
temp share swap [peek]
nested rot swap join
swap ]
temp release
base release
drop ] is kcombs ( n [ --> [ )
2
$ "jam iced plain" nest$
kcombs
witheach
[ witheach
[ echo$ sp ] cr ]
cr
3 10 kcombnums size echo</syntaxhighlight>
{{out}}
<pre>jam jam
iced jam
plain jam
iced iced
plain iced
plain plain
220
</pre>
=={{header|R}}==
The idiomatic solution is to just use a library.
<syntaxhighlight lang="rsplus">library(gtools)
combinations(3, 2, c("iced", "jam", "plain"), set = FALSE, repeats.allowed = TRUE)
nrow(combinations(10, 3, repeats.allowed = TRUE))</syntaxhighlight>
{{out}}
<pre>> combinations(3, 2, c("iced", "jam", "plain"), set = FALSE, repeats.allowed = TRUE)
[,1] [,2]
[1,] "iced" "iced"
[2,] "iced" "jam"
[3,] "iced" "plain"
[4,] "jam" "jam"
[5,] "jam" "plain"
[6,] "plain" "plain"
> nrow(combinations(10, 3, repeats.allowed = TRUE))
[1] 220</pre>
=={{header|Racket}}==
<
#lang racket
(define (combinations xs k)
Line 2,507 ⟶ 3,266:
(map (λ(x) (cons (first xs) x))
(combinations xs (- k 1))))]))
</syntaxhighlight>
=={{header|Raku}}==
Line 2,515 ⟶ 3,274:
{{works with|Rakudo|2016.07}}
<syntaxhighlight lang="raku"
my $k = 2;
.put for [X](@S xx $k).unique(as => *.sort.cache, with => &[eqv])</
{{out}}
Line 2,533 ⟶ 3,292:
{{trans|Haskell}}
<syntaxhighlight lang="raku"
multi combs_with_rep (0, @) { () }
Line 2,549 ⟶ 3,308:
sub combs_with_rep_count ($k, $n) { ($n + $k - 1)! / $k! / ($n - 1)! }
say combs_with_rep_count( 3, 10 );</
{{out}}
<pre>(iced iced)
Line 2,562 ⟶ 3,321:
===version 1===
This REXX version uses a type of anonymous recursion.
<
call RcombN 3, 2, 'iced jam plain' /*The 1st part of Rosetta Code task. */
call RcombN -10, 3, 'Iced jam plain' /* " 2nd " " " " " */
Line 2,581 ⟶ 3,340:
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</
{{out|output}}
<pre>
Line 2,601 ⟶ 3,360:
recursive (taken from version 1)
Reformatted and variable names suitable for OoRexx.
<
debug=0
Call time 'R'
Line 2,666 ⟶ 3,425:
Say l
End
Return</
{{out}}
<pre>----------- 3 doughnut selection taken 2 at a time:
Line 2,689 ⟶ 3,448:
===version 3===
iterative (transformed from version 1)
<
Numeric Digits 20
debug=0
Line 2,743 ⟶ 3,502:
Say l
End
Return</
{{out}}
Line 2,764 ⟶ 3,523:
=={{header|Ring}}==
<
# Project : Combinations with repetitions
Line 2,828 ⟶ 3,587:
next
return aList
</syntaxhighlight>
Output:
<pre>
Line 2,843 ⟶ 3,602:
=={{header|Ruby}}==
{{works with|Ruby|2.0}}
<
puts "There are #{possible_doughnuts.count} possible doughnuts:"
possible_doughnuts.each{|doughnut_combi| puts doughnut_combi.join(' and ')}
# Extra credit
possible_doughnuts = [*1..
# size returns the size of the enumerator, or nil if it can’t be calculated lazily.
puts "", "#{possible_doughnuts.size} ways to order
</syntaxhighlight>
{{out}}
<pre>
Line 2,861 ⟶ 3,621:
plain and plain
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">
// Iterator for the combinations of `arr` with `k` elements with repetitions.
// Yields the combinations in lexicographical order.
struct CombinationsWithRepetitions<'a, T: 'a> {
// source array to get combinations from
arr: &'a [T],
// length of the combinations
k: u32,
// current counts of each object that represent the next combination
counts: Vec<u32>,
// whether there are any combinations left
remaining: bool,
}
impl<'a, T> CombinationsWithRepetitions<'a, T> {
fn new(arr: &[T], k: u32) -> CombinationsWithRepetitions<T> {
let mut counts = vec![0; arr.len()];
counts[arr.len() - 1] = k;
CombinationsWithRepetitions {
arr,
k,
counts,
remaining: true,
}
}
}
impl<'a, T> Iterator for CombinationsWithRepetitions<'a, T> {
type Item = Vec<&'a T>;
fn next(&mut self) -> Option<Vec<&'a T>> {
if !self.remaining {
return None;
}
let mut comb = Vec::new();
for (count, item) in self.counts.iter().zip(self.arr.iter()) {
for _ in 0..*count {
comb.push(item);
}
}
// this is lexicographically largest, and thus the last combination
if self.counts[0] == self.k {
self.remaining = false;
} else {
let n = self.counts.len();
for i in (1..n).rev() {
if self.counts[i] > 0 {
let original_value = self.counts[i];
self.counts[i - 1] += 1;
for j in i..(n - 1) {
self.counts[j] = 0;
}
self.counts[n - 1] = original_value - 1;
break;
}
}
}
Some(comb)
}
}
fn main() {
let collection = vec!["iced", "jam", "plain"];
for comb in CombinationsWithRepetitions::new(&collection, 2) {
for item in &comb {
print!("{} ", item)
}
println!()
}
}
</syntaxhighlight>
{{out}}
<pre>
plain plain
jam plain
jam jam
iced plain
iced jam
iced iced
</pre>
=={{header|Scala}}==
Scala has a combinations method in the standard library.
<
object CombinationsWithRepetition {
Line 2,880 ⟶ 3,723:
}
}
</syntaxhighlight>
{{out}}
Line 2,894 ⟶ 3,737:
=={{header|Scheme}}==
{{trans|PicoLisp}}
<
(cond ((= k 0) '(()))
((null? lst) '())
Line 2,906 ⟶ 3,749:
(display (combs-with-rep 2 (list "iced" "jam" "plain"))) (newline)
(display (length (combs-with-rep 3 '(1 2 3 4 5 6 7 8 9 10)))) (newline)</
{{out}}
<pre>
Line 2,914 ⟶ 3,757:
===Dynamic programming===
<
(define arr (make-vector (+ m 1) '()))
(vector-set! arr 0 '(()))
Line 2,928 ⟶ 3,771:
(display (combs-with-rep 2 (list "iced" "jam" "plain"))) (newline)
(display (length (combs-with-rep 3 '(1 2 3 4 5 6 7 8 9 10)))) (newline)</
{{out}}
<pre>
Line 2,937 ⟶ 3,780:
=={{header|Sidef}}==
{{trans|Perl}}
<
n>0 ? (^l -> map {|k| __FUNC__(n-1, l.slice(k), [a..., l[k]]) }) : a
}
Line 2,943 ⟶ 3,786:
cwr(2, %w(iced jam plain)).each {|a|
say a.map{ .join(' ') }.join("\n")
}</
Also built-in:
<
say a.join(' ')
})</
{{out}}
Line 2,962 ⟶ 3,805:
Efficient count of the total number of combinations with repetition:
<
printf("\nThere are %s ways to pick 7 out of 10 with repetition\n", cwr_count(10, 7))</
{{out}}
<pre>
Line 2,972 ⟶ 3,815:
{{trans|Haskell}}
<
match k, xxs with
| 0, _ -> [[]]
Line 2,978 ⟶ 3,821:
| k, x::xs ->
List.map (fun ys -> x::ys) (combs_with_rep (k-1) xxs)
@ combs_with_rep k xs</
in the interactive loop:
Line 2,993 ⟶ 3,836:
===Dynamic programming===
<
val arr = Array.array (m+1, [])
in
Line 3,003 ⟶ 3,846:
) xs;
Array.sub (arr, m)
end</
in the interactive loop:
Line 3,018 ⟶ 3,861:
=={{header|Stata}}==
<
n = cols(v)
a = J(comb(n+k-1,k),k,v[1])
Line 3,036 ⟶ 3,879:
a = combrep(1..10,3)
rows(a)</
'''Output'''
Line 3,053 ⟶ 3,896:
=={{header|Swift}}==
<
if n == 0 { return [[]] } else {
var combos = [[T]]()
Line 3,063 ⟶ 3,906:
}
}
print(combosWithRep(["iced", "jam", "plain"], n: 2).map {$0.joinWithSeparator(" and ")}.joinWithSeparator("\n"))</
Output:
<pre>plain and plain
Line 3,073 ⟶ 3,916:
=={{header|Tcl}}==
<
proc combrepl {set n {presorted no}} {
if {!$presorted} {
Line 3,095 ⟶ 3,938:
puts [combrepl {iced jam plain} 2]
puts [llength [combrepl {1 2 3 4 5 6 7 8 9 10} 3]]</
{{out}}
<pre>
Line 3,103 ⟶ 3,946:
=={{header|TXR}}==
<
{{out}}
<pre>
Line 3,109 ⟶ 3,952:
</pre>
----
<
{{out}}
<pre>
Line 3,116 ⟶ 3,959:
=={{header|Ursala}}==
<
#import nat
Line 3,123 ⟶ 3,966:
#cast %gLSnX
main = ^|(~&,length) cwr~~/(<'iced','jam','plain'>,2) ('1234567890',3)</
{{out}}
<pre>
Line 3,135 ⟶ 3,978:
<'plain','plain'>},
220)
</pre>
=={{header|VBScript}}==
<syntaxhighlight lang="vb">' Combinations with repetitions - iterative - VBScript
Sub printc(vi,n,vs)
Dim i, w
For i=0 To n-1
w=w &" "& vs(vi(i))
Next 'i
Wscript.Echo w
End Sub
Sub combine(flavors, draws, xitem, tell)
Dim n, i, j
ReDim v(draws)
If tell Then Wscript.Echo "list of cwr("& flavors &","& draws &") :"
Do While True
For i=0 To draws-1
If v(i)>flavors-1 Then
v(i+1)=v(i+1)+1
For j=i To 0 Step -1
v(j)=v(i+1)
Next 'j
End If
Next 'i
If v(draws)>0 Then Exit Do
n=n+1
If tell Then Call printc(v, draws, xitem)
v(0)=v(0)+1
Loop
Wscript.Echo "cwr("& flavors &","& draws &")="&n
End Sub
items=Array( "iced", "jam", "plain" )
combine 3, 2, items, True
combine 10, 3, , False
combine 10, 7, , False
combine 10, 9, , False </syntaxhighlight>
{{out}}
<pre>
list of cwr(3,2) :
iced iced
jam iced
plain iced
jam jam
plain jam
plain plain
cwr(3,2)=6
cwr(10,3)=220
cwr(10,7)=11440
cwr(10,9)=48620
</pre>
=={{header|Wren}}==
===Concise recursive===
{{trans|Go}}
Produces results in no particular order.
<syntaxhighlight lang="wren">var Combrep = Fn.new { |n, lst|
if (n == 0 ) return [[]]
if (lst.count == 0) return []
var r = Combrep.call(n, lst[1..-1])
for (x in Combrep.call(n-1, lst)) {
var y = x.toList
y.add(lst[0])
r.add(y)
}
return r
}
System.print(Combrep.call(2, ["iced", "jam", "plain"]))
System.print(Combrep.call(3, (1..10).toList).count)</syntaxhighlight>
{{out}}
<pre>
[[plain, plain], [plain, jam], [jam, jam], [plain, iced], [jam, iced], [iced, iced]]
220
</pre>
===Library based===
{{libheader|Wren-seq}}
{{libheader|Wren-perm}}
Produces results in lexicographic order.
<syntaxhighlight lang="wren">import "./seq" for Lst
import "./perm" for Comb
var a = ["iced", "jam", "plain"]
a = Lst.flatten(Lst.zip(a, a))
System.print(Comb.listDistinct(a, 2))
a = (1..10).toList
a = Lst.flatten(Lst.zip(Lst.zip(a, a), a))
System.print(Comb.listDistinct(a, 3).count)</syntaxhighlight>
{{out}}
<pre>
[[iced, iced], [iced, jam], [iced, plain], [jam, jam], [jam, plain], [plain, plain]]
220
</pre>
=={{header|XPL0}}==
<
int Count, Array(10);
Line 3,165 ⟶ 4,106:
Combos(0, 0, 3, 10, [0]);
Text(0, "Combos = "); IntOut(0, Count); CrLf(0);
]</
{{out}}
Line 3,181 ⟶ 4,122:
=={{header|zkl}}==
{{trans|Clojure}}
<
if (k==1) return(seq);
if (not seq) return(T);
self.fcn(k-1,seq).apply(T.extend.fp(seq[0])).extend(self.fcn(k,seq[1,*]));
}</
<
combosK(3,T(0,1,2,3,4,5,6,7,8,9)).len();</
{{out}}
<pre>
Line 3,195 ⟶ 4,136:
=={{header|ZX Spectrum Basic}}==
<
20 DIM d$(n,5)
30 FOR i=1 TO n
Line 3,205 ⟶ 4,146:
90 PRINT d$(i);" ";d$(j)
100 NEXT j
110 NEXT i</
|