How can I write a recursive function to get an array representing the set of every permutation of values?

0
votes

I want to write a function -- call it setGenerator() -- that accepts two parameters:

  1. An array of possible values
  2. An integer maximum

I want my function to return an array of arrays, representing every possible permutation of the possible values, from sets of size 0 up to sets of the specified maximum.

So no matter what, this function would always at least return an array containing an empty array. But here's a quick example to illustrate what I'm trying to do:

setGenerator(["A", "B", "C"], 2);
// should return:
// [ [], ["A"], ["B"], ["C"], ["A", "A"], ["A", "B"], ["A", "C"], 
// ["B", "A"], ["B", "B"], ["B", "C"], ["C", "A"], ["C", "B"], ["C", "C"] ]

Look at the input and output here in my example. The input says my possible values are the strings A, B, and C, and that I should form sets of size 0 through 2. So the resultant sets returned are:

  • A set of size zero []
  • Sets of size one for each possible value: [A], [B], [C]
  • Sets of size two for every permutation: [A,A], [A,B], [A,C], [B,A], etc.

If I were to have set my maximum to 3, though, then the function should also return all permutation sets of length 3.

I hope that makes sense. Can anyone help me write this in JavaScript? It would have to involve recursion, but I'm getting stuck when thinking about it.

UPDATE: If you read the comments, you'll see that what I'm describing here are not technically permutations. This is actually a much larger set than just permutations. But hopefully the target I'm shooting for here is made clear by my example above. These can perhaps be called permutations with repetition. I think there should be x factorial of them for a given number, but keep in mind I'm asking about all numbers 0 up to x.

2
javascriptrecursionset
We are not here to do your homework. What did you try. – epascarello
It's not homework... I've been out of school for 10 years, hence a little rusty! :) – soapergem
Why ["A","A"], ["B","B"], ["C","C"] are permutations? – Sampath Liyanage
What do you mean why? They are! – soapergem
Type: [javascript] [permutation] into the search box. – epascarello

2 Answers

1
votes

Gave it a try because the problem was interesting.. 

var results = [];

var setGenerator = function(values,max,prefix){
    prefix = typeof prefix !== 'undefined' ? prefix : []; 
    results.push(prefix);
    for (var i = 0; i<values.length; i++){
        var newPrefix = prefix.slice(0);
        newPrefix.push(values[i]);
        if (newPrefix.length <= max)
            setGenerator(values, max, newPrefix);
    }   
};

setGenerator(["A","B","C"],2);
console.log(results);
0
votes

Well, I figured it out. Here's what I ended up doing:

function addPermutationsWithRepetition(aFinalSet, aAllowed, iLength, aTemp) {
    if (typeof aTemp != 'object') {
        aTemp = [];
    }
    if ( aTemp.length >= iLength ) {
        aFinalSet.push(aTemp);
    } else {
        for (var j = 0; j < aAllowed.length; j++) {
            var aTemp2 = JSON.parse(JSON.stringify(aTemp));
            aTemp2.push(aAllowed[j]);
            addPermutationsWithRepetition(aFinalSet, aAllowed, iLength, aTemp2);
        });
    }
}

Then I just have to do this:

var aFinalSet = [];
for (var i = 0; i < iMaximum; i++) {
    addPermutationsWithRepetition(aFinalSet, aAllowed, i);
}