4
\$\begingroup\$

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?

\$\endgroup\$
  • 3
    \$\begingroup\$ There are n! permutations of n numbers. Just to print them, the code shall have an \$O(n!)\$ complexity; if it exhibits \$O(n^3)\$ it must be wrong. \$\endgroup\$ – vnp Nov 3 '14 at 6:46
8
\$\begingroup\$
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;
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Brythan: Great explanation. Your analysis of algorithm and structure of code was amazing. Thanks much! \$\endgroup\$ – chmod766 Nov 3 '14 at 22:00

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.