Permutation Javascript

本文关键字：Javascript Permutation 更新时间：2023-09-26

所以我现在有了这个代码，在输入中，我的名字的字母"ahimrsu"按升序排列。我需要显示所有组合中"mariush"的正确数字，应该是2170。现在它只显示ahimrsu，ahimrus，ahimsru，ahimsur，ahimurs，ahimusr，ahirmus，ahirmsu。。。。等等我该怎么做？

<!DOCTYPE HTML>
<html>
<head>
<!--Script Function Start Here-->
<script type="text/javascript">
        function perms(data) {
    if (!(data instanceof Array)) {
        throw new TypeError("input data must be an Array");
    }
    data = data.slice();  // make a copy
    var permutations = [],
        stack = [];
    function doPerm() {
        if (data.length == 0) {
            permutations.push(stack.slice());
        }
        for (var i = 0; i < data.length; i++) {
            var x = data.splice(i, 1);
            stack.push(x);
            doPerm();
            stack.pop();
            data.splice(i, 0, x);
        }
    }
    doPerm();
    return permutations;
}
var input = "ahimrsu".split('');
var result = perms(input);
for (var i = 0; i < result.length; i++) {
    result[i] = result[i].join('');
}
console.log(result);
</script>
<!--Header start here-->
</head>
<body>
<!--Script Result-->
<script type="text/javascript">
        document.write(result);
</script>
</body>
</html>

这是我根据以下答案得出的解决方案：https://stackoverflow.com/a/18879232/783743

var permute = (function () {
    return permute;
    function permute(list) {
        return list.length ?
            list.reduce(permutate, []) :
            [[]];
    }
    function permutate(permutations, item, index, list) {
        return permutations.concat(permute(
            list.slice(0, index).concat(
            list.slice(index + 1)))
            .map(concat, [item]));
    }
    function concat(list) {
        return this.concat(list);
    }
}());

您可以使用permute函数来查找数组的所有排列：

var array = "ahimrsu".split("");
var permutations = permute(array).map(join);
var index = permutations.indexOf("maruish");
function join(array) {
    return array.join("");
}

算法很容易理解：

我们想要类型为[a] -> [[a]]的函数permute（即，给定as的列表，它返回输入的排列列表）
给定空列表（[]）是一个输入，输出是一个空的排列列表（[[]]）
否则，对于每个元素：
1. 我们从列表中删除该元素
2. 我们递归地找到剩余元素的排列
3. 我们将移除的元素添加到每个排列的开头

例如，假设我们想找到数组[1, 2, 3]:的排列

1. permute([1, 2, 3]) === [1, 2, 3].reduce(permutate, [])
    1. permutate([], 1, 0, [1, 2, 3])
        1. permute([2, 3]) === [2, 3].reduce(permutate, [])
            1. permutate([], 2, 0, [2, 3])
                1. permute([3]) === [3].reduce(permutate, [])
                    1. permutate([], 3, 0, [3])
                        1. permute([]) === [[]]
                        2. [[]].map(concat, [3]) === [[3]]
                        3. [].concat([[3]]) === [[3]]
                2. [[3]].map(concat, [2]) === [[2, 3]]
                3. [].concat([[2, 3]]) === [[2, 3]]
            2. permutate([[2, 3]], 3, 1, [2, 3])
                1. permute([2]) === [2].reduce(permutate, [])
                    1. permutate([], 2, 0, [2])
                        1. permute([]) === [[]]
                        2. [[]].map(concat, [2]) === [[2]]
                        3. [].concat([[2]]) === [[2]]
                2. [[2]].map(concat, [3]) === [[3, 2]]
                3. [[2, 3]].concat([[3, 2]]) === [[2, 3], [3, 2]]
        2. [[2, 3], [3, 2]].map(concat, [1]) === [[1, 2, 3], [1, 3, 2]]
        3. [].concat([[1, 2, 3], [1, 3, 2]]) === [[1, 2, 3], [1, 3, 2]]
    2. permutate([[1, 2, 3], [1, 3, 2]], 2, 1, [1, 2, 3])
        1. permute([1, 3]) === [1, 3].reduce(permutate, [])
        2. [[1, 3], [3, 1]].map(concat, [2]) === [[2, 1, 3], [2, 3, 1]]
        3. [[1, 2, 3], [1, 3, 2]].concat([[2, 1, 3], [2, 3, 1]])
    3. permutate([[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]], 3, 2, [1, 2, 3])
        1. permute([1, 2]) === [1, 2].reduce(permutate, [])
        2. [[1, 2], [2, 1]].map(concat, [3]) === [[3, 1, 2], [3, 2, 1]]
        3. [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]].concat([[3, 1, 2], [3, 2, 1]])

旧解释：

首先，我们删除列表的第一个元素。因此，我们有项目1和列表[2, 3]。
1. 接下来我们找到了CCD_ 10的置换。
  1. 我们去掉第一个元素。因此，我们有项目2和列表[3]。
    1. 接下来我们找到了CCD_ 13的置换。
      1. 我们去掉第一个元素。因此，我们有项目3和列表[]。
        接着我们找到了CCD_ 16的置换，即CCD_
      2. 我们将CCD_ 18添加到每个排列的开头
      3. 结果是CCD_ 19
    2. 我们将2添加到每个排列的开头
    3. 结果是CCD_ 21
  2. 我们去掉第二个元素。因此，我们有项目3和列表[[2]]。
    1. 接下来我们找到了CCD_ 24的置换。
      1. 我们去掉第一个元素。因此，我们有项目2和列表[]。
        接下来我们找到了CCD_ 27的置换，即CCD_
      2. 我们将CCD_ 29添加到每个排列的开头
      3. 结果是CCD_ 30
    2. 我们将3添加到每个排列的开头
    3. 结果是CCD_ 32
  3. 我们把这两份清单合并在一起
  4. 结果是CCD_ 33
2. 我们将CCD_ 34添加到每个排列的开头
3. 结果为CCD_ 35
第二个元素相同：项目2和列表[1, 3]
第三个元素相同：项目3和列表[1, 2]
我们把这三个清单合并在一起
结果为CCD_ 40

查看演示：

var permute = (function () {
    return permute;
    function permute(list) {
        return list.length ?
            list.reduce(permutate, []) :
            [[]];
    }
    function permutate(permutations, item, index, list) {
        return permutations.concat(permute(
            list.slice(0, index).concat(
            list.slice(index + 1)))
            .map(concat, [item]));
    }
    function concat(list) {
        return this.concat(list);
    }
}());
var array = "ahimrsu".split("");
var permutations = permute(array).map(join);
var index = permutations.indexOf("maruish");
alert("maruish is the " + (index + 1) + "th permutation of ahimrsu.");
function join(array) {
    return array.join("");
}

希望能有所帮助。

字符串排列的算法使用递归步骤会稍微复杂一点（不过可以在不使用递归的情况下进行编码）。

下一个javascript实现是基于以下答案的算法描述：

删除第一个字母

查找其余字母的所有排列（递归步骤）

在所有可能的位置重新插入已删除的信件

实现方式如下：

function permutation(str) {
    if (str.length == 1) {
        return [str];
    }
    var first = str[0],  // Step #1
        perms = permutation(str.slice(1)), // Step #2
        result = [];
    // Step #3
    for (var i = 0; i < perms.length; i++) {
        for (var j = 0; j <= perms[i].length; j++) {
            result.push( perms[i].slice(0, j) + first + perms[i].slice(j) );
        }
    }
    return result;
}
console.log(permutation('ahimrsu'));

上面的实现给出了5040个组合，这似乎是正确的，因为7！==5040（排列数是字符数的阶乘）。

现在，当你有了所有可能的排列数组，你可以很容易地找到特定的字符串出现：

var combinations = permutation('ahimrsu'); 
var index = combinations.indexOf('mariush'); // Index of the "mariush"
alert('"mariush" is the ' + (index + 1) + 'th permutation of "ahimrsu".');

如果我们是使用您的订购方案：

/*jslint white: true*/
var perm = function(s){
    'use strict';
    if(s.length === 1){
        return [s];
    }
    // For each character c in s, generate the permuations p of all
    // the other letters in s, prefixed with c.
    return [].reduce.call(s, function(p,c,i){ // permutations, char, index
        var other = s.slice(0,i) + s.slice(i+1);
        return p.concat(perm(other).map(function(oneperm){
            return c + oneperm;
        }));
    }, []);
};
alert(perm('ahimrsu').indexOf('mariush') + 1); // 2220