Number of all increasing subsequences in given sequence?

Question

You may have heard about the well-known problem of finding the longest increasing subsequence. The optimal algorithm has O(n*log(n))complexity.

I was thinking about problem of finding all increasing subsequences in given sequence. I have found solution for a problem where we need to find a number of increasing subsequences of length k, which has O(n*k*log(n)) complexity (where n is a length of a sequence).

Of course, this algorithm can be used for my problem, but then solution has O(n*k*log(n)*n) = O(n^2*k*log(n)) complexity, I suppose. I think, that there must be a better (I mean - faster) solution, but I don't know such yet.

If you know how to solve the problem of finding all increasing subsequences in given sequence in optimal time/complexity (in this case, optimal = better than O(n^2*k*log(n))), please let me know about that.

In the end: this problem is not a homework. There was mentioned on my lecture a problem of the longest increasing subsequence and I have started thinking about general idea of all increasing subsequences in given sequence.

Answer 1

I don't know if this is optimal - probably not, but here's a DP solution in O(n^2).

Let dp[i] = number of increasing subsequences with i as the last element

for i = 1 to n do
    dp[i] = 1
    for j = 1 to i - 1 do
        if input[j] < input[i] then
            dp[i] = dp[i] + dp[j] // we can just append input[i] to every subsequence ending with j

Then it's just a matter of summing all the entries in dp

Answer 2

You can compute the number of increasing subsequences in O(n log n) time as follows.

Recall the algorithm for the length of the longest increasing subsequence:

For each element, compute the predecessor element among previous elements, and add one to that length.

This algorithm runs naively in O(n^2) time, and runs in O(n log n) (or even better, in the case of integers), if you compute the predecessor using a data structure like a balanced binary search tree (BST) (or something more advanced like a van Emde Boas tree for integers).

To amend this algorithm for computing the number of sequences, store in the BST in each node the number of sequences ending at that element. When processing the next element in the list, you simply search for the predecessor, count the number of sequences ending at an element that is less than the element currently being processed (in O(log n) time), and store the result in the BST along with the current element. Finally, you sum the results for every element in the tree to get the result.

As a caveat, note that the number of increasing sequences could be very large, so that the arithmetic no longer takes O(1) time per operation. This needs to be taken into consideration.

Psuedocode:

ret = 0
T = empty_augmented_bst() // with an integer field in addition to the key
for x int X:

  // sum of auxiliary fields of keys less than x
  // computed in O(log n) time using augmented BSTs
  count = 1 + T.sum_less(x)

  T.insert(x, 1 + count) // sets x's auxiliary field to 1 + count
  ret += count // keep track of return value

return ret

Answer 3

I'm assuming without loss of generalization the input A[0..(n-1)] consists of all integers in {0, 1, ..., n-1}.

Let DP[i] = number of increasing subsequences ending in A[i].

We have the recurrence:

To compute DP[i], we only need to compute DP[j] for all j where A[j] < A[i]. Therefore, we can compute the DP array in the ascending order of values of A. This leaves DP[k] = 0 for all k where A[k] > A[i].

The problem boils down to computing the sum DP[0] to DP[i-1]. Supposing we have already calculated DP[0] to DP[i-1], we can calculate DP[i] in O(log n) using a Fenwick tree.

The final answer is then DP[0] + DP[1] + ... DP[n-1]. The algorithm runs in O(n log n).

Answer 4

This is an O(nklogn) solution where n is the length of the input array and k is the size of the increasing sub-sequences. It is based on the solution mentioned in the question.

vector<int> values, an n length array, is the array to be searched for increasing sub-sequences.

vector<int> temp(n); // Array for sorting
map<int, int> mapIndex; // This will translate from the value in index to the 1-based count of values less than it

partial_sort_copy(values.cbegin(), values.cend(), temp.begin(), temp.end());

for(auto i = 0; i < n; ++i){
    mapIndex.insert(make_pair(temp[i], i + 1)); // insert will only allow each number to be added to the map the first time
}

mapIndex now contains a ranking of all numbers in values.

vector<vector<int>> binaryIndexTree(k, vector<int>(n)); // A 2D binary index tree with depth k
auto result = 0;

for(auto it = values.cbegin(); it != values.cend(); ++it){
    auto rank = mapIndex[*it];
    auto value = 1; // Number of sequences to be added to this rank and all subsequent ranks
    update(rank, value, binaryIndexTree[0]); // Populate the binary index tree for sub-sequences of length 1

    for(auto i = 1; i < k; ++i){ // Itterate over all sub-sequence lengths 2 - k
        value = getValue(rank - 1, binaryIndexTree[i - 1]); // Retrieve all possible shorter sub-sequences of lesser or equal rank
        update(rank, value, binaryIndexTree[i]); // Update the binary index tree for sub sequences of this length
    }
    result += value; // Add the possible sub-sequences of length k for this rank
}

After placing all n elements of values into all k dimensions of binaryIndexTree. The values collected into result represent the total number of increasing sub-sequences of length k.

The binary index tree functions used to obtain this result are:

void update(int rank, int increment, vector<int>& binaryIndexTree)
{
    while (rank < binaryIndexTree.size()) { // Increment the current rank and all higher ranks
        binaryIndexTree[rank - 1] += increment;
        rank += (rank & -rank);
    }
}

int getValue(int rank, const vector<int>& binaryIndexTree)
{
    auto result = 0;
    while (rank > 0) { // Search the current rank and all lower ranks
        result += binaryIndexTree[rank - 1]; // Sum any value found into result
        rank -= (rank & -rank);
    }
    return result;
}

The binary index tree is obviously O(nklogn), but it is the ability to sequentially fill it out that creates the possibility of using it for a solution.

mapIndex creates a rank for each number in values, such that the smallest number in values has a rank of 1. (For example if values is "2, 3, 4, 3, 4, 1" then mapIndex will contain: "{1, 1}, {2, 2}, {3, 3}, {4, 5}". Note that "4" has a rank of "5" because there are 2 "3"s in values

binaryIndexTree has k different trees, level x would represent the total number of increasing sub-strings that can be formed of length x. Any number in values can create a sub-string of length 1, so each element will increment it's rank and all ranks above it by 1.
At higher levels an increasing sub-string depends on there already being a sub-string available of a shorter length and lower rank.

Because elements are inserted into binary index tree according to their order in values, the order of occurrence in values is preserved, so if an element has been inserted in binaryIndexTree that is because it preceded the current element in values.

An excellent description of how binary index tree is available here: http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/

You can find an executable version of the code here: http://ideone.com/GdF0me

Answer 5

Let us take an example -

Take an array {7, 4, 6, 8}
Now if you consider each individual element also as a subsequence then the number of increasing subsequence that can be formed are -
{7} {4} {6} {4,6} {8} {7,8} {4,8} {6,8} {4,6,8}
A total of 9 increasing subsequence can be formed for this array.
So the answer is 9.

The code is as follows -

int arr[] = {7, 4, 6, 8};
int T[] = new int[arr.length];

for(int i=0; i<arr.length; i++)
    T[i] = 1;    

int sum = 1;     
for(int i=1; i<arr.length; i++){
    for(int j=0; j<i; j++){
        if(arr[i] > arr[j]){
            T[i] = T[i] + T[j]; 
        }
    }
    sum += T[i];
}
System.out.println(sum);

The complexity of the code is O(N log N).

Answer 6

Java version as an example:

    int[] A = {1, 2, 0, 0, 0, 4};
    int[] dp = new int[A.length];

    for (int i = 0; i < A.length; i++) {
        dp[i] = 1;

        for (int j = 0; j <= i - 1; j++) {
            if (A[j] < A[i]) {
                dp[i] = dp[i] + dp[j];
            }
        }
    }