Permutations of any given numbers

Question

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<List<Integer>> permute(int[] num) {
    List<List<Integer>> res=new ArrayList<List<Integer>>();
    res.add(new ArrayList<Integer>()); // Add an empty list
    for(int number = 0; number < num.length; number++)
    {
        List<List<Integer>> curr = new ArrayList<List<Integer>>();
        for(List<Integer> nestedL : res)
        {
            for(int j = 0; j < nestedL.size() + 1 ;j++)
            {
                nestedL.add(j,num[number]);
                List<Integer> temp = new ArrayList(nestedL);
                curr.add(temp);
                nestedL.remove(j);
            }
        }
        res = new ArrayList<List<Integer>>(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?

Answer 1

public List<List<Integer>> 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<List<Integer>> res=new ArrayList<List<Integer>>();

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<Integer>()); // 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<Integer> 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<Integer> 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<Integer> 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<List<Integer>> 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<List<Integer>> permutations = new ArrayList<List<Integer>>();
    // Add an empty list so that the middle for loop runs
    permutations.add(new ArrayList<Integer>());

    for ( int i = 0; i < numbers.length; i++ ) {
        // create a temporary container to hold the new permutations 
        // while we iterate over the old ones
        List<List<Integer>> current = new ArrayList<List<Integer>>();
        for ( List<Integer> permutation : permutations ) {
            for ( int j = 0, n = permutation.size() + 1; j < n; j++ ) {
                List<Integer> temp = new ArrayList<Integer>(permutation);
                temp.add(j, numbers[i]);
                current.add(temp);
            }
        }
        permutations = new ArrayList<List<Integer>>(current);
    }

    return permutations;
}