置换的Javascript [英] Permutation Javascript

查看：183
本文介绍了置换的Javascript的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

所以我有这个code现在，而且在输入我有升序排序我的名字的字母ahimrsu。我需要从所有组合显示正确的号码为mariush这应该是2170目前只显示ahimrsu，ahimrus，ahimsru，ahimsur，ahimurs，ahimusr，ahirmus，ahirmsu ....等我该怎么办这个？

 ＆LT;！DOCTYPE HTML＆GT;

＆LT; HTML＆GT;
＆LT; HEAD＆GT;
＆LT;！ - 脚本函数从这里开始 - ＆GT;
＆LT;脚本类型=文/ JavaScript的＆GT;
        函数烫发（数据）{
    如果（！（数据的instanceof阵列））{
        抛出新类型错误（输入数据必须是一个阵列）;
    }

    数据= data.slice（）; //进行复制
    VAR置换= []，
        堆栈= [];

    功能doPerm（）{
        如果（data.length == 0）{
            permutations.push（stack.slice（））;
        }
        对于（VAR I = 0; I＆LT; data.length;我++）{
            变种X = data.splice（I，1）;
            stack.push（X）;
            doPerm（）;
            stack.pop（）;
            data.splice（ⅰ，0，x）的;
        }
    }

    doPerm（）;
    返回排列;
}

变种输入=ahimrsu.split（''）;
VAR的结果=烫发（输入）;
对于（VAR I = 0; I＆LT; result.length;我++）{
    结果[I] =结果[I]。加入（''）;
}
执行console.log（结果）;
＆LT; / SCRIPT＆GT;
＆LT;！ - 头从这里开始 - ＆GT;
＆LT; /头＆GT;
＆LT;身体GT;
＆LT;！ - 脚本结果 - ＆GT;
＆LT;脚本类型=文/ JavaScript的＆GT;
        文件撰写（结果）;
＆LT; / SCRIPT＆GT;

＆LT; /身体GT;
＆LT; / HTML＆GT;

解决方案

这是从下面的答案我的解决方案：的http：// stackoverflow.com/a/18879232/783743 

  VAR置换=（函数（）{
    返回置换;

    功能置换（名单）{
        返回list.length？
            list.reduce（排列替换，[]）：
            [[]];
    }

    功能排列替换（置换，项目，指标，列表）{
        返回permutations.concat（置换（
            list.slice（0，索引）.concat（
            list.slice（索引+ 1）））
            .MAP（CONCAT，[项目]））;
    }

    功能CONCAT（名单）{
        返回this.concat（名单）;
    }
}（））;

您可以使用置换函数找到一个数组的所有排列：

  VAR阵列=ahimrsu.split（）;
VAR排列=置换（阵列）.MAP（加入）;
VAR指数= permutations.indexOf（maruish）;

功能加入（阵列）{
    返回array.join（）;
}

该算法非常简单易懂：

  1. 我们希望有一个函数置换的类型 [A] - ＆GT; [A]] （即给定的名单 A 的IT返回输入排列的列表）。
  2. 由于空列表（ [] ）的输入，输出排列（一个空列表 [[]] ）。
  3. 否则，对于每一个元素：
    1. 我们从列表中删除的元素。
    2. 我们递归地找到剩余元素的排列。
    3. 我们加入我们拆下来，每次改变的开始元素。

例如，假设我们想找到阵列的排列 [1，2，3] ：

  1。置换（[1，2，3]）=== [1，2，3]。降低（排列替换，[]）
    1.排列替换（[]，1，0，[1，2，3]）
        1.置换（[2,3]）=== [2，3]。降低（排列替换，[]）
            1.排列替换（[]，2，0，[2，3]）
                1.置换（[3]）=== [3]。降低（排列替换，[]）
                    1.排列替换（[]，3,0，[3]）
                        1.置换（[]）=== [[]]
                        2. [[]]。图（concat，则[3]）=== [[3]]
                        3. [] .concat（[[3]]）=== [[3]]
                2. [[3]。图（concat，则[2]）=== [[2，3]]
                3. [] .concat（[[2，3]]）=== [[2，3]]
            2.排列替换（[[2，3]]，3,1，[2，3]）
                1.置换（[2]）=== [2]。降低（排列替换，[]）
                    1.排列替换（[]，2，0，[2]）
                        1.置换（[]）=== [[]]
                        2. [[]]。图（concat，则[2]）=== [[2]]
                        3. [] .concat（[[2]]）=== [[2]]
                2. [[2]]。图（concat，则[3]）=== [[3,2]]
                3. [[2，3]]的concat（[[3，2]]）=== [[2，3]，[3，2]]
        2. [[2，3]，[3，2]]。图（concat，则[1]）=== [[1，2，3]，[1，3，2]]
        3. [] .concat（[[1，2，3]，[1，3，2]]）=== [[1，2，3]，[1，3，2]]
    2.排列替换（[[1，2，3]，[1，3,2]，2，1，[1，2，3]）
        1.置换（[1，3]）=== [1，3]。降低（排列替换，[]）
        2. [[1,3]，[3,1]。图（concat，则[2]）=== [[2，1,3]，[2，3，1]]
        3. [[1，2，3]，[1，3,2]。的concat（[[2，1,3]，[2，3，1]]）
    3.排列替换（[[1，2，3]，[1，3,2]，[2，1,3]，[2，3，1]]，3，2，[1，2，3]）
        1.置换（[1,2]）=== [1，2]。降低（排列替换，[]）
        2. [[1,2]，[2，1]]。图（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. 首先我们删除列表的第一个元素。因此，我们有项目 1 和列表 [2，3] 。
    1. 接下来，我们找到的排列[2，3] 。
      1. 我们删除的第一个元素。因此，我们有项目 2 和列表 [3] 。
        1. 接下来，我们找到的排列[3] 。
          1. 我们删除的第一个元素。因此，我们有项目 3 和列表 [] 。
            1. 接下来我们发现的排列 [] 是 [[]] 。
          2. 我们加入 3 来每个排列的开始。
          3. 的结果是 [3] 。
        2. 我们加入 2 来每个排列的开始。
        3. 的结果是 [2，3]] 。
      2. 我们删除第二个元素。因此，我们有项目 3 和列表 [[2]] 。
        1. 接下来，我们找到的排列[2] 。
          1. 我们删除的第一个元素。因此，我们有项目 2 和列表 [] 。
            1. 接下来我们发现的排列 [] 是 [[]] 。
          2. 我们加入 2 来每个排列的开始。
          3. 的结果是 [[2]] 。
        2. 我们加入 3 来每个排列的开始。
        3. 的结果是 [[3,2]] 。
      3. 我们将二者结合起来两份清单。
      4. 的结果是 [2，3]，[3,2]] 。
    2. 我们加入 1 来每个排列的开始。
    3. 的结果是 [1，2，3]，[1，3，2]] 。
  2. 同为第二个元素：项目 2 和列表 [1,3]
  3. 同为第三个要素：项目 3 和列表 [1，2]
  4. 我们结合了三个列表。
  5. 的结果是 [[1，2，3]，[1，3,2]，[2，1,3]，[2，3，1]，[3,1， 2]，[3，2，1] 。

请参阅演示：

VAR置换=（函数（）{     返回置换;     功能置换（名单）{         返回list.length？             list.reduce（排列替换，[]）：             [[]];     }     功能排列替换（置换，项目，指标，列表）{         返回permutations.concat（置换（             list.slice（0，索引）.concat（             list.slice（索引+ 1）））             .MAP（CONCAT，[项目]））;     }     功能CONCAT（名单）{         返回this.concat（名单）;     } }（））; 变种阵列=ahimrsu.split（）; VAR排列=置换（阵列）.MAP（加入）; VAR指数= permutations.indexOf（maruish）; 警报（maruish是的+（索引+ 1）+ahimrsu的第置换。）; 功能加入（阵列）{     返回array.join（）; }

希望有所帮助。

So I have this code now, and in input I have in ascending order my name's letters "ahimrsu". I need to show up the right number for "mariush" from all combinations which should to be 2170. For now it only show ahimrsu, ahimrus, ahimsru, ahimsur, ahimurs, ahimusr, ahirmus, ahirmsu.... etc How can I do this?

<!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>

解决方案

This is my solution from the following answer: http://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);
    }
}());

You can use the permute function to find all the permutations of an array:

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

function join(array) {
    return array.join("");
}

The algorithm is very simple to understand:

  1. We want a function permute of the type [a] -> [[a]] (i.e. given a list of as it returns a list of permutations of the input).
  2. Given the empty list ([]) an an input, the output is an empty list of permutations ([[]]).
  3. Otherwise for every element:

    1. We remove the element from the list.
    2. We recursively find the permutations of the remaining elements.
    3. We add the element we removed to the beginning of every permutation.

For example, suppose we want to find the permutation of the array [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]])

Old explanation:

  1. First we remove the first element of the list. Hence we have item 1 and list [2, 3].

    1. Next we find the permutations of [2, 3].

      1. We remove the first element. Hence we have item 2 and list [3].

        1. Next we find the permutations of [3].

          1. We remove the first element. Hence we have item 3 and list [].

            1. Next we find the permutations of [] which is [[]].

          2. We add 3 to the beginning of each permutation.
          3. The result is [[3]].

        2. We add 2 to the beginning of each permutation.
        3. The result is [[2, 3]].

      2. We remove the second element. Hence we have item 3 and list [[2]].

        1. Next we find the permutations of [2].

          1. We remove the first element. Hence we have item 2 and list [].

            1. Next we find the permutations of [] which is [[]].

          2. We add 2 to the beginning of each permutation.
          3. The result is [[2]].

        2. We add 3 to the beginning of each permutation.
        3. The result is [[3, 2]].

      3. We combine the two two lists.
      4. The result is [[2, 3], [3, 2]].

    2. We add 1 to the beginning of each permutation.
    3. The result is [[1, 2, 3], [1, 3, 2]].

  2. Same for the second element: item 2 and list [1, 3].
  3. Same for the third element: item 3 and list [1, 2].
  4. We combine the three lists.
  5. The result is [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]].

See the demo:

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

Hope that helps.

这篇关于置换的Javascript的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
前端开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆