Permutations of any given numbers

I have solved one programming problem where we have to find all the permutations of given numbers.

For example, \$[1,2,3]\$ have the following permutations:

$$[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]$$

I have written the code for it and my code successfully cleared all the tests. But, I am not really sure about its complexity.

public List> permute(int[] num) {
    List> res=new ArrayList>();
    res.add(new ArrayList()); // Add an empty list
    for(int number = 0; number > curr = new ArrayList>();
        for(List nestedL : res)
        {
            for(int j = 0; j  temp = new ArrayList(nestedL);
                curr.add(temp);
                nestedL.remove(j);
            }
        }
        res = new ArrayList>(curr);
    }

   return res;
}

First, look at the algorithm, which suggests that it is a \$O(n^3)\$. But, I am not sure if it it correct. Would somebody like to throw more light on the complexity of this algorithm?

public List> permute(int[] num) {

I'd call num, numbers. In fact, I try to always name collections with a plural. Also, I write names out rather than abbreviate them. It will make things much easier if you ever have to read the code in the future.

List> res=new ArrayList>();

It would be helpful here to explain why res is a list of lists. Why not just a single list? Maybe this would be obvious to me if you came up with a more descriptive name. I'm guessing that res is short for result. I would have probably named it permutations.

res.add(new ArrayList()); // Add an empty list

When commenting, try to say why you are doing things rather than what you are doing. E.g. // Add an empty list so that the middle for loop runs.

This seems odd though. You pass in an int[]. Why not make a list of integer arrays then? If that makes something not work, comment on it so that you don't regress it later.

for(List nestedL : res)
    {

Note that res can contain all the permutations (of which there are \$n!\$). This is what gives you your \$O(n!)\$ time. Note that it's actually \$O(n^3n!)\$ time, but the \$n!\$ eats the \$n^3\$.

for(int j = 0; j < nestedL.size() + 1 ;j++)

This would be better if you pulled the nestedL.size() + 1 out of the comparison.

for(int j = 0, n = nestedL.size() + 1; j < n ; j++)

It seems like you should be able to do a bit better here. There's a lot of list creation and copying, which seems unnecessary.

nestedL.add(j,num[number]);
            List temp = new ArrayList(nestedL);
            curr.add(temp);
            nestedL.remove(j);

Ok, you add an element to a list; then you copy the list; save the copy; finally, you remove the added element from the original list. Why not reorder things like so

List temp = new ArrayList(nestedL);
            temp.add(j, num[number]);
            curr.add(temp);

That saves a remove operation.

This also highlights a problem with the name number. It's not a number from the num array. It's an index to the array. I'd name it either i or index.

public List> permute(int[] numbers) {
    // we use a list of lists rather than a list of arrays 
    // because lists support adding in the middle
    // and track current length
    List> permutations = new ArrayList>();
    // Add an empty list so that the middle for loop runs
    permutations.add(new ArrayList());

    for ( int i = 0; i > current = new ArrayList>();
        for ( List permutation : permutations ) {
            for ( int j = 0, n = permutation.size() + 1; j  temp = new ArrayList(permutation);
                temp.add(j, numbers[i]);
                current.add(temp);
            }
        }
        permutations = new ArrayList>(current);
    }

    return permutations;
}

StackExchange Code Review Q#68716, answer score: 8