Though I like recursions and understand it, I fail to master it! I am stuck with a problem which I know that recursion can solve, but I do not know how.

I have an array of strings like: "hundred", "fifty", "thirtythree" etc. I have 'x' number of places to arrange them but the condition is, the string following in next place should always be lesser than or equal to the string preceding it.

For example: String array: "hundred", "fifty", "thirtythree"

Number of places: 4

Few of the correct possibilities:

  • "hundred, hundred, hundred, fifty"
  • "hundred, hundred, hundred, thirtythree"
  • "hundred, hundred, fifty, fifty"
  • "hundred, hundred, fifty, thirtythree"
  • etc.

Examples of Incorrect possibilities:

  • fifty, hundred, hundred, thirtythree
  • hundred, fifty, hundred, thirtythree

With the best I could think, I created a recursive function where I try to place these strings and then increase the parameters so that the same task is repeated in recursion for rest of the slots. Fiddle here: https://jsfiddle.net/80crqzhu/7/

function invokePermutation()
    var permutation_array = [];
    var currentPositions = {
        row: 0,
        column: 0
    getComponentPermutations (["hundred", "fifty", "thirtythree"], permutation_array, 4, currentPositions);

   var title = document.getElementById('container');
   title.innerHTML = permutation_array.join("<br />");

function getComponentPermutations(modeArray, permutation_array, max_positions, current_positions) {
            // Stopping condition
        if (max_positions === current_positions.column && modeArray.length) {
            current_positions.column = 0; // Reset column
            current_positions.row = current_positions.row + 1; // Move to next row
        for (i = 0; i < modeArray.length; i++) {
            if (0 === current_positions.column) {
                // http://stackoverflow.com/a/29881936/260665
                permutation_array[current_positions.row] = [];
            permutation_array[current_positions.row][current_positions.column] = modeArray[i];

            // Lets move to next position in column
            current_positions.column = current_positions.column + 1;

            // The array which we pass for recursion can only have the current modeArray and items lesser than it. For ex, if currenty iteration has fifty, we have to generate an array with fifty and thirtythree to pass on. It should not have hundred in it!
            var newModeArray = modeArray.slice(i);
            getComponentPermutations(newModeArray, permutation_array, max_positions, current_positions); // Recursion

However, the results are not as what I expect, it does not list out all possibilities.

I am sure my code / algorithm is wrong, but I do not understand what is the right way! Appreciate if someone can help me understand where I am going wrong and how to solve this problem.

  • 1
    "the string following in next place should always be lesser than or equal to the string preceding it" - So, you really only want to sort N items, then? – Kilian Foth May 11 '16 at 14:00
  • @KilianFoth - Thanks for your interest! I do not want to sort, but I want to find out different possibilities like: "hundred, hundred, hundred, fifty", "hundred, hundred, hundred, thirtythree", "hundred, hundred, fifty, fifty", "hundred, hundred, fifty, thirtythree" etc. – Raj Pawan Gumdal May 11 '16 at 14:07
  • Why does "hundred" come before "thirtythree"? "hundred" is lexicographically less than "thirtythree"! – Jörg W Mittag May 11 '16 at 14:39
  • Sorry for the confusion here, you can think of values which those strings hold. hundred=100, fifty=50, thirtythree=33. – Raj Pawan Gumdal May 11 '16 at 14:40

I got it working like this:

function invokePermutation()
    var permutation_array = [];
    getComponentPermutations (["hundred", "fifty", "thirtythree"], 0, [], 4, permutation_array);

   var title = document.getElementById('container');
   title.innerHTML = permutation_array.join("<br />");

function getComponentPermutations(possibilities, current_lowest_possibility_index, current_array_beginning, max_positions, completed_permutations) {
    //if the current array we are building up is the max length, add it to our result set
    if (current_array_beginning.length == max_positions) {
    //we've run out of other possibilities to use, so return
    if (current_lowest_possibility_index >= possibilities.length) {
    //take the current part we are building up and call this for the next possibility to put in the next slot
    getComponentPermutations(possibilities, current_lowest_possibility_index + 1, current_array_beginning, max_positions, completed_permutations);

    //add the current possibility
    var cloned_beginning = current_array_beginning.slice();
    getComponentPermutations(possibilities, current_lowest_possibility_index, cloned_beginning, max_positions, completed_permutations);

Note that this is dependent on your array of possibilities being sorted such that the "higher" values come before the "lower" ones.

This is possibly best to see by using an example of how it builds up the arrays. First, it will start with an empty array as what we have built up so far. Then it is going to run and do the first recursive call until the current possibility is at index 2 (ie. "thirtythree"). Then that first call will just return.

Then we will add that to what we are building up so we have ["thirtythree"]. Then we recurse again, but now with the current state being ["thirtythree"] and the current possibility being "thirtythree". The calls keep happening until we have built an array like this ["thirtythree","thirtythree","thirtythree","thirtythree"]. Then finally the next call goes into the first if block to add that to our result set.

Then this backs up by returning until the current array state is ["thirtythree","thirtythree","thirtythree"] and the next item to use is "fifty". Then ["thirtythree","thirtythree","thirtythree","fifty"] gets added. And so on until the stack has unwound all the way to putting in ["hundred","hundred","hundred","hundred"].

| improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.