排列

Wu Jun 2020-02-29 14:03:51
01 数据结构与算法 > 算法题 > 回溯搜索

题目出处

字符串的排列

1 题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串 abc,则打印出由字符 a, b, c 所能排列出来的所有字符串 abc, acb, bac, bca, cab 和 cba。结果请按字母顺序输出。

2 解题思路

2.1 递归算法 DFS

递归法,问题转换为先固定第一个字符,求剩余字符的排列;求剩余字符排列时跟原问题一样。

需要注意的几点:

import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
public class Solution {
    public static void main(String[] args) {
        Solution p = new Solution();
        System.out.println(p.Permutation("abc").toString());
    }

    public ArrayList<String> Permutation(String str) {
        ArrayList<String> resultList = new ArrayList<>();
        if(null != str && str.length() > 0){
            backtrack(str.toCharArray(), resultList, 0);
            Collections.sort(resultList);
        }
        return resultList;
    }
     
    private void backtrack(char[] ch, List<String> list, int i){
        //下标 i 移到 char 数组末尾时,添加这一组字符串进入结果集中,递归终止
        if(i == ch.length - 1){
            //判断一下是否重复
            if(!list.contains(String.valueOf(ch))){
                list.add(String.valueOf(ch));
            }
        }else{
            for(int j = i; j < ch.length; j++){
                swap(ch, i, j);
                backtrack(ch, list, i + 1);
                swap(ch, i, j);
            }
        }
    }
     
    private void swap(char[] str, int i, int j) {
        if (i != j) {
            char temp = str[i];
            str[i] = str[j];
            str[j] = temp;
        }
    }
}
复杂性分析

2.2 迭代算法:字典生成算法

一个全排列可看做一个字符串,字符串可有前缀、后缀。

生成给定全排列的下一个排列.所谓一个的下一个就是这一个与下一个之间没有其他的。

这就要求这一个与下一个有尽可能长的共同前缀,也即变化限制在尽可能短的后缀上。

839647521 是 1—9 的排列。1—9 的排列最前面的是 123456789,最后面的 987654321,从右向左扫描若都是增的,就到了 987654321,也就没有下一个了。否则找出第一次出现下降的位置。

如何得到 346987521 的下一个

  1. 从尾部往前找第一个 P(i-1) < P(i) 的位置

    3 4 6 <- 9 <- 8 <- 7 <- 5 <- 2 <- 1
    最终找到 6 是第一个变小的数字,记录下 6 的位置 i-1

  2. 从 i 位置往后找到最后一个大于 6 的数

    3 4 6 -> 9 -> 8 -> 7 5 2 1
    最终找到 7 的位置,记录位置为 m

  3. 交换位置 i-1 和 m 的值

    3 4 7 9 8 6 5 2 1

  4. 倒序 i 位置后的所有数据

    3 4 7 1 2 5 6 8 9
    则 347125689 为 346987521 的下一个排列

public class Solution {
    public ArrayList<String> Permutation(String str) {
       ArrayList<String> res = new ArrayList<>();
 
        if (str != null && str.length() > 0) {
            char[] seq = str.toCharArray();
            Arrays.sort(seq); //排列
            res.add(String.valueOf(seq)); //先输出一个解
 
            int len = seq.length;
            while (true) {
                int p = len - 1, q;
                //从后向前找一个seq[p - 1] < seq[p]
                while (p >= 1 && seq[p - 1] >= seq[p]) --p;
                if (p == 0) break; //已经是“最小”的排列,退出
                //从p向后找最后一个比seq[p]大的数
                q = p; --p;
                while (q < len && seq[q] > seq[p]) q++;
                --q;
                //交换这两个位置上的值
                swap(seq, q, p);
                //将p之后的序列倒序排列
                reverse(seq, p + 1);
                res.add(String.valueOf(seq));
            }
        }
 
        return res;
    }
     
    public static void reverse(char[] seq, int start) {
        int len;
        if(seq == null || (len = seq.length) <= start)
            return;
        for (int i = 0; i < ((len - start) >> 1); i++) {
            int p = start + i, q = len - 1 - i;
            if (p != q)
                swap(seq, p, q);
        }
    }
     
    public static void swap(char[] cs, int i, int j) {
        char temp = cs[i];
        cs[i] = cs[j];
        cs[j] = temp;
    }
}

全排列

1 题目描述

给定一个没有重复数字的序列,返回其所有可能的全排列。

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

2 解题思路

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> output = new ArrayList<>();
        
        if(nums.length > 0){
            // convert nums into list since the output is a list of lists
            List<Integer> input = new ArrayList<>();
            for(int num : nums){
                input.add(num);
            }
            backtrack(input, 0, output);
        }
        
        return output;
    }
    
    public void backtrack(List<Integer> input, int first, List<List<Integer>> output){
        
        // if all integers are used up
        if(first == input.size()){
            output.add(new ArrayList<>(input));
        }else{
            for(int i = first; i < input.size(); i++){
                // place i-th integer first 
                // in the current permutation
                Collections.swap(input, first, i);
                // use next integers to complete the permutations 
                backtrack(input, first + 1, output);
                // backtrack
                Collections.swap(input, i, first);
            }
        }
    }
}

全排列 II

1 题目描述

给定一个可包含重复数字的序列,返回所有不重复的全排列。

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

2 解题思路

和 46.全排列 的区别是考虑重复,但这是数字不是字符串,比较数字数组的重复比较麻烦,所以考虑在生成过程中就避免重复——在一定会产生重复结果集的地方剪枝。

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

public class Solution {

    public List<List<Integer>> permuteUnique (int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        ArrayList<Integer> curList = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(curList, ans, visited, nums);
    
        return ans;
    }
    /**
     * 回溯法
     * @param curList 当前正在处理的字符串
     * @param permutations 排列组合结果集合
     * @param visited 标记当前递归链已经访问过的元素
     * @param nums 给定数组
     */
    private void backtrack (List<Integer> curList,
                            List<List<Integer>> permutations,
                            boolean[] visited,
                            int[] nums) {
        if (curList.size() == nums.length) {
            permutations.add(new ArrayList<>(curList));
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1]){
                    continue;
                }
                if (visited[i]) {
                    continue;
                }
                visited[i] = true;
                curList.add(nums[i]);
                backtrack(curList, permutations, visited, nums);
                curList.remove(curList.size() - 1);
                visited[i] = false;
            }
        }
    }
}

全排列进阶

1 题目描述

给出从 1 开始递增的整数数组长度 n,求数组的全排列第 k 行的值

2 解题思路

由 k 取余,得到第 k 行应该是在哪个数开头的那几行中,再递归计算