Permutations

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

解法1:用递归的方法,取数组中的一个数放在第一位,然后递归的计算之后剩下的数的组合,与这个第一位的数合并在一起组成一个permutation,然后数再取下一个数,以此类推。
如上例就是先去1放第一位,递归算出剩下的2,3的排列组合,然后取2放第一位,递归算出1,3的组合。然后取3放第一位,再递归计算1,2的排列组合,
代码如下:注意当传递递归的数组时,不能用简单的shallow copy,而需做deep copy,应该用arrayList的copy constructor而尽量避免用.clone

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> input = new ArrayList<Integer>();
        for (int i: num)
        {
            input.add(i);
        }
        if (input.size() == 0)
            return result;
        else
            return getPermute(input);
    }
    
    public ArrayList<ArrayList<Integer>> getPermute(ArrayList<Integer> in)
    {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> next = new ArrayList<Integer>();
        if (in.isEmpty())
        {
            return result;
        }
        else if (in.size() == 1)
        {
            next.add(in.get(0));
            result.add(next);
            return result;
        }
        else
        {
            for (int i = 0; i < in.size(); i++)
            {
                ArrayList<Integer> nextList = new ArrayList<Integer>(in); //copy constructor to make deep copy and pass to recursive function.
                int prefix = nextList.remove(i);
                ArrayList<ArrayList<Integer>> array = getPermute(nextList);
                for (ArrayList<Integer> a : array)
                {
                    a.add(0, prefix);
                    result.add(a);
                }
            }
            return result;
        }
    }
}

Second Submission:
Use arraylist for ease of manipulation

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < num.length; i++) {
            list.add(num[i]);
        }
        return getPerm(list);
    }
    
    public ArrayList<ArrayList<Integer>> getPerm(ArrayList<Integer> list) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (list.size() == 1) {
            ArrayList<Integer> tmp = new ArrayList<Integer>();
            tmp.add(list.get(0));
            res.add(tmp);
            return res;
        }
        for (int i = 0; i < list.size(); i++) {
            int curr = list.get(i);
            list.remove(i);
            for (ArrayList<Integer> l : getPerm(list)) {
                l.add(0, curr);
                res.add(l);
            }
            list.add(i, curr); // put removed element back
        }
        return res;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s