UT dallas eesearchers continue related work on topswops problem news
30 October 2010

Dr. Linda Morales and Dr. Hal SudboroughIn a related issue, Sudborough, Morales and their graduate students have also computed the maximum number of Topswops steps over all permutations of length n for small integers n.

Because there are more than 355 trillion different permutations of length 17, a brute force approach of trying all such permutations, one after the other, would require months of computation time. Knuth, who had previously computed the exact number for n=16, used a new, innovative approach, which allowed much shorter computation times. The UT Dallas group made several additional improvements and was able to determine that permutations of length 17 require at most 159 Topswops steps.

And their new technique required only a few days of computation. They have continued by also showing there is a permutation of length 18 that terminates with all cards in sorted order in 191 Topswops steps and that no such permutation of length 18 takes more than 191 steps. Why is that a noteworthy achievement of computational performance? Because there are more than 6 quadrillion permutations of length 18.





 search domain-b
  go
 
UT dallas eesearchers continue related work on topswops problem