Shuffling

[Mok-Kong Shen]

For playing cards there are riffle shuffling etc. With computers
one is not dependent on constraints resulting from manual working
and consequently could specify more complex operations that may be
rather inconvenient to be performed manually. I like thus to pose
a general question as follows:

Given a list of n different elements, could one find a shuffling
(permutation) operation on them which can be characterized by the
numerical value of one single parameter (corresponding essentially
to the cutting point of a card deck into two parts in manual
shuffling) and which is likely to lead to the highest degree of
derangement (disorder) of the original list?

I have done some small amount of experiments but I don't think
to have yet found a really optimal permutation operation.

Thanks in advance.

M. K. Shen

[Mok-Kong Shen]

Am 30.07.2012 12:52, schrieb Mok-Kong Shen:
[snip]

> I have done some small amount of experiments but I don't think
> to have yet found a really optimal permutation operation.

A presumably not too bad, though I think yet sub-optimal, scheme
I found sofar is as follow:

Let n be the length of the list to be permuted and kn be a point of
division of the list into two sections. One applies riffle shuffle
to each section and then reverse the ordering of the whole.

It seems to me that, if kn is (randomly chosen and) located in the
middle half of the list, then the permutation effected is a sufficiently
"random" one in some sense.

Perhaps someone could give hints on improvements or provide a similar
but better scheme. For those who like to try out mine, I am attaching
a Python code below.

M. K. Shen

-----------------------------------------------------------

def makecards(n):
cards=[]
for i in range(n):
cards+=[i]
return(cards)

def riffle(cards,n):
newcards=[]
nh=n//2
for i in range(nh):
newcards=newcards+[cards[nh+i]]+[cards[i]]
if nh*2<n:
newcards+=[cards[n-1]]
return(newcards)

def newshuffle(cards,kn,n):
newcards=riffle(cards[0:kn],kn)+riffle(cards[kn:n],n-kn)
newcards.reverse()
return(newcards)

# example:

n=52
cards=makecards(n)
kn=18
newcards=newshuffle(cards,kn,n)
print(newcards)

[hexxial]

Pokerstars is an online poker room. They offer a webpage explaining the
shuffling algorithm they use:

"To perform an actual shuffle, we use another simple and reliable algorithm:
- first we draw a random card from the original deck (1 of 52) and place
it in a new deck - now original deck contains 51 cards and the new deck
contains 1 card
- then we draw another random card from the original deck (1 of 51) and
place it on top of the new deck - now original deck contains 50 cards
and the new deck contains 2 cards
- we repeat the process until all cards have moved from the original
deck to the new deck
This algorithm does not suffer from "Bad Distribution Of Shuffles"
described in [1]."

It's actually pretty simple and effective, given a good random number
generator (they also explain how they generate numbers using entropy
generated by the users). If you're interested check out their webpage
explaining it: http://www.pokerstars.com/poker/room/features/security/