Myke Enriq

Ranch Hand

Posts: 115

posted 5 years ago

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 ?

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 ?

posted 5 years ago

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.

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

posted 5 years ago

loool

The thing is one can talk about

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

Find the formula champ ! (this is what this thread is asking in the first place). Only

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

Are you man enough to solve it ?

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 ?

posted 5 years ago

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

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

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 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

posted 5 years ago

This is only the begining of the discussion.

You say:

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)

3)

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 please3)

**Does a given permutation have a single composing series of cycles ?**
posted 5 years ago

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

Yes. (For some value of "easy".)

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.

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 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

posted 5 years ago

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

So the following algorithm solves ALL shuffling problems:

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.

least common multiple of the sizes of those cycles.

posted 5 years ago

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.

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

Posts: 3090

14

posted 5 years ago

ah...missed that once we started talking about 'shuffles'.
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

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: 4568

9

posted 5 years ago

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?

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?

Ryan McGuire

Ranch Hand

Posts: 1113

7

posted 5 years ago

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

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?

posted 5 years ago

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...

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: 1113

7

posted 5 years ago

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

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: 3090

14

posted 5 years ago

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: 1113

7

posted 2 years ago

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: 1113

7

posted 2 years ago

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 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?

posted 2 years ago

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 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: 1113

7

posted 2 years ago

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 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.

posted 2 years ago

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 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: 1113

7

posted 2 years ago

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.

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.

It is sorta covered in the JavaRanch Style Guide. |