Combinations with repetitions: Difference between revisions

Line 1:

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:~~

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:

Line 88:

end Combinations;</lang>

Output:

<pre>ICED+ICED

ICED+JAM

Line 125:

Line 127:

= c%</lang>

'''Output:'''

<pre>

Choices of 2 from 3:

Line 161:

Line 163:

& out$(choices$(3.iced jam plain butter marmite tahin fish salad onion grass):?+[?N&!N)

);</lang>

Output:

<pre>iced^2+jam^2+plain^2+iced*jam+iced*plain+jam*plain

220</pre>

Line 177:

Line 179:

</lang>

Example output:

<pre>

user> (combinations '[iced jam plain] 2)

((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))

</~~lang~~>

</pre>

=={{header|C}}==

Line 217:

Line 218:

return 0;

}

</lang>~~Output:<pre>iced iced~~

</lang>

⚫

{{out}}<pre>iced iced

iced jam

iced plain

Line 282:

Line 284:

end program main

</lang>

Output:

<pre>

iced iced

Line 309:

Line 311:

</lang>

output

<~~lang~~>

<pre>

jam,plain:

[ [ 'iced', 'iced' ],

Line 319:

Line 321:

[ 'plain', 'plain' ] ]

220 ways to order 3 donuts given 10 types

</~~lang~~>

</pre>

=={{header|D}}==

Line 450:

Line 452:

(test (comb/rep 2 {"iced" "jam" "plain"}))

</lang>

'''Output:'''

<pre>

{[|"iced" "iced"|] [|"iced" "jam"|] [|"jam" "jam"|] [|"iced" "plain"|] [|"jam" "plain"|] [|"plain" "plain"|]}

</~~lang~~>

</pre>

=={{header|Erlang}}==

Line 467:

Line 469:

[[H|L] || L <- comb_rep(N-1,S)]++comb_rep(N,T).

</lang>

Output:

<pre>

94> comb:comb_rep(2,[iced,jam,plain]).

[[iced,iced],

Line 478:

Line 480:

95> length(comb:comb_rep(3,lists:seq(1,10))).

220

</~~lang~~>

</pre>

=={{header|GAP}}==

<lang gap># Built-in

Line 508:

Line 511:

[]string{"1", "2", "3", "4", "5", "6", "7", "8", "9", "10"})))

}</lang>

Output:

<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:

Line 577:

fmt.Printf("\npicking 3 of 10: %d\n", count)

}</lang>

Output:

<pre>

plain plain

Line 595:

Line 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~~

// of the set is valid as a key type for maps. Strings are easy.

// the convention of always storing true for the value.

// 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~~

// Multisets of strings are easy in the same way.

// of the element as the value.

// We store the multiplicity of the element as the value.

type multiset map[string]int

Line 688:

Line 692:

fmt.Println(len(combrep(3, ten)))

}</lang>

Output:

<pre>

map[plain:1 jam:1]

Line 784:

Line 788:

</lang>

Output:

<pre>

plain plain

Line 900:

Line 904:

</lang>

Output:

<pre>

iced iced

Line 935:

Line 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>~~output<lang>iced iced~~

</script></body></html></lang>

<pre>iced iced

iced jam

iced plain

Line 942:

Line 948:

plain plain

6 combos

pick 3 out of 10: 220 combos</~~lang~~>

pick 3 out of 10: 220 combos</pre>

=={{header|jq}}==

<lang jq>def pick(n):

Line 959:

Line 966:

</lang>

<~~lang sh~~>$ jq -n -r -c -f pick.jq

<pre>$ jq -n -r -c -f pick.jq

Pick 2:

["iced","iced"]

Line 967:

Line 974:

["jam","plain"]

["plain","plain"]

There are 220 ways to pick 3 objects with replacement from 10.</~~lang~~>

There are 220 ways to pick 3 objects with replacement from 10.</pre>

=={{header|Lua}}==

Line 1,110:

Line 1,117:

io.write_string(from_int(N) ++ " choices.\n", !IO).</lang>

Output:

<pre>[[iced, iced], [jam, jam], [plain, plain], [iced, jam], [iced, plain], [jam, plain]]

220 choices.</pre>

Line 1,130:

Line 1,136:

echo(@["iced", "jam", "plain"].combsReps(2))

echo toSeq(1..10).combsReps(3).len</lang>

Output:

<pre>@[@[iced, iced], @[iced, jam], @[iced, plain], @[jam, jam], @[jam, plain], @[plain, plain]]

220</pre>

Line 1,244:

Line 1,250:

say combs_with_rep_count( 3, 10 );</lang>

⚫

~~Output:~~<pre>["iced", "iced"]

<pre>["iced", "iced"]

["iced", "jam"]

["iced", "plain"]

Line 1,285:

Line 1,292:

echo "$num_donut_combos ways to order 3 donuts given 10 types";

?></lang>

~~output~~ in the browser:

{{out}} in the browser:

<~~lang~~>

<pre>

iced iced

iced jam

Line 1,294:

Line 1,301:

plain plain

220 ways to order 3 donuts given 10 types

</~~lang~~>

</pre>

=={{header|PicoLisp}}==

Line 1,307:

Line 1,314:

(combrep (dec N) Lst) )

(combrep N (cdr Lst)) ) ) ) )</lang>

Output:

<pre>: (combrep 2 '(iced jam plain))

-> ((iced iced) (iced jam) (iced plain) (jam jam) (jam plain) (plain plain))

Line 1,385:

Line 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.

Sample output:

<pre>Combinations of 2 dougnuts taken 3 at a time with repetitions.

iced + iced

Line 1,452:

Line 1,459:

end /*u*/

return 0</lang>

~~'''output'''~~ using the defaults for input:

{{out}} using the defaults for input:

<pre>

──────────── 3 doughnut selection taken 2 at a time:

Line 1,507:

Line 1,514:

</lang>

'''Output'''

<pre>

iced,iced

Line 1,631:

Line 1,638:

puts [combrepl {iced jam plain} 2]

puts [llength [combrepl {1 2 3 4 5 6 7 8 9 10} 3]]</lang>

Output:

<pre>

{iced iced} {iced jam} {iced plain} {jam jam} {jam plain} {plain plain}

Line 1,646:

Line 1,653:

main = ^|(~&,length) cwr~~/(<'iced','jam','plain'>,2) ('1234567890',3)</lang>

output:

<pre>

(

Line 1,689:

Line 1,696:

]</lang>

Output:

<pre>

iced iced