LeetCode Online Judge 题目C# 练习 - 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 public static List<List<int>> Permutation(List<int> num) 2 { 3 List<List<int>> ret = new List<List<int>>(); 4 PermutationHelper(ret, num, 0); 5 return ret; 6 } 7 8 public static void PermutationHelper(List<List<int>> ret, List<int> num, int index) 9 { 10 if (index == num.Count - 1) 11 ret.Add(new List<int>(num)); 12 else 13 { 14 for (int i = index; i < num.Count; i++) 15 { 16 PermutationSwap(num, index, i); 17 PermutationHelper(ret, num, index + 1); 18 PermutationSwap(num, index, i); //remember this!!! 19 } 20 } 21 } 22 23 public static void PermutationSwap(List<int> num, int i, int j) 24 { 25 int temp = num[i]; 26 num[i] = num[j]; 27 num[j] = temp; 28 }
代码分析:
这也应该是必须复习的题目了,求所有的排列组合。
这个是递归的做法,思想是把每一个元素都放到第一个位置(做法是第一个元素与所有后面的元素都交换一次,当然第一次是跟自己交换),然后递归下去求从第二个位置开始的所以排列组合。
例如:
记住要递归玩之后swap back,不然就乱了套,结果会出现重复。
复习的时候想应该有DP的做法。
1 public static List<List<int>> PermutationDP(List<int> num) 2 { 3 if (num.Count == 0) 4 return null; 5 6 List<List<int>> curr = new List<List<int>>(); 7 List<List<int>> next = new List<List<int>>(); 8 9 curr.Add(new List<int> { num[0] }); 10 for (int i = 1; i < num.Count; i++) 11 { 12 for (int p = 0; p < curr.Count; p++) 13 { 14 List<int> temp = new List<int>(curr[p]); 15 int temp_count = temp.Count; 16 for (int k = 0; k <= temp_count; k++) 17 { 18 temp.Insert(k, num[i]); 19 next.Add(new List<int>(temp)); 20 temp.RemoveAt(k); 21 } 22 } 23 PermutationDPSwap(ref curr, ref next); 24 next.Clear(); 25 } 26 27 return curr; 28 } 29 30 public static void PermutationDPSwap(ref List<List<int>> curr, ref List<List<int>> next) 31 { 32 List<List<int>> temp; 33 temp = curr; 34 curr = next; 35 next = temp; 36 }
代码分析:
DP的做法
例如:
1,2,3
1 的 所有排列组合 : 1
1, 2 的所有排列组合 = (2,1), (1,2) 。 就是用2加到之前所有排列组合的前面, 插入到每个元素之间 (这里没有),加到后面。
1,2, 3 的所有排列组合 = (3,2,1)前面, (2,3,1)之间, (2,1,3)后面, (3,1,2)前面, (1,3,2)之间, (1,2,3) 后面
......
感觉嘛。DP好像好懂,可能是我脑子对递归的抗拒,老觉得自己写不出来递归。在这个CASE, 递归的performance比DP好,可能是因为List的Insert 和 RemoveAt都比较耗性能的,虽然到了11个元素大家都out of memory了。
这里学习到一个东西。C#里面虽然List<List<int>>之类的reference type 传参的时候是pass by reference, 但是其实是一个reference 的copy,
analogous passing a pointer to the object, the pointer get copied, 所以这一调换 curr 和 next 的位置的时候,要用ref 关键字。
转载于:https://www.cnblogs.com/etcow/archive/2012/10/05/2712576.html