Given a shape, return all triangles that can be formed

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, 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;
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));
}
}
}
• ... but given a polygon 10 are possible" <- makes little sense... what polygon? – rolfl May 12 '14 at 20:21
• oops - goofed pentagon with polygon. Sorry – JavaDeveloper May 12 '14 at 20:46
• @rolfl implemented optimistic recursion as you suggested in one of previous reviews :) thanks – JavaDeveloper May 12 '14 at 21:32
• 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. – Thomas Andrews Jul 28 '15 at 20:20

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.