Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# chip stack shuffle question

Myke Enriq
Ranch Hand
Posts: 115
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
Posts: 605
7
Trivial - at worst it is o(n2) normally it is n (log n) the proof is left to the OP

Steve Fahlbusch
Bartender
Posts: 605
7
oh and by the way--- this is not a programming diversion.

Paul Clapham
Sheriff
Posts: 21107
32
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
Posts: 115
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
Sheriff
Posts: 21107
32
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
Posts: 115
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
Sheriff
Posts: 21107
32
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
Posts: 115
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
Sheriff
Posts: 21107
32
Ouch! You're marking my homework assignment!

But yeah, I think you've got the idea.

fred rosenberger
lowercase baba
Bartender
Posts: 12127
30
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.

Mike Simmons
Ranch Hand
Posts: 3080
14
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
Posts: 12127
30
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
Posts: 4567
8
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
Posts: 3080
14
Yup.

Ryan McGuire
Ranch Hand
Posts: 1067
4
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
Sheriff
Posts: 21107
32
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
Posts: 1067
4
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
Posts: 3080
14
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.

Ryan McGuire
Ranch Hand
Posts: 1067
4
What if your stack had a billion trillion (10 ^ 15) chips in it? http://arxiv.org/pdf/0803.2160v1.pdf

Ryan McGuire
Ranch Hand
Posts: 1067
4
Paul Clapham wrote: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...

Exactly. I revived this thread because it has come down to a question of programming and, so far, nobody had offered any programs.

I spent a couple hours last night working it out with pencil and paper and then refreshing myself on Java after a few years of using just C# and came up with some code. My program matches values with The Online Encyclopedia of Integer Sequences up to Landau(47). Can anyone confirm or refute that Landau(250) = 2147478576? I'll post the code once I have a chance to neaten it up and possibly use some long ints for a few things, but the algorithm is good enough. The trickiest part was ordering the partitions for a number. e.g. Once you have 5+8+13+1+1 as a partition for 28, what is the "next" partition?

Paul Clapham
Sheriff
Posts: 21107
32
Ryan McGuire wrote:Can anyone confirm or refute that Landau(250) = 2147478576?

Reference 18 in http://arxiv.org/pdf/0803.2160v1.pdf is here: http://archive.numdam.org/article/BSMF_1969__97__129_0.pdf (retrieved from J-L Nicolas's website http://math.univ-lyon1.fr/~nicolas/publications.html) and it claims that g(250) is 3,651,003,162,326,520.

Ryan McGuire
Ranch Hand
Posts: 1067
4
Paul Clapham wrote:
Ryan McGuire wrote:Can anyone confirm or refute that Landau(250) = 2147478576?

Reference 18 in http://arxiv.org/pdf/0803.2160v1.pdf is here: http://archive.numdam.org/article/BSMF_1969__97__129_0.pdf (retrieved from J-L Nicolas's website http://math.univ-lyon1.fr/~nicolas/publications.html) and it claims that g(250) is 3,651,003,162,326,520.

I'm glad I already mentioned having to go back use long ints in a few places since that is the issue here. Even that value for g(250) is approaching 2^64, so I may have to go with BigIntegers to go much higher.

Paul Clapham
Sheriff
Posts: 21107
32
Ryan McGuire wrote:I'm glad I already mentioned having to go back use long ints in a few places since that is the issue here.

I sort of guessed that.

I noticed that Nicolas had actual algorithms in some of his papers. (They are in antique languages because the papers were written in the Dark Ages of computing, but still...) If you don't consider it cheating you could have a look at those papers.

Ryan McGuire
Ranch Hand
Posts: 1067
4
Paul Clapham wrote:I noticed that Nicolas had actual algorithms in some of his papers. (They are in antique languages because the papers were written in the Dark Ages of computing, but still...) If you don't consider it cheating you could have a look at those papers.

I wanted to go through the exercise of implementing at least a slightly-better-than-brute-force algorithm. This is a Programming Diversions, as opposed to Higher Math Diversions, forum so I'm satisfied that we've completed the original task as assigned. Mmmmaybe I'll look at the Maple code and see if I can translate the improved algorithm to Java, but that would count as a new assignment.

If you're curious, my run for g(500) finally completed overnight at some point. The final results for that are 16, 27, 25, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 61 = 715657920159093382270800. So if you had 500 poker chips in a stack and were able to perform one of these shuffles every minute, how long would it take you to get the chips back to the original order? At least a day or two, I would guess.