html - Permutation Javascript

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

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

Share Improve this question asked Oct 22, 2014 at 11:30 Markus Hayner 631 silver badge9 bronze badges

The algorithm for string permutation is going to be recursive (simplest). – dfsq Commented Oct 22, 2014 at 11:36
It is going to show all binations of those letters – Markus Hayner Commented Oct 22, 2014 at 11:39
Give me few minutes to code it.. – dfsq Commented Oct 22, 2014 at 11:40
1 Here is an algorithm stackoverflow./a/14008544/949476. Let me know if you want help implementing it, I got it working (seems to me). – dfsq Commented Oct 22, 2014 at 11:42
possible duplicate of Java permutation alghorithm – Vincent van der Weele Commented Oct 22, 2014 at 11:48

| Show 6 more ments

3 Answers 3

Sorted by: Reset to default 3

This is my solution from the following answer: https://stackoverflow./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:

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).
Given the empty list ([]) an an input, the output is an empty list of permutations ([[]]).
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:

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 [].
        
        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 [].
        
        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 bine 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]].
Same for the second element: item 2 and list [1, 3].
Same for the third element: item 3 and list [1, 2].
We bine the three lists.
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.

Algorithm for string permutation will be a little bit more plicated with recursive step (it's possible to code it without recursion though).

The next javascript implementation is based on the description of the algorithm from this answer:

Remove the first letter

Find all the permutations of the remaining letters (recursive step)

Reinsert the letter that was removed in every possible location.

Implementation then something like this:

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'));

Above implementation gives 5040 binations, which seems to be correct, since 7! == 5040 (number of permutations is a factorial of the number of chars).

Now when you have all possible permutations array you can easily find specific string occurrence:

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

Well, 'mariush' is actually permutation 2220 if we are using your ordering scheme:

/*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

科技改变生活-雨落星辰 - 所有的伟大,都源于一个勇敢的开始

html - Permutation Javascript - Stack Overflow

3 Answers 3

与本文相关的文章

评论列表(0)