Jeśli jesteś właścicielem tej strony, możesz wyłączyć reklamę poniżej zmieniając pakiet na PRO lub VIP w panelu naszego hostingu już od 4zł!

Permutation algorithm

Permutation algorithm

You might remember me writing several articles explaining different sorting algorithms. I might come back to that series as there are few sorting algorithms I haven’t gone through.

But I wanted to do something else now, this is an interesting algorithm to find all permutations of a string.

Let’s say you have string “bar”. The steps are as follows:

  1. If the string is just a one letter, return it.
  2. Remove the first letter of the string and find all permutations of the new string. Do this recursively.
  3. For each found permutation, insert the remove letter from the previous step at every single position. Add each of these strings as a result.
  4. Return the array of results.

Here is implementation in JavaScript:

function permutations(word) {
    if (word.length <= 1) {
        return [word];
    }

    var perms = permutations(word.slice(1, word.length)),
    char = word[0],
    result = [],
    i;
    perms.forEach(function (perm) {
        for (i = 0; i < perm.length + 1; i += 1) {
            result.push(perm.slice(0, i) + char + perm.slice(i, perm.length));
        }
    });

    return result;
}

Source: http://blog.richardknop.com/2013/10/permutation-algorithm/

<!–
var d = new Date();
r = escape(d.getTime()*Math.random());
document.writeln('’);
//–>

Posted Październik 26th, 2013 in Zend and PHP.

Leave a response: