#### Lab 1890 - UD Sequences

##### Description

An up-down sequence of length *n* is a reordering of the numbers 1,2,3,...,n such that the second number is larger than
the first, the third is smaller than the second, the fourth is larger than the third, and so on in an alternating up-down
way.

Here are all the up-down sequences of length 4 or less:

n=1 1

n=2 1,2

n=3 1,3,2; 2,3,1

n=4 1,3,2,4; 1,4,2,3; 2,3,1,4; 2,4,1,3; 3,4,1,2

You are to find all the up-down sequences for n=5 and n=6.

##### Algorithm

Take the numbers 1, 2, 3, 4, 5, and 6. Pick a number -- I'll choose 2. Of the unpicked numbers above 2, pick a number: 3. Then
one below 3: 1; and another above 1: 5; and a number below 5: 4. That sequence 2-3-1-5-4 is a valid up-down sequence.

You could randomly choose numbers finding sequences and then use a HashSet to keep track of unique solutions until you have
all 16 of them for n=5 or all 61 for n=6. For this lab, though, you should use an exhaustive algorithm. One suggestion: pick a
number, then make a list of all sequences with that number and all available higher numbers. Then with that list, create a list
of all sequences with those two first numbers and all available lower numbers in the third spot. Continue in an up-down manner
until all solutions are found. The ListQueue data structure should feel like a good fit for this.

Copyright © 2010 by Asylum Computer Services LLC |
Return to CS Labs |