Anonymous user
Combinations with repetitions: Difference between revisions
m
{{out}}
m (→{{header|REXX}}: removed OVERFLOW from PRE html tag.) |
m ({{out}}) |
||
Line 1:
{{task|Discrete math}}
The set of combinations with repetitions is computed from a set, <math>S</math> (of cardinality <math>n</math>), and a size of resulting selection, <math>k</math>, by reporting the sets of cardinality <math>k</math> where each member of those sets is chosen from <math>S</math>.
In the real world, it is about choosing sets where there is a “large” supply of each type of element and where the order of choice does not matter.
For example:
:Q: How many ways can a person choose two doughnuts from a store selling three types of doughnut: iced, jam, and plain? (i.e., <math>S</math> is <math>\{\mathrm{iced}, \mathrm{jam}, \mathrm{plain}\}</math>, <math>|S| = 3</math>, and <math>k = 2</math>.)
Line 86 ⟶ 88:
end Combinations;</lang>
{{out}}
<pre>ICED+ICED
ICED+JAM
Line 125 ⟶ 127:
NEXT
= c%</lang>
{{out}}
<pre>
Choices of 2 from 3:
Line 161 ⟶ 163:
& out$(choices$(3.iced jam plain butter marmite tahin fish salad onion grass):?+[?N&!N)
);</lang>
{{out}}
<pre>iced^2+jam^2+plain^2+iced*jam+iced*plain+jam*plain
220</pre>
Line 177 ⟶ 179:
</lang>
{{out}}
<pre>
user> (combinations '[iced jam plain] 2)
((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))
</
=={{header|C}}==
Line 217 ⟶ 218:
return 0;
}
</lang>
iced jam
iced plain
Line 282 ⟶ 284:
end program main
</lang>
{{out}}
<pre>
iced iced
Line 309 ⟶ 311:
</lang>
{{out}}
<
jam,plain:
[ [ 'iced', 'iced' ],
Line 319 ⟶ 321:
[ 'plain', 'plain' ] ]
220 ways to order 3 donuts given 10 types
</
=={{header|D}}==
Line 450 ⟶ 452:
(test (comb/rep 2 {"iced" "jam" "plain"}))
</lang>
{{out}}
<pre>
{[|"iced" "iced"|] [|"iced" "jam"|] [|"jam" "jam"|] [|"iced" "plain"|] [|"jam" "plain"|] [|"plain" "plain"|]}
</
=={{header|Erlang}}==
Line 467 ⟶ 469:
[[H|L] || L <- comb_rep(N-1,S)]++comb_rep(N,T).
</lang>
{{out}}
<pre>
94> comb:comb_rep(2,[iced,jam,plain]).
[[iced,iced],
Line 478 ⟶ 480:
95> length(comb:comb_rep(3,lists:seq(1,10))).
220
</
=={{header|GAP}}==
<lang gap># Built-in
Line 508 ⟶ 511:
[]string{"1", "2", "3", "4", "5", "6", "7", "8", "9", "10"})))
}</lang>
{{out}}
<pre>
[[plain plain] [plain jam] [jam jam] [plain iced] [jam iced] [iced iced]]
220
</pre>
===Channel===
Using channel and goroutine, showing how to use synced or unsynced communication.
Line 573 ⟶ 577:
fmt.Printf("\npicking 3 of 10: %d\n", count)
}</lang>
{{out}}
<pre>
plain plain
Line 595 ⟶ 599:
// Go maps are an easy representation for sets as long as the element type
// of the set is valid as a key type for maps. Strings are easy.
// We follow the convention of always storing true for the value.
type set map[string]bool
// Multisets of strings are easy in the same way.
// We store the multiplicity of the element as the value.
type multiset map[string]int
Line 688 ⟶ 692:
fmt.Println(len(combrep(3, ten)))
}</lang>
{{out}}
<pre>
map[plain:1 jam:1]
Line 784 ⟶ 788:
</lang>
{{out}}
<pre>
plain plain
Line 900 ⟶ 904:
</lang>
{{out}}
<pre>
iced iced
Line 935 ⟶ 939:
disp(pick(2, [], 0, ["iced", "jam", "plain"], true) + " combos");
disp("pick 3 out of 10: " + pick(3, [], 0, "a123456789".split(''), false) + " combos");
</script></body></html></lang>
{{out}}
<pre>iced iced
iced jam
iced plain
Line 942 ⟶ 948:
plain plain
6 combos
pick 3 out of 10: 220 combos</
=={{header|jq}}==
<lang jq>def pick(n):
Line 959 ⟶ 966:
</lang>
{{Out}}
<
Pick 2:
["iced","iced"]
Line 967 ⟶ 974:
["jam","plain"]
["plain","plain"]
There are 220 ways to pick 3 objects with replacement from 10.</
=={{header|Lua}}==
Line 1,110 ⟶ 1,117:
io.write_string(from_int(N) ++ " choices.\n", !IO).</lang>
{{out}}
<pre>[[iced, iced], [jam, jam], [plain, plain], [iced, jam], [iced, plain], [jam, plain]]
220 choices.</pre>
Line 1,130 ⟶ 1,136:
echo(@["iced", "jam", "plain"].combsReps(2))
echo toSeq(1..10).combsReps(3).len</lang>
{{out}}
<pre>@[@[iced, iced], @[iced, jam], @[iced, plain], @[jam, jam], @[jam, plain], @[plain, plain]]
220</pre>
Line 1,244 ⟶ 1,250:
say combs_with_rep_count( 3, 10 );</lang>
{{out}}
▲Output:<pre>["iced", "iced"]
<pre>["iced", "iced"]
["iced", "jam"]
["iced", "plain"]
Line 1,285 ⟶ 1,292:
echo "$num_donut_combos ways to order 3 donuts given 10 types";
?></lang>
<
iced iced
iced jam
Line 1,294 ⟶ 1,301:
plain plain
220 ways to order 3 donuts given 10 types
</
=={{header|PicoLisp}}==
Line 1,307 ⟶ 1,314:
(combrep (dec N) Lst) )
(combrep N (cdr Lst)) ) ) ) )</lang>
{{out}}
<pre>: (combrep 2 '(iced jam plain))
-> ((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))
Line 1,385 ⟶ 1,392:
EndIf </lang>The nextCombination() procedure operates on an array of indexes to produce the next combination. This generalization allows producing a combination from any collection of elements. nextCombination() returns the value #False when the indexes have reach their maximum values and are then reset.
{{out}}
<pre>Combinations of 2 dougnuts taken 3 at a time with repetitions.
iced + iced
Line 1,452 ⟶ 1,459:
end /*u*/
return 0</lang>
<pre>
──────────── 3 doughnut selection taken 2 at a time:
Line 1,507 ⟶ 1,514:
</lang>
{{out}}
<pre>
iced,iced
Line 1,631 ⟶ 1,638:
puts [combrepl {iced jam plain} 2]
puts [llength [combrepl {1 2 3 4 5 6 7 8 9 10} 3]]</lang>
{{out}}
<pre>
{iced iced} {iced jam} {iced plain} {jam jam} {jam plain} {plain plain}
Line 1,646 ⟶ 1,653:
main = ^|(~&,length) cwr~~/(<'iced','jam','plain'>,2) ('1234567890',3)</lang>
{{out}}
<pre>
(
Line 1,689 ⟶ 1,696:
]</lang>
{{out}}
<pre>
iced iced
| |||