Iterator - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Combinatorics : Iterator : Iterator/MultiCombination

Iterator

  

MultiCombination

  

generate multicombinations

 

Calling Sequence

Parameters

Options

Description

Examples

References

Compatibility

Calling Sequence

MultiCombination(M, t, opts)

Parameters

M

-

list(posint); numbers of distinct elements

t

-

nonnegint; size of combinations

opts

-

(optional) equation(s) of the form option = value; specify options for the MultiCombination command

Options

• 

compile = truefalse

  

True means compile the iterator. The default is true.

Description

• 

The MultiCombination command returns an iterator that generates all t-combinations chosen from a multiset.

• 

The M parameter specifies the multiset. It is a list of integers, m1,m2,,mn, with mk the multiplicity of the k-th element.

• 

The t parameter is the number of items to choose.

• 

The output of each iteration is an Array of t positive integers. An integer k represents a selection of the k-th element.

• 

There is an isomorphism between multicombinations and bounded-compositions. This object uses the same algorithm as BoundedComposition but transforms the output.

Methods

The iterator object has the following methods. The self parameter is the iterator object.

• 

Number(self): return the number of iterations required to step through the iterator, assuming it started at rank one.

Examples

withIterator:

Construct an iterator corresponding to the number of ways to choose 5 balls from a bucket with 2 red balls, 5 green balls, and 3 black balls.

BMultiCombination2,5,3,5:

Print each combination. The 1s correspond to red balls, the 2s to green balls, and the 3s to black balls.

forbinBdoprintf%d\n,benddo:

1 1 2 2 2
1 2 2 2 2
2 2 2 2 2
1 1 2 2 3
1 2 2 2 3
2 2 2 2 3
1 1 2 3 3
1 2 2 3 3
2 2 2 3 3
1 1 3 3 3
1 2 3 3 3
2 2 3 3 3

Compute the number of ways to select four entrees from a menu of 10 dishes allowing multiple selections of any of the entrees. Because four is the most that can be selected, this is equivalent to assigning four as the multiplicity of all items.

NumberMultiCombination`$`4,10,4

715

(1)

Suppose one is allowed to choose any entree no more than twice. This can be expressed as

MMultiCombination`$`2,10,4:

There are 615 ways to obtain such a combination.

NumberM

615

(2)

Number of Distinct Ranks of a Poker Hand

• 

A standard poker hand consists of five cards drawn from a 52 card deck, with four suits of 13 cards per suit.

• 

The rank of a hand depends first on its category (straight flush, four of a kind, etc.), then on its rank within that category. The rank does not depend on the suits, with the exception that a flush (all five cards of the same suit) is a separate category.

• 

The number of distinct hand ranks equals the number of possible flushes of a given suit plus the number of multicombinations of five cards from a deck with four cards of each rank.

• 

The number of possible flushes of a given suit is simply the number of ways to choose a set of five objects from a set of thirteen distinct objects. The binomial function computes the result, 135. It can also be computed using the Number method of the Combination object:

numFNumberCombination13,5

numF1287

(3)
• 

Construct an iterator that generates each of the multcombinations of five cards drawn from a deck.

HMultiCombination`$`4,13,5:

• 

Count the number of multicombinations. We can do this in a number of ways; one is simply to invoke the Number method.

numHNumberH

numH6175

(4)
• 

For this case, it is also practical to count the iterations one by one.

numHadd1,h=H

numH6175

(5)
• 

A final method is the following. If there were five of each ranked card, rather than four, we would obtain exactly 13 more distinct ranked hands then the actual deck (the 13 five of a kind). This is expressed by the following formula:

numHNumberMultiCombination`$`5,13,513

numH6175

(6)
• 

The total number of distinct ranks of poker hands is

numF+numH

7462

(7)

References

  

Knuth, Donald Ervin. The Art of Computer Programming, volume 4, fascicle 3; generating all combinations and partitions,sec. 7.2.1.3, exercise 60, p. 30, and answers, algorithm Q, pp. 98-99.

Compatibility

• 

The Number method was updated in Maple 2020.

• 

The Iterator[MultiCombination] command was introduced in Maple 2016.

• 

For more information on Maple 2016 changes, see Updates in Maple 2016.

See Also

combinat[choose]

Iterator

Iterator[BoundedComposition]