Generate permutations of characters in arrays - JavaScript

Question

I'm working on a JavaScript function that will generate permutations of a nested array (let's call it input). I want to do it in a way, that the length of permutations will be of input.length. So, given

var input = [["0", "5", "9"], ["2", "3"], ["0", "5", "4"]];

I'm looking to generate permutations of length 3, containing any of ["0", "5", "9"] as a first character, any of ["2", "3"] as the second character etc.

My main challenge is I don't understand recursion well enough to apply it to the problem at hand. I understand the general principle and can step through a given function in order to understand how it behaves (obviously, the more complex the function is, the longer it takes me to understand it. When I can't wrap my mind around a function, I use sticky notes and map each call using a separate note on my wall. This way I can easier visualize the pattern and usually after stepping through a couple of calls my understanding becomes much better). However, if I were to write the same function that I'm able to understand that way, I would probably struggle.

So I've found a function that generates permutation of a simple string with an intention to modify it in a way so that it handles a nested array and generates desired output.

var permutations = [];
function doPerm(str, arr) {
    if (typeof (str) == 'string') str = str.split('');
    if (str.length == 0) permutations.push(arr.join(''));
    for (var i = 0; i < str.length; i++) {
        var x = str.splice(i, 1);
        arr.push(x);
        doPerm(str, arr);
        arr.pop();
        str.splice(i, 0, x);
    }
}

A modification would add another level on top of the existing function (as from what I imagine "rest" variable would have to be a permutation itself).

However, I'm sure there's a way to simplify the problem. Any guidance or possible solutions to this will be appreciated.

What are you actually trying to achieve? An example of before and after would be nice. — Ori Drori
– Ori Drori, Commented Sep 13, 2015 at 13:46
If I understood your question correctly, given input = [["3, "4"], ["8", "9"], ["5", "6"]]; I want the function to generate output = ["385", "386", "395", "396", "485", "486", "495", "496"]; Thanks! — Patrick
– Patrick, Commented Sep 13, 2015 at 14:30

גלעד ברקן · Accepted Answer · 2015-09-15 03:05:06Z

Here is a recursive solution in JavaScript. I tried to match your words with the appropriate step in the function, see the comments.

function f(input, index, result) {

      // "...the length of permutations will be of input.length"

      if (index == input.length) {
        $("#output").append(JSON.stringify(result) + "<br>"); // output
        return; // terminate this particular thread
      }

      // "containing any of ["0", "5", "9"] as a first character"

      for (var i = 0; i < input[index].length; i++) {

        var copyOfResult = result.slice();
        copyOfResult.push(input[index][i]);

        // "any of ["2", "3"] as the second character etc."

        f(input, index + 1, copyOfResult);

      }
    }

     // start the recursion;

    f([["0", "5", "9"],["2", "3"],["0", "5", "4"]], 0, []);

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<div id="output"></div>

orb · Accepted Answer · 2015-09-14 11:28:36Z

0

Let's try the naive way,

foreach input1 in input[1]
    foreach input2 in input[2]
        foreach input3 in input[3]
            print input1*100 + input2*10 + input3*1

It should be easy to implement and alternate the above code segment to get what you want :)

answered Sep 14, 2015 at 11:28

orb

1752 silver badges14 bronze badges

1 Comment

m69 ''snarky and unwelcoming'' Over a year ago

If I understand the question correctly, the OP wants this to work for different lengths of input, so a fixed number of nested loops won't work.

Collectives™ on Stack Overflow

Generate permutations of characters in arrays - JavaScript

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related