CODEWITHSUNDEEP
c++algorithm
Krzysztof Lewko
Krzysztof Lewko

Reputation: 1002

Ascending subsequences in permutation

With given permutation 1...n for example 5 3 4 1 2 how to find all ascending subsequences of length 3 in linear time ?

Is it possible to find other ascending subsequences of length X ? X

I don't have idea how to solve it in linear time.

Upvotes: 3

Views: 609

Answers (2)

btilly
btilly

Reputation: 46408

Do you need the actual ascending sequences? Or just the number of ascending subsequences?

It isn't possible to generate them all in less than the time it takes to list them. Which, as has been pointed out, is O(NX / (X-1)!). (There is a possibly unexpected factor of X because it takes time O(X) to list a data structure of size X.) The obvious recursive search for them scales not far from that.

However counting them can be done in time O(X * N2) if you use dynamic programming. Here is Python for that.

counts = []
answer = 0
for i in range(len(perm)):
    inner_counts = [0 for k in range(X)]
    inner_counts[0] = 1
    for j in range(i):
        if perm[j] < perm[i]:
            for k in range(1, X):
                inner_counts[k] += counts[j][k-1]
    counts.add(inner_counts)
    answer += inner_counts[-1]

For your example 3 5 1 2 4 6 and X = 3 you will wind up with:

counts = [
    [1, 0, 0],
    [1, 1, 0],
    [1, 0, 0],
    [1, 1, 0],
    [1, 3, 1],
    [1, 5, 5]
]
answer = 6

(You only found 5 above, the missing one is 2 4 6.)

It isn't hard to extend this answer to create a data structure that makes it easy to list them directly, to find a random one, etc.

Upvotes: 2

hugomg
hugomg

Reputation: 69944

You can't find all ascending subsequences on linear time because there may be much more subsequences than that.

For instance in a sorted original sequence all subsets are increasing subsequences, so a sorted sequence of of length N (1,2,...,N) has N choose k = n!/(n-k)!k! increasing subsequences of length k.

Upvotes: 1

Related Questions