字符串的全排列

sunny5541 发布于2019-08-23 11:38 / 2187人阅读

摘要：问题输入一个字符串按字典序打印出该字符串中字符的所有排列。如此递归处理，从而得到所有字符的全排列。记斐波那契数列的第位这件事为，则有。其中，表示去掉那个开头字符的剩余字符串的全排列。

问题

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

地址：https://www.nowcoder.com/prac...

递归

思路：从字符串中选出一个字符作为排列的第一个字符，然后对剩余的字符进行全排列。如此递归处理，从而得到所有字符的全排列。

分析：我们可以先根据一个实际的例子想想，怎样才能无遗漏的输出全排列：

两个数就不用说了，对于 ab，只有 ab 和 ba 两种
三个数，比如 abc，我们先分为三种情况，就是 a 开头，b 开头和 c 开头
对于 a 开头的情况，剩下 b 和 c，这就回到了两个数的排列；
对于 b 开头的情况，剩下 a 和 c，这也回到了两个数的排列；
c 开头的情况同理；
四个数，先按照开头分为四种情况，然后按照三个数的排列去处理
……
以此类推

由此可看出，这是一个递归。就好像求斐波那契数列的某一个元素，我们要先求出前面的；要想求出前面的，我们就要求出更前面的。记 “斐波那契数列的第 n 位” 这件事为 F(n)，则有 F(n) = F(n - 1) + F(n - 2)。

类似地，记 “求出 n 个字符串的全排列” 这件事为 P(n)，则有 P(n) = 分别以这n个字符之一开头 + P(n - 1)。其中，P(n - 1) 表示去掉那个开头字符的剩余字符串的全排列。哪怕只有两个字符，比如对于上面例子中的 ab，同样符合这一条结论。

分析：以 "abc" 为例，执行步骤如下：

a 作为开头 -> 求 bc 全排列 -> 得到 bc 和 cb -> 与 a 合并 -> 得到 abc 和 acb
b 作为开头 -> 求 ac 全排列 -> 得到 ac 和 ca -> 与 b 合并 -> 得到 bac 和 bca
c 作为开头 -> 求 ab 全排列 -> 得到 ab 和 ba -> 与 c 合并 -> 得到 cab 和 cba

注：之前递归过程选择的字符，下一次不能再被选。

时间复杂度：O(n！)。

function permutation(str) {
    if(str.length == 0) {
        return [];
    }
    var result = [];
    var sortTemp = "";
    var arr = str.split("");
    // var len = arr.length;
    var result = sortString(arr, sortTemp, result);
    return result;

    function sortString(arr, sortTemp, res) {
        if(arr.length == 0) {
            return res.push(sortTemp);
        } else {
            let isRepeat = {};
            for(let i = 0; i < arr.length; i++) { // 不要用 len
                if(!isRepeat[arr[i]]) {
                    let temp = arr.splice(i, 1)[0]; // i 取出第i个字符作为第一个字符
                    sortTemp += temp;
                    sortString(arr, sortTemp, res); // 固定第一个字符的剩下字符的全排列已完成
                    arr.splice(i, 0, temp); // i 补全 恢复原字符串
                    sortTemp = sortTemp.slice(0, sortTemp.length - 1); // 清空sortTemp: 每次截掉字符串中的最后一个字符
                    isRepeat[temp] = true; // 相同的字符便不再在第一个字符中固定并对剩下的字符进行全排列了
                }
            }    
        }
        return res;
    }
}
permutation("abc")

这里固定字符串数组元素中的第一个字符的方式：是利用数组中splice()方法通过截取出来（删掉一个元素），完成全排列后再将该字符补全回原字符串中splice()（添加元素）的方式。遍历该字符串数组，依次截取掉每个字符元素的方式来作为字符串数组元素的第一个字符。

当然还可以通过依次向后交换的方式、或者取出元素以后向后插入的方式、以及经典的回溯法的方式等等。

References

leetcode题解(递归和回溯法)
July 算法习题 - 字符串4（全排列和全组合）

GPU云服务器云服务器最快的全排列算法字符串全排列字符串全排列算法 html网页的全选

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/97236.html

July 算法习题 - 字符串4（全排列和全组合）

摘要：求字符串的全排列字符串的全排列设计一个算法，输出一个字符串字符的全排列。的做法没有结果的，都是在一个字符串上进行的操作。字符串的全组合输入三个字符，则它们的组合有。因此可以循环字符串长度，然后输出对应代表的组合即可。求字符串的全排列字符串的全排列设计一个算法，输出一个字符串字符的全排列。比如，String = abc 输出是abc,bac,cab,bca,cba,...

tuniutech 2019-08-14 12:11 评论0 收藏0
JS 字符串全排列算法及内存溢出

摘要：问题给定字符串，求出所有由该串内字符组合的全排列。于是我想的办法是利用尾递归优化。算法二尾递归终止条件长度为第一次递归时，插入首字母递归截取了第一个字符的子串函数的第一个参数是本次递归的字符串，第二个参数是前个字符的全排列结果。问题给定字符串，求出所有由该串内字符组合的全排列。所包含的字符不重复。输入：abc 输出：[abc,acb,bac,bca,cab,cba] 我在实现算法...

sihai 2019-08-22 14:56 评论0 收藏0
如何求ABC的全排列？--如何理解回溯算法？

摘要：它真的是深度优先搜索吗是真的吗是真的如果是的话，那它的搜索空间解空间是什么是向量组成的集合，而。既然深度优先搜索剪枝回溯。什么是全排列？从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。那么ABC的全排列有哪些？根据定义得到：ABCACBBACBCACABCBA 如何通过程序求解？方法一：暴力...

zero 2019-08-16 16:22 评论0 收藏0
数字全排列

摘要：数字全排列问题描述给一个不重复的数字数组，写一个程序，输出全排列。那么两个数字的全排列怎么算呢，以为例，就是第一个数字为的剩下的数的全排列第一个数字为的剩下的数的全排列。依次类推到个数字的全排列设数组，设的全排列为，设。数字全排列问题描述给一个不重复的数字数组，写一个程序，输出全排列。比如给定数组： [1, 2, 3] 输出： [1, 2, 3] [1, 3, 2] [2, 1...

zoomdong 2019-08-15 15:54 评论0 收藏0
《剑指offer》分解让复杂问题更简单

摘要：拆分链表，将和进行拆分，保证原始链表不受影响。要求不能创建任何新的结点，只能调整树中结点指针的指向。输入一个字符串长度不超过可能有字符重复字符只包括大小写字母。递归，记录一个当前节点的位置，该位置指向最后一个节点时记录一次排列。 1.复杂链表的复制输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的hea...

wawor4827 2019-08-23 15:27 评论0 收藏0