Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.games.development.programming.algorithms > #36 > unrolled thread

Shuffling

Back to article view | Back to comp.games.development.programming.algorithms

Contents

  Shuffling Mok-Kong Shen <mok-kong.shen@t-online.de> - 2012-07-30 12:52 +0200
    Re: Shuffling Mok-Kong Shen <mok-kong.shen@t-online.de> - 2012-08-01 20:14 +0200
    Re: Shuffling hexxial <hexxial@gmail.com> - 2013-01-20 22:58 +0000

#36 — Shuffling

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

[toc] | [next] | [standalone]

#37

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)

[toc] | [prev] | [next] | [standalone]

#41

Em 30-07-2012 11:52, Mok-Kong Shen escreveu:
>
> 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

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/

[toc] | [prev] | [standalone]

Back to top | Article view | comp.games.development.programming.algorithms

csiph-web