3
$\begingroup$

Imagine I have 4 letters. Is there some algorithm that produces
"abcd" -> 1
"bacd" -> 2
"bcad" -> 3
... etc
without finding and numbering every single combination? My goal is to get a number from 1 to 52! from a shuffled deck of cards. It's impractical to find and number all 52! combinations, so I need a way that doesn't require that. The order that the numbers appear in doesn't matter, as long as numbers don't repeat and there are no gaps.

$\endgroup$
  • $\begingroup$ I guess you mean permutation, i.e. a specific ordering of all the cards? $\endgroup$ – JiK Jan 29 '14 at 21:54
  • $\begingroup$ Are you looking to use this number to shuffle the deck or is the deck already shuffled and you want the number to record the current state? $\endgroup$ – John Habert Jan 29 '14 at 21:54
  • $\begingroup$ @JiK: Yes, that's what I mean. $\endgroup$ – Daffy Jan 29 '14 at 21:55
  • $\begingroup$ @JohnHabert: The latter. I intend to use the current state of the deck to generate random numbers. I assume the method used to get a number from the deck could be reversed to get a deck from a number. $\endgroup$ – Daffy Jan 29 '14 at 21:56
  • $\begingroup$ This is discussed exhaustively in Donald E. Knuth The Art of Computer Programming volume 4, and less exhaustively but still enough to solve the problem in section 4.3.1 of Higher-Order Perl, which is available online for free. $\endgroup$ – MJD Jan 29 '14 at 22:06
2
$\begingroup$

You can first number all the cards, so that

Aclubs -> 0
2clubs -> 1
...
Kspades -> 51

I'm going to do the simpler case, where you have just four cards, A,B,C,D, which I'll number 0, 1, 2, and 3.

Suppose that you have DACB. Here's how I'll assign a number. It's ugly, but it'll work:

D --> 3 --> 3! * 3 = 18
A --> 0 --> 2! * 0 =  0
C --> 1 --> 1! * 1 =  1
B --> 0 --> 0! * 0 =  0
Total:               19

Now you may notice that the numbers to the right of the letters aren't the numbers I said. They are for D and A, but not the last two. Let me explain:

  • The first number gets its true label.

  • The second number gets its true label, minus however many items below it have been used already.

  • Same for the third number and fourth number.

It helps if you keep a list of the available numbers:

D --> 3 --> 3! * 3 = 18  ABCD available; D is number 3 (starting from 0)
A --> 0 --> 2! * 0 =  0  ABC  available; A is number 0
C --> 1 --> 1! * 1 =  1  BC available; C is number 1
B --> 0 --> 0! * 0 =  0  B available; B is number 0
Total:               19

This will assign a different number to every possible permutation.

"How do you go the other way?" you might ask. You use integer division and remainders, and reverse the process. In what follows, DIV and REM denote those two things:

Code: 19

19 DIV 3! --> 3 REM 1;  (3, ABCD) --> D
 1 DIV 2! --> 0 REM 1;  (0, ABC)  --> A
 1 DIV 1! --> 1 REM 0;  (1, BC)   --> C
 0 DIV 0! --> 0 REM 0;  (0, B)    --> B

The codes you get will range from $0$ to $52! - 1$.

$\endgroup$
3
$\begingroup$

There are $4!=24$ permutations (which is what you want since order matters). It is cleaner (many fewer +1's and -1's) if the permutation numbers run from $0-23$ and the characters from $0-3$ For permutation $n$, the first digit is $\lfloor \frac n{3!} \rfloor$ Subtract $n-6\lfloor \frac n{3!} \rfloor$ and that is the permutation number for the remaining characters.

For a $52$ card deck, number the cards $0-51$. The first division should be by $51!$. When you have found the first card, take it out and do the same with $51$ cards, dividing by $50!$ and so on.

$\endgroup$
  • $\begingroup$ The letters were an example. The actual question is about a standard 52 card deck. $\endgroup$ – John Habert Jan 29 '14 at 21:58
  • $\begingroup$ @JohnHabert: I added the extension to $52$ $\endgroup$ – Ross Millikan Jan 29 '14 at 22:03
0
$\begingroup$

If the permutations are numbered in the lexicographical order, the number given to a permutation is sometimes called the rank of the permutation, although even this term is apparently not very common.

Some algorithms for rank->permutation and permutation->rank are listed for example here.

A simple observation is that the rank of a permutation $(a_i)_{i=0}^{N-1}$ of $\{0,1,\dots,N-1\}$ is $$ R=(N-1)! a_0 + R', $$ where $R'$ is the rank of the permutation $(a_i)_{i=1}^{N-1}$. Note that this formula cannot be directly applied recursively because $(a_i)_{i=1}^{N-1}$ is no longer a permutation of $\{0,1,\dots,N-2\}$.

$\endgroup$
0
$\begingroup$

I may be wrong about this, but as far as I know, there's not a canonical enumeration of the elements of the permutation group $S_{52}$ as $\{\pi_1, \pi_2, \ldots, \pi_{52!} \}$. You may be better off representing the shuffled deck as a product of cycles, and that's easy to do. Not sure what you're doing with this, but it might be useful.

Assuming the cards are numbered 1, 2, ... , 52, you can perform the following process until you exhaust the deck. Card $n_1=1$ now occupies position $n_2$ (which could still be 1, of course). Card $n_2$ then has been displaced to position $n_3$. So card $n_3$ has been displaced to position $n_4$, and so on. Because there are only 52 positions, you will eventually come to a card which has been displaced to the position originally occupied by card $n_1$. So you have a cycle $(n_1, n_2, \ldots, n_{M_1})$; this means that the card positions in the cycle have been rotated forward to the next position in the list, with an implicit wrap of the last to the first (the card in position $n_{M_1}$ has been displaced into position $n_1=1$). Note that it is completely possible that $M_1=1$, so that the first card is not moved, and that cycle has length 1. It is also possible that you traverse every single position before you arrive at the first position again, in which case the whole deck has been rearranged in a rotation (a single cycle of length 52).

For convenience, let's refine the notation and add a second subscript "$1$" to the elements of the cycle we just created to identify the fact that it is the "first" cycle: now we call the cycle we created above $(n_{1,1}, n_{1,2}, \ldots, n_{1,M_1})$.

If we have exhausted the deck, we are done. The shuffle is represented by a single cycle.

Otherwise, find the first position not yet considered, say position $n_{2,1}$, which will be the first member of our second cycle (hence the subscript "$2$"). As before, continue moving through the deck with the second cycle until you arrive back at position $n_{2,1}$ again, and we will have a second cycle $(n_{2,1}, n_{2,2}, \ldots, n_{2,M_2})$ containing $M_2$ positions. Note that the cycles are disjoint by construction.

And so on.

You eventually exhaust the deck with a finite number $N$ of cycles, each of which has a finite number of positions. These positions partition the deck into cycles by construction. So we can represent the shuffled deck as a product of partitions

$$(n_{1,1}, \ldots, n_{1,M_1})(n_{2,1}, \ldots, n_{2,M_2})\ldots(n_{N,1}, \ldots, n_{N,M_N})$$

where $M_1 + M_2 + \ldots + M_N = 52$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.