Given a shape, return all triangles that can be formed

Question

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));
 }
 }
}

• rolfl: ... but given a polygon 10 are possible" <- makes little sense... what polygon?
• JavaDeveloper: oops - goofed pentagon with polygon. Sorry
• JavaDeveloper: @rolfl implemented optimistic recursion as you suggested in one of previous reviews :) thanks
• Thomas Andrews: 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.

Answer 1

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.