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 ?
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.
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 ?
So here's the way to look at it.
Let's suppose you have 8 things being permuted. I don't like the stackofcoins 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 2cycle and two 3cycles. The 2cycle has order 2 and the 3cycles 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 3cycles 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?
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 ?
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.
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.
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 offbyone 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'.
There are only two hard things in computer science: cache invalidation, naming things, and offbyone errors
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?
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?
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...
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.
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?
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 JL Nicolas's website http://math.univlyon1.fr/~nicolas/publications.html) and it claims that g(250) is 3,651,003,162,326,520.
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 JL Nicolas's website http://math.univlyon1.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.
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.
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 slightlybetterthanbruteforce 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.
Bras cause cancer. And tiny ads:
Why should you try IntelliJ IDEA ?
https://coderanch.com/wiki/696337/IntelliJIDEA
