排列Javascript

一尘不染

排列Javascript

algorithm

所以我现在有了这段代码，在输入中，我的名字字母“ 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>

阅读 257

2020-07-28

共1个答案

一尘不染

这是我从以下答案中得出的解决方案:

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("");
}

该算法很容易理解：

我们想要一个permute类型的函数[a] -> [[a]]（即给定一个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]])

旧的解释：

首先，我们删除列表的第一个元素。因此，我们有item 1和list [2, 3]。
1. 接下来，我们找到的排列[2, 3]。
2. 我们删除第一个元素。因此，我们有item 2和list [3]。
  1. 接下来，我们找到的排列[3]。
  2. 我们删除第一个元素。因此，我们有item 3和list []。
    1. 接下来，我们找到的排列[]是[[]]。
  3. 我们添加3到每个排列的开头。
  4. 结果是[[3]]。
  5. 我们添加2到每个排列的开头。
  6. 结果是[[2, 3]]。
3. 我们删除第二个元素。因此，我们有item 3和list [[2]]。
  1. 接下来，我们找到的排列[2]。
  2. 我们删除第一个元素。因此，我们有item 2和list []。
    1. 接下来，我们找到的排列[]是[[]]。
  3. 我们添加2到每个排列的开头。
  4. 结果是[[2]]。
  5. 我们添加3到每个排列的开头。
  6. 结果是[[3, 2]]。
4. 我们将两个两个列表合并。
5. 结果是[[2, 3], [3, 2]]。
6. 我们添加1到每个排列的开头。
7. 结果是[[1, 2, 3], [1, 3, 2]]。
第二个元素相同：item 2和list [1, 3]。
第三个元素相同：item 3和list [1, 2]。
我们将三个列表结合在一起。
结果是[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]。

观看演示：

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("");

}

希望有帮助。

2020-07-28