File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Programming Diversions and the fly likes chip stack shuffle question Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "chip stack shuffle question" Watch "chip stack shuffle question" New topic
Author

chip stack shuffle question

Myke Enriq
Ranch Hand

Joined: Feb 13, 2012
Posts: 102
You have N poker chips in a stack. Also you have the mathematical function permutation X: P(c1 , c2 ,c3 ... cN) = {cp1 , cp2 , ... cpN}

So permutation X is one of the many permutations of N numbers. However you know it , and it is static (it is the same one from the begining to the end of this problem).

Question:

Given a stack of N chips and the permutation X , how many consecutive times do you apply permutation X to those chips to obtain the initial stack ?

Meaning you start with initial stack , then you shuffle it once using permutation X ,(each chip i goes to position PX(i) ) , then again and again. How many times you have to do that to get to the original stack ?
Steve Fahlbusch
Bartender

Joined: Sep 18, 2000
Posts: 555
    
    7

Trivial - at worst it is o(n2) normally it is n (log n) the proof is left to the OP
Steve Fahlbusch
Bartender

Joined: Sep 18, 2000
Posts: 555
    
    7

oh and by the way--- this is not a programming diversion.
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18110
    
    8

Most of the diversions which show up in this forum are really mathematical diversions and not programming diversions. This one: yup, it's mathematical but I suppose you could do some programming to solve it. But chances are that your program would be a "brute force" solution, which we mathematicians look down on.

Anyway I don't think the question as stated has an answer. For example the chosen permutation might be the identity permutation (the one which does nothing), in which case the answer would be zero. Or it might be the permutation which takes the top chip and moves it to the bottom of the stack, in which case the answer would be N.

Perhaps the question meant to ask for the maximum number of times to apply the permutation, i.e. the largest number of times that any permutation has to be applied? Or perhaps it meant to ask for a number M such that no matter which permutation you chose, applying it M times results in the initial stack? Both are interesting questions.
Myke Enriq
Ranch Hand

Joined: Feb 13, 2012
Posts: 102
Steve Fahlbusch wrote:Trivial - at worst it is o(n2) normally it is n (log n) the proof is left to the OP


loool

The thing is one can talk about what kind of permutation is it ? Really , Paul Clapham noticed that for a specific permutation the answer is zero. He actually had a moment to think before he posted unlike you.

What about for a permutation that only switches 2 numbers A and B between them and leaves all others intact ?


I have a feeling there is a rule / law to be discovered here , as well as a formula , that solves all these stack shuffle questions.

But to find the property of the permutation that directly affects the numbers of shuffles needed is a hard one . Like really , I bet with some computer simulation one can guess what law/property we are looking for.

Find the formula champ ! (this is what this thread is asking in the first place). Only after you solve it you can say it is an easy of hard question. That is if you solve it.

Really , to solve this takes time , patience , belief in your ability to solve , computing skills, simulating skills.

Are you man enough to solve it ?
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18110
    
    8

Well, it wasn't hard for me to notice that sort of thing because I did my PhD in the subject.

So here's the way to look at it.

Let's suppose you have 8 things being permuted. I don't like the stack-of-coins image because it seems kind of awkward to be taking coins and stuffing them in the middle of the stack, but it doesn't really matter. It's easier to just use the numbers from 1 to 8 anyway, so let's do that. There are 40,320 different permutations of those 8 numbers, that's 8 factorial. One of them looks like this:

(1 3)(2 7 4)(5 6 8)

That means that 1 goes to 3 and 3 goes to 1; 2 goes to 7, 7 goes to 4, and 4 goes to 2; 5 goes to 6, 6 goes to 8, and 8 goes to 5.

Now what happens if we apply this twice? Then 1 goes to 1 and 3 goes to 3; 2 goes to 4, 4 goes to 7, and so on, so the result looks like this:

(1)(3)(2 4 7)(5 8 6)

So this leaves two of the numbers fixed.

And if you apply that permutation three times, then (leaving out the work) the result looks like this:

(1 3)(2)(4)(5)(6)(7)(8)

In other words it leaves all but two of the numbers fixed.

And if you think about it a bit, you'll see that applying the permutation six times, the result leaves all of the numbers fixed. So the order of that permutation, as we call it in the math biz, is 6.

That's because in the representation I originally wrote down it had a 2-cycle and two 3-cycles. The 2-cycle has order 2 and the 3-cycles have order 3, so their product (we think of applying one permutation followed by applying another permutation as "multiplication") has order 6. You might think the order of the product should be 2 x 3 x 3, but since the two 3-cycles operate "in parallel" the order of the product is really the greatest common multiple of the orders of the individual cycles.

So that's the rule you're looking for. There is a permutation of the 8 coins which has order 7... can you find it? And can you find one which has order 15?
Myke Enriq
Ranch Hand

Joined: Feb 13, 2012
Posts: 102
This is only the begining of the discussion.

You say:

Each permutation can be decomposed in a series of cycles , and the least common denominator of those cycles is the number we are looking for.

1) I guess it is easy to prove that this number you get is the smallest number for wich the cards are suffled back in place.
2) How do you decompose a given permutation in its cycles ? Algorithm please
3) Does a given permutation have a single composing series of cycles ?
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18110
    
    8

Myke Enriq wrote:This is only the begining of the discussion.


Of course it is. That's how come people can spend 4 years writing a thesis about the topic.

1) I guess it is easy to prove that this number you get is the smallest number for wich the cards are suffled back in place.

Yes. (For some value of "easy".)
2) How do you decompose a given permutation in its cycles ? Algorithm please

What is 1 mapped to? Call it X. If X is 1 then we're done finding the cycle containing 1. Otherwise what is X mapped to? Repeat until we get back to 1... which we must because there's only a finite number of coins/cards/whatever. Then we have the cycle containing 1.

Now consider all the numbers which aren't in that cycle. If there aren't any then we're done. Otherwise repeat the process starting with the smallest number in that set.

Repeat until every number is in one of the cycles.
3) Does a given permutation have a single composing series of cycles ?

Is the representation as a set of cycles unique? That's a good question. Wouldn't be out of place at the end of Chapter 1 of the text book. The answer is "yes" but it isn't obvious. The algorithm I posted makes it look like there's only one possible representation, but what would happen if you chose 2 as your starting point instead of 1?

In that case instead of ending up with (1 2 3) as the representation of the permutation you might end up with (2 3 1). That looks different but it's really the same in terms of how it actually works: 1 goes to 2 and 2 goes to 3 and 3 goes to 1 in both cases.
Myke Enriq
Ranch Hand

Joined: Feb 13, 2012
Posts: 102
Paul Clapham wrote:

2) How do you decompose a given permutation in its cycles ? Algorithm please

What is 1 mapped to? Call it X. If X is 1 then we're done finding the cycle containing 1. Otherwise what is X mapped to? Repeat until we get back to 1... which we must because there's only a finite number of coins/cards/whatever. Then we have the cycle containing 1.

Now consider all the numbers which aren't in that cycle. If there aren't any then we're done. Otherwise repeat the process starting with the smallest number in that set.

Repeat until every number is in one of the cycles.




You should elaborate more on the fact that if chip1 has the following cycle: 1 -> 2 -> 7 -> 1 meaning cycle (1 , 2 ,7) then 2 and 7 also are described by this cycle. I guess it is ok.


So the following algorithm solves ALL shuffling problems:

Take the permutation , find the cycle for 1, for 2(if 2 is not in the cycle of 1) , for 3 (if 3 is not in the cycle of 1 or in the cycle of 2) ... and so on then compose the
least common multiple of the sizes of those cycles.

Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18110
    
    8

Ouch! You're marking my homework assignment!

But yeah, I think you've got the idea.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10905
    
  12

Is it a requirement that the shuffles don't know anything about each other? because I could define a shuffle this way:



so if i have
1 2 3 4

the first shuffle gives me
3 1 2 4

then i get
1 3 2 4

and these last two keep oscillating. I will never get back to my original state.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2969
    
    9
That was covered:
So permutation X is one of the many permutations of N numbers. However you know it , and it is static (it is the same one from the begining to the end of this problem).
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 10905
    
  12

Mike Simmons wrote:That was covered:
So permutation X is one of the many permutations of N numbers. However you know it , and it is static (it is the same one from the begining to the end of this problem).

ah...missed that once we started talking about 'shuffles'.
Matthew Brown
Bartender

Joined: Apr 06, 2010
Posts: 4240
    
    7

Paul Clapham wrote:So that's the rule you're looking for. There is a permutation of the 8 coins which has order 7... can you find it? And can you find one which has order 15?

So order 7 would be any permutation combining a cycle of 1 and a cycle of 7? And order 15 would be any with a cycle of 3 and one of 5?
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2969
    
    9
Yup.
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 988
    
    1
Matthew Brown wrote:So order 7 would be any permutation combining a cycle of 1 and a cycle of 7? And order 15 would be any with a cycle of 3 and one of 5?


So...

For a given N, how can you split that up so that the least common multiple is the maximum?

For N=8, some of the options are (2,3,3) with a LCM of 6, (1,7) with an LCM of 7 and (5, 3) with an LCM of 15. A quick exhaustive search should convince that (3,5) for an LCM of 15 is the maximum for N=8.

Given any value of N, how can you determine the greatest LCM?

Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18110
    
    8

It must have been somebody called Landau who first thought of that, because Wolfram MathWorld calls it "Landau's function". Wolfram doesn't mention how to calculate it, but Landau didn't know that either. Since it deals with partitions of the numbers from 1 to n, and we don't even have an expression which counts such partitions, there isn't going to be an expression for Landau's function either.

Of course we could do some programming which would spit out the value of Landau(n) for any n, and this IS the Programming Diversions forum...
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 988
    
    1
Paul Clapham wrote:It must have been somebody called Landau who first thought of that, because Wolfram MathWorld calls it "Landau's function". Wolfram doesn't mention how to calculate it, but Landau didn't know that either. Since it deals with partitions of the numbers from 1 to n, and we don't even have an expression which counts such partitions, there isn't going to be an expression for Landau's function either.

Of course we could do some programming which would spit out the value of Landau(n) for any n, and this IS the Programming Diversions forum...


Writing an brute force, exhaustive search algorithm to find Landau(n) would be straightforward enough. However, I wonder if there is way to avoid checking every partition.
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2969
    
    9
Well for starters, I'm pretty sure we could skip considering anything except powers of primes. Furthermore once a given power of a prime is included, there's no point in including any lower powers of that same prime as part of the same partition. Ultimately only one power of a given prime should be part of any considered solution.
 
jQuery in Action, 2nd edition
 
subject: chip stack shuffle question
 
Similar Threads
general RT\Embedded with J2ME
Another horse race
Poker chips shuffling 2
Shuffling poker chips
How does this actually solve Towers of Hanoi?