6
\$\begingroup\$

Given a shape, get all triangles that can be possible by connecting the points.

Example: given 3 points, only 1 triangle is possible, but given a pentagon, 10 are possible.

Also the combination formula is \$\dfrac{n!}{r!(n-r)!}\$. Does it mean \$O(n!)\$ is the complexity?

Looking for:

  1. Code review optimization and best practices.
  2. Verifying complexity:

    Time: \$O\left(\dfrac{n!}{r! (n-r)!}\right)\$ - which I guess is the same as \$O(n!)\$.

    Space: \$O\left(\dfrac{n!}{r! (n-r)!} \cdot r\right)\$ - space occupied by the list to be returned.

public final class GetTriangles {

    private GetTriangles() {}

    /**
     * Returns the list of all the triangles possible, given the input shape.
     * If the less than three points are returned it causes illegal argument exception
     */
    public static List<int[]> combinate (int n) {
        if (n < 3) throw new IllegalArgumentException("The input shape has less than 3 points:  " + n);
        final List<int[]> list = new ArrayList<int[]>();
        for (int i = 1; i < n - 1; i++) {
            compute(i, new int[3], 0, n, list);
        }
        return list;
    }

    private static void compute(int startFrom, int[] a, int arrPosition, int n, List<int[]> list) {
        if (arrPosition == a.length - 1) {
            a[arrPosition] = startFrom; 
            list.add(Arrays.copyOf(a, a.length));
            return;
        }

        a[arrPosition] = startFrom; 

        for (int i = startFrom + 1; i <= n; i++) {
            compute(i, a, arrPosition + 1, n, list);
        }
    }

    public static void main(String[] args) { 
       final List<int[]> list = combinate(5);

       int[] a1  = {1, 2, 3};
       int[] a2  = {1, 2, 4};
       int[] a3  = {1, 2, 5};
       int[] a4  = {1, 3, 4};
       int[] a5  = {1, 3, 5};
       int[] a6  = {1, 4, 5};
       int[] a7  = {2, 3, 4};
       int[] a8  = {2, 3, 5};
       int[] a9  = {2, 4, 5};
       int[] a10 = {3, 4, 5};

       final List<int[]> list1 = Arrays.asList(a1, a2, a3, a4, a5, a6, a7, a8, a9, a10);

       for (int i = 0; i < list.size(); i++) {
           assertArrayEquals(list.get(i), list1.get(i));
       }
    }
}
\$\endgroup\$
  • \$\begingroup\$ ... but given a polygon 10 are possible" <- makes little sense... what polygon? \$\endgroup\$ – rolfl May 12 '14 at 20:21
  • \$\begingroup\$ oops - goofed pentagon with polygon. Sorry \$\endgroup\$ – JavaDeveloper May 12 '14 at 20:46
  • \$\begingroup\$ @rolfl implemented optimistic recursion as you suggested in one of previous reviews :) thanks \$\endgroup\$ – JavaDeveloper May 12 '14 at 21:32
  • \$\begingroup\$ I don't think your test is great, because it expects a particular order for the result, and there is nothing in the problem that requires any particular order. \$\endgroup\$ – Thomas Andrews Jul 28 '15 at 20:20
5
\$\begingroup\$

No, it doesn't mean \$O(n!)\$ complexity. The \$(n-r)\$ in the denominator cancels most of the terms in the numerator. For choosing three points to make a triangle, \$r\$ = 3, and so your actual expression is \$\frac{(n)(n-1)(n-2)}{3!}\$ => \$\frac{(n^3-3n^2+2n)}{3!}\$ => \$O(n^3)\$.

So you should expect \$O(n^3)\$ time, and \$O(3*n^3)\$ => \$O(n^3)\$ space.

Next thought - if you are going to be working with triangles, you need to know where the points are (so that you can check whether or not the points are co-linear). What your code currently does is seek out every 3-tuple combination of vertices; so you are (possibly) missing part of the problem.

That said, breaking the triangle problem into two distinct pieces is a good idea; because you do need to enumerate the vertices anyway, and treating them as ordered tuples gives you a good way to avoid extra work.

But trying to enumerate the tuples using recursion... that's a bad idea. Better would be to simply enumerate the combinations using squashed ordering. Thomas Andrews has a nice illustration of that technique on a more complicated problem.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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