Steve Fahlbusch wrote:Trivial - at worst it is o(n2) normally it is n (log n) the proof is left to the OP
Myke Enriq wrote:This is only the begining of the discussion.
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 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.
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
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).
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).
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one 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?
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?
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...
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...
Ryan McGuire wrote:Can anyone confirm or refute that Landau(250) = 2147478576?
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.
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.
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.
Did you see how Paul cut 87% off of his electric heat bill with 82 watts of micro heaters? |