Permutation Javascript

Question

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>

The algorithm for string permutation is going to be recursive (simplest). — dfsq
– dfsq, Commented Oct 22, 2014 at 11:36
Here is an algorithm stackoverflow.com/a/14008544/949476. Let me know if you want help implementing it, I got it working (seems to me). — dfsq
– dfsq, Commented Oct 22, 2014 at 11:42

Community · Accepted Answer · 2017-05-23 12:15:10Z

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

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

What I can't understand is where I shoud to insert var array = "ahimrsu".split(""); var permutations = permute(array); var index = permutations.indexOf("maruish");

Community · Accepted Answer · 2017-05-23 11:59:22Z

3

Algorithm for string permutation will be a little bit more complicated 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 combinations, 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 combinations = permutation('ahimrsu'); 
var index = combinations.indexOf('mariush'); // Index of the "mariush"
alert('"mariush" is the ' + (index + 1) + 'th permutation of "ahimrsu".');

edited May 23, 2017 at 11:59

CommunityBot

11 silver badge

answered Oct 22, 2014 at 12:00

dfsq

193k26 gold badges244 silver badges261 bronze badges

5 Comments

Markus Hayner Over a year ago

It is going to do same thing as mine. Maybe I don't explain correctly. between "ahimrsu" and "usmhira" you can have 5040 combinations notated with 0 for ahimrsu, 1 for ahimrus, 2 for ahimsru, 3 for ahimsur etc. 2170 is for mariush. I need to show that mariush is in 2170 position.

dfsq Over a year ago

If you need to find a position of specific string in the array you should use indexOf method. Like var combinations = permutation('ahimrsu'); var mariush = combinations.indexOf('mariush').

Markus Hayner Over a year ago

where shoud to be placed those 2 lines?

Aadit M Shah Over a year ago

Good answer. Simple explanations are the best.

1983 Over a year ago

@dfsq Nice answer, but different ordering scheme to the OP, if that matters.

1983 · Accepted Answer · 2014-10-22 16:07:59Z

1

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

edited Oct 22, 2014 at 16:07

answered Oct 22, 2014 at 14:43

1983

5,9832 gold badges30 silver badges39 bronze badges

1 Comment

dfsq Over a year ago

Nice usage of reduce!

Collectives™ on Stack Overflow

Permutation Javascript

3 Answers 3

2 Comments

5 Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

5 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related