All possible bitonic sets of given digits N

Question

We know that a bitonic sequence has a increasing and then decreasing sequence of digits like:

{6,7,8,9,5,4,3,2,1}, {5,7,8,9,6,4,3,2,1}  are bitonic sets for N=9

Is there any efficient algorithm for finding all possible bitonic sets for given no of digits N.

We can generalize this case for a set of size N.

There exist some element (K) in the set for which:

N(i) > N(i+1) true for all elements right of k.

N(i+1) > N(i) true for all elements left of k inclusive.

like for {6,7,8,9,5,4,3,2,1}, k = 9

Now the elements in the sets will be unique.

We have to find all unique sets following above bitonic property?

Kindly correct if i am doing some mistake in using terminology.

Answer 1

Here's an algorithm. Place $N$, then $N-1$, then $N-2$, and so on, down to one, as follows: whenever you have a choice of places to put a number, place it as far left as you can; when you complete a permutation, go back to the last place where you had a choice to make, and make the first choice farther to the right, and proceed as before.

Here's what it generates for $N=5$:

45321, 35421, 25431, 15432, 34521, 24531, 14532, 23541, 13542, 12543, 23451, 13452, 12453, 12354.

Answer 2

To calculate the count of all combination of sets in bitonic sequence: Let N = 6

Fixing 6 at position 2 will produce set like this:

_ 6 _ _ _ _

So we have to choose 1 digit from rest 5 digits such that sequence is increasing, we can do this in 5C1 ways.

_ _ 6 _ _ _

Now we have to choose 2 digits from rest 5 digits such that sequence is increasing, we can do this in 5C2 ways.

and so on till we have 6 at N-1 position.

So the total number of possible sets will be:

5C1 + 5C2 + 5C3 + 5C4 = 2^5 -2

So the no of bitonic sets for any N distinct integers set

2^n - 2