Lab 1890 - UD Sequences


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.


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