# 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<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++)
{
List<Integer> temp = new ArrayList(nestedL);
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?

• 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.
– vnp
Nov 3 '14 at 6:46

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


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

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