On 17/05/2012, at 2:04 PM, Gregg Lebovitz wrote:
Richard,
Thank you. This is an example of what I had in mind when I talked about changing the playing field. Do you have a slide deck for this lecture that you would be willing to share with me? I am very interested in learning more.
No slide deck required. The task is "generating alternating permutations". Method 1: generate permutations using a backtracking search; when a permutation is generated, check if it is alternating. Method 2: use the same backtracking search, but only allow extensions that preserve the property of being an alternating permutation. For n=12 the second method is 94 times faster than the first, and the ratio increases with growing n. At the time I wrote the program I had not heard of Bauslaugh and Ruskey's constant-average-time algorithm for generating alternating permutations. Experimentally the Method 2 backtracking search appears to take constant time per solution anyway. n (time ms): En n! 1 ( 0.0): 1 1 <- method 1 1 ( 0.0): 1 <- method 2 2 ( 0.0): 1 2 2 ( 0.0): 1 3 ( 0.0): 2 6 3 ( 0.0): 2 4 ( 0.0): 5 24 4 ( 0.0): 5 5 ( 0.0): 16 120 5 ( 0.0): 16 6 ( 0.1): 61 720 6 ( 0.0): 61 7 ( 0.6): 272 5040 7 ( 0.1): 272 8 ( 4.4): 1385 40320 8 ( 0.3): 1385 9 ( 35.2): 7936 362880 9 ( 1.4): 7936 10 ( 359.7): 50521 3628800 10 ( 9.3): 50521 11 ( 4035.7): 353792 39916800 11 ( 67.0): 353792 12 (49584.6): 2702765 479001600 <- method 1 12 ( 528.1): 2702765 <- method 2 Those times are in C; SWI Prolog (which compiles to an abstract instruction set that is then interpreted by portable C) was about 24 times slower. A factor of 94 comfortably exceeds a factor of 24...