Extracting length-3 subsequences from a list For a list li, I want to print only the values of the triplets a, b, c where 0 &lt;= index(a) &lt; index(b) &lt; index(c) &lt; 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 &lt; j &lt; 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 &lt; j &lt; 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).
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 &lt; j &lt; 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 &lt; j &lt; 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