String Permuter

This is a string permutation generator application written in HTML and JavaScript. You can type in a word with a maximum length of 10 characters into the input field.
The application generates all character combinations of the input string value in a list field.

Online-Version: https://nowca.github.io/string-permuter/string-permuter.html

Using the HTML5 Web Worker API

The Application uses the Web Worker API to run the algorithm code asynchronous in the background of the HTML/JavaScript application.

Algorithm code script

The Web Worker function with the permutation algorithm is called by the event handler function self.onmessage

169 | <script id="webworker-script" type="javascript/worker">
170 |     self.onmessage = function(event) {
... |

The permutation algorithm code returns the generated list to the program script with self.postMessage()

203 | self.postMessage(permutation_array.join('\n'));

Termination of the calculation in the Web Worker thread

The calculation of the permutation can be canceled by terminating the Web Worker Process with the Cancel Button which calls the webWorkerInstance.terminate()

There is a known Bug in Firefox and Chromium which keeps the Web Worker function broken after terminating the thread.

As a workaround the Web Worker Object is instantiated new after each termination with the function call webWorkerInstance.start(), which creates a new text-blob-buffer-object of the script-code, reinstantiates its own object-instance and updates all necessary functions.

325 | webWorkerInstance.start = (function startNewWebWorker()
326 | {
...
332 |     webWorkerInstance = new Worker(
...
348 |     webWorkerInstance.start = this.start;
349 | })

The Permutation Calculator Algorithm

Implemented Permutation Algorithm

The HTML/JS Application is using a recursive permutation algorithm by mixing the characters of a string to all possible constallation values.
(e.g. abc -> acb, bac, bca, cab, cba)

function permute(input)
{
    var i, char, chars = input.split("");

    for (i = 0; i < chars.length; i++)
    {
        char = chars.splice(i, 1);
        used_chars.push(char);

        if (chars.length == 0)
        {
            permutation_array[permutation_array.length] = used_chars.join("");
        }

        permute(chars.join(""));
        chars.splice(i, 0, char);
        used_chars.pop();
    }
}

The original source code of the Permutation Calculator can be found at: https://staff.roguecc.edu/JMiller/JavaScript/permute.js

Explanation of the Algorithm Process:

The calculation is called by

364 |  webWorkerInstance.postMessage(elements.inputField.value);

The called Web Worker thread runs the algorithm script with the input word

234 |  permute(message.data);

The visualisation plot is generated with graphviz dot.
You can find the .dot-file in the doc folder of the repository.

e.g. permute("abc") is processed like this:

permute("abc")
    > permute("bc")
        > permute("c")
            > permute("")
        > permute("b")
            > permute("")
    > permute("ac")
        > permute("c")
            > permute("")
        > permute("a")
            > permute("")
    > permute("ab")
        > permute("b")
            > permute("")
        > permute("a")
            > permute("")

So there are 16 function calls for "abc"

Complexity and number of function calls

The algorithm complexity is factorial O(n!) for combinatorical permutation.

A string with 10 characters would give out "10! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 = 3628800" (more than 3 x 10^6 or 3 million combinations)

(This means it can take a long while to calulcate all the possible values of the string, if it has too many characters.)

For calculation of function calls you can use the formula k of n elements without order and repeat if you need to.

Data Export

It is possible to save the generated permutation data as a generated text file.