CODEWITHSUNDEEP
algorithmrandom
Sid
Sid

Reputation: 573

Quick idea for a shuffling algorithm - would this work?

I was discussing with my brothers a quick-and-dirty algorithm for shuffling a deck of cards (i.e. an array in which every element is unique). Description of the algorithm:

Let the number of cards in the deck be n. Take a number x so that gcd(n,x)=1. Now iteratively pick the card number (x*i) mod n for i=1 up to i=n and put it in a new pile of cards (without removing the card from the original deck, that is, make a copy of the card). The new pile of card will be our result.

It seems clear to me that only performing this algorithm once will not give a result that is "random enough" (in the sense that it would fail statistical tests for determining randomness). But what if we perform the algorithm iteratively, possibly for a new value of x that also fulfills gcd(n,x)=1? If doing this a sufficient number of times would give us a "random enough" result, how many times could we expect to need to do this as a function of n?

Upvotes: 1

Views: 117

Answers (1)

Kaganar
Kaganar

Reputation: 6570

Doing it multiple times would be insufficient due to the wonders of modulo arithmetic. In fact, there are at most n permutations you could ever achieve this way, and that's precisely when n is prime or 1.

Suppose you were to do this twice, with x relatively prime to n the first time and y relatively prime to n the second time.

The first time an element at position p is moved to p * x (mod n). Then the second time it is moved to (p * x) * y (mod n). This is the same as moving it to p * (x * y) (mod n) because of the associative nature of modular arithmetic. But if x * y = v (mod n) then it's the same as moving it to p * v (mod n) -- and as you know, there aren't more than n equivalence classes.

Hence, there are at most n permutations that could be resulted in a n-length deck. (No, this isn't a rigorous proof!)

Edit:

I had claimed if you used modular multiplicative exponentiation instead, it would be superior. However, after additional consideration many trivial configurations would still fall prey to modular arithmetic in the same "at most n permutations" way.

Upvotes: 3

Related Questions