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, Oct 22 '14 at 11:36
Here is an algorithm http://stackoverflow.com/a/14008544/949476. Let me know if you want help implementing it, I got it working (seems to me). — dfsq, Oct 22 '14 at 11:42
possible duplicate of [Java permutation alghorithm](http://stackoverflow.com/questions/26502895/java-permutation-alghorithm) — Vincent van der Weele, Oct 22 '14 at 11:48
Well, what I need is to show up the number of my word not the word. So how you can see I have 7 letter that means 5040 combinations. If I will start from 0 my word have the number 2170. What I need is to create a new var with my word "MARIUSH" and in result to show me the number for my word. — Markus Hayner, Oct 22 '14 at 11:49
So you just need to calculate factorial, not actual permutations of the string — dfsq, Oct 22 '14 at 11:50
I think thats what I need, I try to explain you how I see this problem. — Markus Hayner, Oct 22 '14 at 11:52
So do you need the number of permutation for the string, or you need actual string permutations (array of strings)? — dfsq, Oct 22 '14 at 11:53
Think like this. I have 3 var: var input = "ahimrsu", var word = "mariush" and var result = "the number of mariush from 5040 combinations" — Markus Hayner, Oct 22 '14 at 11:54
Anyway, I still don't get what you want. But since I have already coded a function that calculates all string permutations I will post it as an example of javascript implementation. If you need just a number you should go with just factorial function (which you already have I guess). — dfsq, Oct 22 '14 at 11:56

score 3 · Answer 1 · edited May 23 '17 at 11:59

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 '17 at 11:59

Community

1
1

answered Oct 22 '14 at 12:00

dfsq

191,768
25
236
258

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. – Markus Hayner Oct 22 '14 at 12:29
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')`. – dfsq Oct 22 '14 at 13:06
where shoud to be placed those 2 lines? – Markus Hayner Oct 22 '14 at 13:47
Good answer. Simple explanations are the best. – Aadit M Shah Oct 22 '14 at 14:38
@dfsq Nice answer, but different ordering scheme to the OP, if that matters. – 1983 Oct 22 '14 at 15:24

score 3 · Accepted Answer · edited May 23 '17 at 12:15

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"); — Markus Hayner, Oct 22 '14 at 13:56

1983 · Answer 3 · 2014-10-22T16:07:59.010

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

Permutation Javascript

3 Answers3

Linked

Related