Extracting length-3 subsequences from a list

Question

For a list li, I want to print only the values of the triplets a, b, c where 0 <= index(a) < index(b) < index(c) < len(li).

Example:

f([6, 3, 88, 4])
6 3  88
6 3  4
6 88 4
3 88 4 

Here is my solution, but it is O(n**3) (time complexity):

def f(li):
    for i, n in enumerate(li):
        for j, o in enumerate(li):
            for k, p in enumerate(li):
                if i < j < k:
                    print n, o, p

However, it should be doable in O(n). Any clues?

I have the following function as well:

def f(li):
    i = 0
    j = i + 1
    k = j + 1
    n = li[i]
    o = li[j]
    p = li[k]
    while i < j < k:
        print n, o, p
        if n == li[-3]:
            break
        if p != li[-1]:
            k += 1
        elif o == li[-2]:
            i += 1
            j = i + 1
            k = j + 1
        elif p == li[-1]:
            j += 1
            k = j + 1

        n = li[i]
        o = li[j]
        p = li[k]

I believe this is O(n).

Answer 1

In any case, the minimum time complexity for a list of length \$n\$ would be $$\mathrm{nCr}(n, 3) = \frac{n!}{3!\ (n-3)!} = \frac{1}{6} n(n - 1)(n - 2)$$ because that is the number of results to expect. That is \$O(n^3)\$.

Explanation of the combination formula:

Let's ignore the i < j < k requirement for now. How many ways are there to pick one element? (There are \$n\$ ways.) How many ways are there to pick the next element from the remaining \$n-1\$ elements? (For each of the \$n\$ first picks, there are \$n-1\$ second picks.) How many choices are there for the third element? (There are \$n-2\$.) That means that there are \$n(n-1)(n-2)\$ permutations when picking 3 elements from a list of \$n\$, also written as \$\frac{n!}{(n-3)!}\$.

Now, let's consider the ordering. For any collection of 3 items, how many possible sequences exist? There are 3 choices for the first item, 2 choices for the second item, and 1 obligatory choice for the third. That's \$3!=3\cdot2\cdot1=6\$ orderings. So, out of all the \$n(n-1)(n-2)\$ lists of of \$i, j, k\$, only \$\frac{1}{6}\$ of the them will have \$i, j, k\$ in ascending order.

What you can do, though, is eliminate the conditional, so that every iteration succeeds in producing a result. (Your if i < j < k check succeeds less than \$\frac{1}{6}\$ of the time.) I would also change print to yield for greater flexibility.

def subsequence_triplets(lst):
    end = len(lst)
    for i in range(0, end - 2):
        for j in range(i + 1, end - 1):
            for k in range(j + 1, end):
                yield lst[i], lst[j], lst[k]

for a, b, c in subsequence_triplets([6, 3, 88, 4]):
    print a, b, c