How many Beggar-my-neighbour possible games are there?
There are 5 types of card: a, b, c, d, e.
In a bundle of 52 cards there are 4 cards of type a, 4 of type b, 4 of type c, 4 of type d and 36 of type e.
I'd like to know the number of permutations of the following array and how I can get through all of the permutations using an algorithm:
$$\underbrace{\text{a a a a b b b b c c c c d d d d e e e . . . e}}_{\text{52 cards in all}}$$
Obviously all the elements with the same name are interchangable.
$ \quad$
$ \quad$
I'm programming a C++ program that looks for infinite games. The game logic already works (I've compared five real games with five computer ones and the results were right). But now it only resolves a game at a time, and I have to manually give it the deck of cards. So I need an algorithm that goes through all of the possible games and tests them. (Even if $6.54\cdot10^{20}$ is really big)
By now I thought of this:
Divide the problem into simpler ones: first I choose the position for the a's (in 52 places), then for the b's (in 48 places), then for the c's (in 44 places), and at the end I choose the position for the d's (in 40 places).
Every time I call a function named, let's say,
next_permutation(), I advance to the next possible places for d. When I got through all d's permutations I advance to the next c possible places. The same goes for b's and then a's.Store 4 numbers nA, nB, nC, nD. Every number represents the current permutation of the letters (as I said above). When I reach the maximum number of d's ${52 \choose 4}$ I increase nC by 1 and reset nD to 0. When I reach the maximum number of c's ${48 \choose 4}$ I increase nB by 1 and reset both nC and nD to 0. When I reach the maximum number of b's ${44 \choose 4}$ I increase nA by 1 and reset nB, nC and nD to 0.
So I only have to figure out how to go through all of the possible combinations of 4 cards of the same type in a deck of 52, 48, 44 and 40 cards.
There are $52 \choose 4$ ways to choose where the a's go.
There are then $48 \choose 4$ ways to choose where the b's go.
There are then $44 \choose 4$ ways to choose where the c's go.
There are then $40 \choose 4$ ways to choose where the d's go.
That leaves the rest of the $36$ slots to put the e's.
The number of ways to arrange these is then
$${52 \choose 4}\cdot{48 \choose 4}\cdot{44 \choose 4}\cdot{40 \choose 4}\approx6.54\cdot10^{20}$$