Richard O'Keefe ok at cs.otago.ac.nz
Thu May 17 07:11:42 CEST 2012

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

```