# 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 <= 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).

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

• I've made quite a few test cases and it works for all of them. But thanks for affirming what I asked for. It would be interesting to see how you got to that number minimum time complexity. Commented Jan 21, 2015 at 2:15
• The explanation of how you applied the combination formula is greatly appreciated! Commented Jan 21, 2015 at 13:12