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].

next_permutation()

函数 next_permutation()的具体实现见这节 Next Permutation。

  1. // Permutations
  2. // 重新实现 next_permutation()
  3. // 时间复杂度O(n!)，空间复杂度O(1)
  4. public class Solution {
  5.     public List<List<Integer>> permute(int[] nums) {
  6.         List<List<Integer>> result = new ArrayList<>();
  7.         Arrays.sort(nums);
  9.         do {
  10.             ArrayList<Integer> one = new ArrayList<>();
  11.             for (int i : nums) {
  12.                 one.add(i);
  13.             }
  14.             result.add(one);
  15.             // 调用的是 2.1.12 节的 next_permutation()
  16.             // 而不是 std::next_permutation()
  17.         } while(nextPermutation(nums, 0, nums.length));
  18.         return result;
  19.     }
  20.     // 代码来自 2.1.12 节的 next_permutation()
  21.     private static boolean nextPermutation(int[] nums, int begin, int end) {
  22.         // From right to left, find the first digit(partitionNumber)
  23.         // which violates the increase trend
  24.         int p = end - 2;
  25.         while (p > -1 && nums[p] >= nums[p + 1]) --p;
  27.         // If not found, which means current sequence is already the largest
  28.         // permutation, then rearrange to the first permutation and return false
  29.         if(p == -1) {
  30.             reverse(nums, begin, end);
  31.             return false;
  32.         }
  34.         // From right to left, find the first digit which is greater
  35.         // than the partition number, call it changeNumber
  36.         int c = end - 1;
  37.         while (c > 0 && nums[c] <= nums[p]) --c;
  39.         // Swap the partitionNumber and changeNumber
  40.         swap(nums, p, c);
  41.         // Reverse all the digits on the right of partitionNumber
  42.         reverse(nums, p+1, end);
  43.         return true;
  44.     }
  45.     private static void swap(int[] nums, int i, int j) {
  46.         int tmp = nums[i];
  47.         nums[i] = nums[j];
  48.         nums[j] = tmp;
  49.     }
  50.     private static void reverse(int[] nums, int begin, int end) {
  51.         end--;
  52.         while (begin < end) {
  53.             swap(nums, begin++, end--);
  54.         }
  55.     }
  56. }

递归

本题是求路径本身，求所有解，函数参数需要标记当前走到了哪步，还需要中间结果的引用，最终结果的引用。

扩展节点，每次从左到右，选一个没有出现过的元素。

本题不需要判重，因为状态装换图是一颗有层次的树。收敛条件是当前走到了最后一个元素。

代码

  1. // Permutations
  2. // 深搜，增量构造法
  3. // 时间复杂度O(n!)，空间复杂度O(n)
  4. public class Solution {
  5.     public List<List<Integer>> permute(int[] nums) {
  6.         Arrays.sort(nums);
  8.         List<List<Integer>> result = new ArrayList<>();
  9.         List<Integer> path = new ArrayList<>(); // 中间结果
  11.         dfs(nums, path, result);
  12.         return result;
  13.     }
  14.     private static void dfs(int[] nums, List<Integer> path,
  15.                             List<List<Integer>> result) {
  16.         if (path.size() == nums.length) {  // 收敛条件
  17.             result.add(new ArrayList<Integer>(path));
  18.             return;
  19.         }
  21.         // 扩展状态
  22.         for (int i : nums) {
  23.             // 查找 i 是否在path 中出现过
  24.             int pos = path.indexOf(i);
  26.             if (pos == -1) {
  27.                 path.add(i);
  28.                 dfs(nums, path, result);
  29.                 path.remove(path.size() - 1);
  30.             }
  31.         }
  32.     }
  33. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/brute-force/permutations.html