Efficient program to print/return all increasing subsequences of size 3 in an array

Question

Given an array like

1, 6, 5, 2, 3, 4

we need to print

1 2 3
1 3 4
1 2 4
2 3 4

What is the best way to do this? Is this dynamic programming?

Is there a better way to do than the bruteforce O(n3)? I am sure there is.

The reason I say dynamic programming is because I can see this as something like

• for '1' (print all results of sub problem of the rest of the array with subsequences of size 2).

• for '2' (print all results of sub problems of the rest of the array with subseqences of size 2)

and go on like this.

However, there is a lot of overlap in the above two results, so we need to find an efficient way of reusing that, I guess.

Well, these are just random thoughts. You can correct me with the right appraoch.

OK, let me correct, if not print, I need the different increasing sequences returned. My point is, I need to find an approach to get to these sequences in the most efficient way.

Answer 1

You can walk through the array and remember what partial sequences are possible until the current point. Print and forget any sequences that reach length 3.

Example:

(1 6 5 2 3 4)
  ^
remember ((1))

(1 6 5 2 3 4)
    ^
remember ((1) (1 6) (6))

(1 6 5 2 3 4)
      ^
remember ((1) (1 6) (6) (1 5) (5))

(1 6 5 2 3 4)
        ^
remember ((1) (1 6) (6) (1 5) (5) (1 2) (2))

(1 6 5 2 3 4)
          ^
remember ((1) (1 6) (6) (1 5) (5) (1 2) (2) (1 3) (1 2 3) (2 3) (3))
print and forget (1 2 3)
remember ((1) (1 6) (6) (1 5) (5) (1 2) (2) (1 3) (2 3) (3))

(1 6 5 2 3 4)
            ^
remember ((1) (1 6) (6) (1 5) (5) (1 2) (2) (1 3) (2 3) (3) (1 4) (1 2 4) (2 4)
          (1 3 4) (2 3 4) (3 4) (4))
print and forget (1 2 4)
print and forget (1 3 4)
print and forget (2 3 4)
done.

The challenge seems to lie in the choice of an appropriate data structure for the remembered subsequences.

Answer 2

In the generalized case you have to calculate the complexity based on two things:

1- Count of input numbers (I will call it b)
2- Length of output (I will call it d)

A generalized method that I can think of, is to construct an analogous graph to the problem in O(n^2):

If a larger number comes after a smaller number, There is a directed edge from smaller one to it.

Now in order to find all sequences of length d, You need to start from each number and output all paths of length (d - 1).

If you use a traversal method like BFS the complexity will be less than O(d x (b ^ (d - 1))).

However you can use adjacent matrix multiplication to find the paths of length d, which will bring the complexity down to something less than O((d - 2) x (b ^ 3)). (Nth power of an adjacency matrix will tell you how many paths exist from each node to another with length of N).

There are algorithms to reduce square matrix multiplication complexity a bit.