### Notes on an Algorithm to Enumerate Langford Sequences

© John E. Miller, 1997.

The trick is shifting all the pairs around in a systematic order to exhaust
all possible positional combinations, finding all the possible langford
sequences for a given number of pairs in the process.

123456 Actions
...... empty arrangement
3...3. 3's placed in first position
.2..2. 2's can't fit in second position, conflicts with 3's
..2..2 2's do fit in third position
1.1... 1's can't fit in first position, conflicts with 2's
.1.1.. 1's fit in second
312132 bingo! complete arrangement

A Hand-Waving Explanation:
The algorithm proceeds simply by starting each pair at the leftmost
position and scanning for the first position where it will fit. After the
pair has been fit into the arrangement and all smaller pairs have likewise
been attempted and removed, the pair moves over to the next available place
- not back at the left. When a pair has gone all the way over to the right
(i.e. the right element of the pair would fall off the end of the
arrangement), attention shifts up to the next higher pair, and attention
will come back down again if that higher pair is fit into the arrangement.
The remainder of this page goes into various aspects of implementing this
algorithm.

#### An note on efficiency - using a linked list

The main thing that I missed implementing this algorithm for speed was to keep
a list (a linked-list in CS parlance) of unfilled positions in the arrangement.
This may seem like more work in the beginning or when the arrangement is
sparsely filled. This is not the case! You need to scan for them anyway, AND
when the arrangement is nearly filled, having a linked list is very handy for
placing the 4's, 3's, and so on. Get the idea? This is one way Rick Groth's
algorithm managed to start way later than mine and overtake it computing L(2,19).
(Another way is by breaking the problem down by position of the 19's, and using a computer for each position.)

I do have some of Rick's source code, but I leave that as an exercise for the
reader. I don't know if any of Ruskey's students employed this time-saver.
I would assume so - jm 8/2001

### An Array-Based, Non-Recursive Algorithm

### Notes on the above algorithm

#### Termination upon reaching the reflection point

The above algorithm if left alone will produce twice the number of solutions,
since it continues to shift the n's all the way across the arrangement.
The solutions produced are unique up to the point where the solution
produced is the reversal of the previous arrangement. Solutions produced
past the reflection point are mirror images of successively older solutions,
to where the last solution produced is a mirror of the first.

For odd n's, this occurs exactly when the highest pair is shifted past
the middle of the arrangement. For even values of n, the highest pair can
occupy the middle of the arrangement, and therefore the reversal
(reflection) occurs with the (n-1)st pair is shifted past the middle.

The exact positions can be known ahead of time and tested for. My
algorithm just saves a copy of the previously
found solution to be used in testing for this reflection point. It takes
very little overhead since the test for the reflection fails quickly except
when it is for real. I think this is more elegant since it works for both
odd & even values of n.

#### Use of a position vector

In order to aid in removing a given pair from the arrangement when the time
comes, the position of the leftmost element can be recorded in a vector
(array). The value of p can be fetched from the vector, and the
corresponding elements of A can be zeroed.

The position is also needed in order to continue the scan from the place
where the pair was resting.

#### Erasing the 1,2,3's

Once a solution is found, there is no point in continuing to scan for
a new place for the 1's, since there is only 2 places vacant in the
arrangement, and the 1's were just there!

Similarly, it is easy to show that removing the 1's and the 2's does
not create any new possibilities for placement of the 1's and 2's.

The same goes for removing the 3's too, except in the case where a 312132
subsequence is embedded in the larger sequence. It can replaced with
its reverse in order to create yet another solution. Special programming
for this situation is not warranted - it takes very little time to
just let the algorithm work toward the next solution or work its way back
up into higher pairs in search of the next solution.

I did some investigation of this in 1970 or so (while at WSU) and found
that it made virtually no difference in the overall performance. (I was
designing a special circuit at the time, and I wanted to see what if it was
important or not).

But it is easy enough in the coding to remove the 1's, 2's and 3's, and let
the algorithm proceed scanning for a place for the 3's. If it fails, it
will go up to the 4's, etc. If it succeeds, it may lead to the reversal
of the 3-subsequence. So, my programs employ this little trick.

#### Going from low to high

The obvious question is - what if I start by placing the 1's into the
solution first and then the 2's, et cetera, up to the n's?

The answer isn't obvious to me. I don't recall making any quantitative
measure of this. Intuitively, it seems easier to fit the smaller pairs in
towards the last, but I really don't think they are any easier

.

Perhaps someone could do some comparisons on the amount of back-tracking
that has to be done between low-to-high and high-to-low algorithms.
I would be surprised if there were a significant advantage between these
two. Are they the same? If not, one has to be better -- but by how much?
And is one *consistently* better? If not, which should you use based
on n?

### Notes on other approaches, good and bad

#### bits vs bytes

Use n binary masks where two bits are separated by k bits, k=1,n.
Use logical operations between the arrangement word and each of the
masks which you shift to the right as you scan.

Andrew Burke's program, and others over time have used this method. It is
faster by a factor of 4 or so from a byte-oriented program, but is limited
to the word length of the machine -- 32 bits could handle n=16, or 64 bits
could handle 32 pairs (in the case of a CRAY or DEC Alpha).

The algorithm could be fine-tuned by coding in assembly language for sure,
taking advantage of the particular architecture. My earlier assault on 12
was done in assembly on a 16-bit computer, but not using bit masks.

#### Pruning the search?

It is questionable whether there is much checking you can to at any point
that is worth the overhead spent.

Stopping after each insertion to check whether it is feasible that all
pairs might individually fit into the arrangement is a lot of work, but it
would prevent a lot of needless work. I did a test on this, and it was less
important as n increased. I.e., When there are lots of empty spaces, most
pairs look feasible at some place in the arrangement. When there are fewer
empty places, it pays to just let the algorithm proceed and eliminate what
doesn't work.

I can't think of a reason or criteria that would define a level when
such look-ahead's could be turned on or off.

In short, I see no opportunity for pruning the search. Suggestions welcome!

#### Recursion

The algorithm can be coded somewhat more simply in a recursive manner -
but at the expense of system overhead. I see no advantage to recursion,
other than a means to employ multiple processors.

#### Parallelism

Langford's Problem is a natural candidate for multi-processing.
It can easily be decomposed into any number of independent sub-problems.

One method would be to have a top-level program generate a set of partially
completed Langford sequences. The depth of this completion could be
increased until you got a desired number of partial solutions, which you
would save. Then using a system such as Linda

, place the list of partial
solutions into its Tuple Space

and make them available to a pool of
processors in your Linda O/S. Processors would pick up a tuple, and return
the result. If a processor crashed or otherwise never returned a particular
tuple, Linda would eventually assign it to another processor.

### Pseudo Code

begin
initialize;
repeat
try;
if successful
then lowerpair
else higherpair
until done
end.

Download a C program (only 2K) and see for yourself.

This is all I have time for now. I have notes from Randy Austin
about some of the questions that I've raised above about testing whether it makes any difference wo work from low to high or VV.

Created by: john@timehaven•us

Modified: May 30, 2004, edited Jan 2020!