4
\$\begingroup\$

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

\$\endgroup\$
0

1 Answer 1

6
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – Bentley4
    Jan 21, 2015 at 2:15
  • \$\begingroup\$ The explanation of how you applied the combination formula is greatly appreciated! \$\endgroup\$
    – Bentley4
    Jan 21, 2015 at 13:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.