Finding all combinations of input set

Question

A friend and I occasionally come up with some code challenges for each other to help stay sharp. This time he proposed this one, and I thought it would be excellent practice. Doing this one in javascript, I've built a web interface for it already but generating all the possible sequences for the fruits has been tough.

I have done it the cheesy way by creating functions to split up the work for say one element combinations, two element combinations, three element combinations, 4 element combinations and 5 element combinations for nested loops all the way down.

While the above idea does work, it breaks as soon as you add in a 6th input. So is there a way to achieve the same thing for N inputs? I've been trying to find a recursive way to do it, but I've been hitting a hard wall on those attempts so far. Regardless this is a great learning opportunity that I would love some help with!

Input

Your script must prompt the user for the number of fruit, 1 to 5. 
The fruit available to the script for each input selection are as follows:

1 = [Cherry, Lime, Banna]
2 = [Cherry, Lime, Banna, Orange, Apple]
3 = [Cherry]
4 = [Cherry, Lime]
5 = [Cherry, Lime, Banna, Orange]


Output
Your script should generate the list of all possible fruit sequences that could be 
generated for the given input selection from 1 to 5.

Restrictions

1) The script is allowed to use any fruit only once per sequence, or not at all.    
2) The script must generate at least one fruit per sequence.

Sample Input: 4

Sample Output:
[Cherry]
[Lime]
[Cherry][Lime]
[Lime][Cherry]

Do it without any existing libraries like Jquery, ES6 Syntax.

recursiveGenerator = function() {    
    fruitSequences = [];
    fruitRemaining = inputs[selectedInput].slice();    

    arrayBuilder([], fruitRemaining);

    console.log('finshed calculating, resulting fruit sequences');
    console.log(fruitSequences);
}

arrayBuilder = function(array, fruitRemaining) {

    console.log('called arrayBuilder');
    console.log(array, fruitRemaining);

    fruitRemaining.forEach( function(fruit) {
        if (array.indexOf(fruit) === -1) {
            array.push(fruit);
        } else {
            return;
        }        

        if (array.length < fruitRemaining.length) {
            arrayBuilder(array, fruitRemaining);
        } else {
            fruitSequences.push(array);
            fruitRemaining.pop();
        }
    })
}

`I've been hitting a hard wall on those attempts so far` Please post your attempt and we can try to help you get over it — CertainPerformance, Jun 01 '18 at 04:12
*"that I would love some help with"* You haven't asked a specific question though. We don't know what exactly you need help with. If you search StackOverflow for "array permutations" you should find plenty of starting points. E.g. https://stackoverflow.com/q/9960908/218196 — Felix Kling, Jun 01 '18 at 04:12
I just added my recursion attempt which I know fails horribly. It's a concept I've struggled with for a long time. — Nebri, Jun 01 '18 at 04:18
This is basically two problems: Find all subsets of the array, and for each subset find all permutations of it. You can find solutions for each of these on SO, you just need to combine them. — Barmar, Jun 01 '18 at 04:27
I'm not sure I understand the part about colors in the problem description, though. Where are colors in the input data? — Barmar, Jun 01 '18 at 04:28
ah, initially we were using colors as the input. Then we decided to switch it up to fruits thinking it might be more clear. I've quickly edited the question again to fix these errors. Sorry for confusion Barmar. — Nebri, Jun 01 '18 at 04:32

chuckx · Accepted Answer · 2018-06-01T16:36:57.093

It helps to visualize the algorithm. Given the list a b c, these are the combinations we want to generate:

Single character combinations:

a b c
1
a b c
  1
a b c
    1

Two character combinations:

a b c
1 2
a b c
1   2
a b c
  1 2
a b c
2 1
a b c
2   1
a b c
  2 1

Three character combinations:

a b c
1 2 3
a b c
1 3 2
etc.

That can be described as "1 to n" combinations, where n is the length of the list.

One approach in code is with the following pair of functions:

let nCombinations = function(list, numItems) {
    // Requesting more items than the list isn't possible.
    if (list.length < numItems) {
        return [];
    }
    // If requesting 1 item per combination, quickly return a list
    // of single item lists.
    if (numItems == 1) {
        let result = [];
        for (let i = 0; i < list.length; i++) {
            result.push([list[i]]);
        }
        return result;
    }
    // Loop through the list, combining each element with all the
    // permutations of the remaining elements.
    let result = [];
    for (let i = 0; i < list.length; i++) {
        let currentElement = list.slice(i, i + 1);
        let restList = list.slice(0, i).concat(list.slice(i + 1));
        let restCombinations = nCombinations(restList, numItems - 1);
        for (let j = 0; j < restCombinations.length; j++) {
            result.push(
                currentElement.concat(restCombinations[j]));
        }
    }
    return result;
}

let combinations = function(list) {
    let result = [];
    // Loop through the "1 to n" combinations
    for (let i = 1; i <= list.length; i++) {
        i_combinations = nCombinations(list, i);
        for (let j = 0; j < i_combinations.length; j++) {
            result.push(i_combinations[j]);
       }
    }
    return result;
}

Using them with:

const OPTIONS = [
    ['Cherry', 'Lime', 'Banana'],
    ['Cherry', 'Lime', 'Banana', 'Orange', 'Apple'],
    ['Cherry'],
    ['Cherry', 'Lime'],
    ['Cherry', 'Lime', 'Banana', 'Orange']
];

for (var i = 0; i < OPTIONS.length; i++) {
    console.log('Option ' + (i + 1) + ': ' + OPTIONS[i]);
    console.log(combinations(OPTIONS[i]));
}

Produces the following output:

w$ node select-fruits.js
Option 1: Cherry,Lime,Banana
[ [ 'Cherry' ],
  [ 'Lime' ],
  [ 'Banana' ],
  [ 'Cherry', 'Lime' ],
  [ 'Cherry', 'Banana' ],
  [ 'Lime', 'Cherry' ],
  [ 'Lime', 'Banana' ],
  [ 'Banana', 'Cherry' ],
  [ 'Banana', 'Lime' ],
  [ 'Cherry', 'Lime', 'Banana' ],
  [ 'Cherry', 'Banana', 'Lime' ],
  [ 'Lime', 'Cherry', 'Banana' ],
  [ 'Lime', 'Banana', 'Cherry' ],
  [ 'Banana', 'Cherry', 'Lime' ],
  [ 'Banana', 'Lime', 'Cherry' ] ]
Option 2: Cherry,Lime,Banana,Orange,Apple
[ [ 'Cherry' ],
  [ 'Lime' ],
  [ 'Banana' ],
  [ 'Orange' ],
  [ 'Apple' ],
  [ 'Cherry', 'Lime' ],
  [ 'Cherry', 'Banana' ],
  [ 'Cherry', 'Orange' ],
  [ 'Cherry', 'Apple' ],
  [ 'Lime', 'Cherry' ],
  [ 'Lime', 'Banana' ],
  [ 'Lime', 'Orange' ],
  [ 'Lime', 'Apple' ],
  [ 'Banana', 'Cherry' ],
  [ 'Banana', 'Lime' ],
  [ 'Banana', 'Orange' ],
  [ 'Banana', 'Apple' ],
  [ 'Orange', 'Cherry' ],
  [ 'Orange', 'Lime' ],
  [ 'Orange', 'Banana' ],
  [ 'Orange', 'Apple' ],
  [ 'Apple', 'Cherry' ],
  [ 'Apple', 'Lime' ],
  [ 'Apple', 'Banana' ],
  [ 'Apple', 'Orange' ],
  [ 'Cherry', 'Lime', 'Banana' ],
  [ 'Cherry', 'Lime', 'Orange' ],
  [ 'Cherry', 'Lime', 'Apple' ],
  [ 'Cherry', 'Banana', 'Lime' ],
  [ 'Cherry', 'Banana', 'Orange' ],
  [ 'Cherry', 'Banana', 'Apple' ],
  [ 'Cherry', 'Orange', 'Lime' ],
  [ 'Cherry', 'Orange', 'Banana' ],
  [ 'Cherry', 'Orange', 'Apple' ],
  [ 'Cherry', 'Apple', 'Lime' ],
  [ 'Cherry', 'Apple', 'Banana' ],
  [ 'Cherry', 'Apple', 'Orange' ],
  [ 'Lime', 'Cherry', 'Banana' ],
  [ 'Lime', 'Cherry', 'Orange' ],
  [ 'Lime', 'Cherry', 'Apple' ],
  [ 'Lime', 'Banana', 'Cherry' ],
  [ 'Lime', 'Banana', 'Orange' ],
  [ 'Lime', 'Banana', 'Apple' ],
  [ 'Lime', 'Orange', 'Cherry' ],
  [ 'Lime', 'Orange', 'Banana' ],
  [ 'Lime', 'Orange', 'Apple' ],
  [ 'Lime', 'Apple', 'Cherry' ],
  [ 'Lime', 'Apple', 'Banana' ],
  [ 'Lime', 'Apple', 'Orange' ],
  [ 'Banana', 'Cherry', 'Lime' ],
  [ 'Banana', 'Cherry', 'Orange' ],
  [ 'Banana', 'Cherry', 'Apple' ],
  [ 'Banana', 'Lime', 'Cherry' ],
  [ 'Banana', 'Lime', 'Orange' ],
  [ 'Banana', 'Lime', 'Apple' ],
  [ 'Banana', 'Orange', 'Cherry' ],
  [ 'Banana', 'Orange', 'Lime' ],
  [ 'Banana', 'Orange', 'Apple' ],
  [ 'Banana', 'Apple', 'Cherry' ],
  [ 'Banana', 'Apple', 'Lime' ],
  [ 'Banana', 'Apple', 'Orange' ],
  [ 'Orange', 'Cherry', 'Lime' ],
  [ 'Orange', 'Cherry', 'Banana' ],
  [ 'Orange', 'Cherry', 'Apple' ],
  [ 'Orange', 'Lime', 'Cherry' ],
  [ 'Orange', 'Lime', 'Banana' ],
  [ 'Orange', 'Lime', 'Apple' ],
  [ 'Orange', 'Banana', 'Cherry' ],
  [ 'Orange', 'Banana', 'Lime' ],
  [ 'Orange', 'Banana', 'Apple' ],
  [ 'Orange', 'Apple', 'Cherry' ],
  [ 'Orange', 'Apple', 'Lime' ],
  [ 'Orange', 'Apple', 'Banana' ],
  [ 'Apple', 'Cherry', 'Lime' ],
  [ 'Apple', 'Cherry', 'Banana' ],
  [ 'Apple', 'Cherry', 'Orange' ],
  [ 'Apple', 'Lime', 'Cherry' ],
  [ 'Apple', 'Lime', 'Banana' ],
  [ 'Apple', 'Lime', 'Orange' ],
  [ 'Apple', 'Banana', 'Cherry' ],
  [ 'Apple', 'Banana', 'Lime' ],
  [ 'Apple', 'Banana', 'Orange' ],
  [ 'Apple', 'Orange', 'Cherry' ],
  [ 'Apple', 'Orange', 'Lime' ],
  [ 'Apple', 'Orange', 'Banana' ],
  [ 'Cherry', 'Lime', 'Banana', 'Orange' ],
  [ 'Cherry', 'Lime', 'Banana', 'Apple' ],
  [ 'Cherry', 'Lime', 'Orange', 'Banana' ],
  [ 'Cherry', 'Lime', 'Orange', 'Apple' ],
  [ 'Cherry', 'Lime', 'Apple', 'Banana' ],
  [ 'Cherry', 'Lime', 'Apple', 'Orange' ],
  [ 'Cherry', 'Banana', 'Lime', 'Orange' ],
  [ 'Cherry', 'Banana', 'Lime', 'Apple' ],
  [ 'Cherry', 'Banana', 'Orange', 'Lime' ],
  [ 'Cherry', 'Banana', 'Orange', 'Apple' ],
  [ 'Cherry', 'Banana', 'Apple', 'Lime' ],
  [ 'Cherry', 'Banana', 'Apple', 'Orange' ],
  [ 'Cherry', 'Orange', 'Lime', 'Banana' ],
  [ 'Cherry', 'Orange', 'Lime', 'Apple' ],
  [ 'Cherry', 'Orange', 'Banana', 'Lime' ],
  ... 225 more items ]
Option 3: Cherry
[ [ 'Cherry' ] ]
Option 4: Cherry,Lime
[ [ 'Cherry' ],
  [ 'Lime' ],
  [ 'Cherry', 'Lime' ],
  [ 'Lime', 'Cherry' ] ]
Option 5: Cherry,Lime,Banana,Orange
[ [ 'Cherry' ],
  [ 'Lime' ],
  [ 'Banana' ],
  [ 'Orange' ],
  [ 'Cherry', 'Lime' ],
  [ 'Cherry', 'Banana' ],
  [ 'Cherry', 'Orange' ],
  [ 'Lime', 'Cherry' ],
  [ 'Lime', 'Banana' ],
  [ 'Lime', 'Orange' ],
  [ 'Banana', 'Cherry' ],
  [ 'Banana', 'Lime' ],
  [ 'Banana', 'Orange' ],
  [ 'Orange', 'Cherry' ],
  [ 'Orange', 'Lime' ],
  [ 'Orange', 'Banana' ],
  [ 'Cherry', 'Lime', 'Banana' ],
  [ 'Cherry', 'Lime', 'Orange' ],
  [ 'Cherry', 'Banana', 'Lime' ],
  [ 'Cherry', 'Banana', 'Orange' ],
  [ 'Cherry', 'Orange', 'Lime' ],
  [ 'Cherry', 'Orange', 'Banana' ],
  [ 'Lime', 'Cherry', 'Banana' ],
  [ 'Lime', 'Cherry', 'Orange' ],
  [ 'Lime', 'Banana', 'Cherry' ],
  [ 'Lime', 'Banana', 'Orange' ],
  [ 'Lime', 'Orange', 'Cherry' ],
  [ 'Lime', 'Orange', 'Banana' ],
  [ 'Banana', 'Cherry', 'Lime' ],
  [ 'Banana', 'Cherry', 'Orange' ],
  [ 'Banana', 'Lime', 'Cherry' ],
  [ 'Banana', 'Lime', 'Orange' ],
  [ 'Banana', 'Orange', 'Cherry' ],
  [ 'Banana', 'Orange', 'Lime' ],
  [ 'Orange', 'Cherry', 'Lime' ],
  [ 'Orange', 'Cherry', 'Banana' ],
  [ 'Orange', 'Lime', 'Cherry' ],
  [ 'Orange', 'Lime', 'Banana' ],
  [ 'Orange', 'Banana', 'Cherry' ],
  [ 'Orange', 'Banana', 'Lime' ],
  [ 'Cherry', 'Lime', 'Banana', 'Orange' ],
  [ 'Cherry', 'Lime', 'Orange', 'Banana' ],
  [ 'Cherry', 'Banana', 'Lime', 'Orange' ],
  [ 'Cherry', 'Banana', 'Orange', 'Lime' ],
  [ 'Cherry', 'Orange', 'Lime', 'Banana' ],
  [ 'Cherry', 'Orange', 'Banana', 'Lime' ],
  [ 'Lime', 'Cherry', 'Banana', 'Orange' ],
  [ 'Lime', 'Cherry', 'Orange', 'Banana' ],
  [ 'Lime', 'Banana', 'Cherry', 'Orange' ],
  [ 'Lime', 'Banana', 'Orange', 'Cherry' ],
  [ 'Lime', 'Orange', 'Cherry', 'Banana' ],
  [ 'Lime', 'Orange', 'Banana', 'Cherry' ],
  [ 'Banana', 'Cherry', 'Lime', 'Orange' ],
  [ 'Banana', 'Cherry', 'Orange', 'Lime' ],
  [ 'Banana', 'Lime', 'Cherry', 'Orange' ],
  [ 'Banana', 'Lime', 'Orange', 'Cherry' ],
  [ 'Banana', 'Orange', 'Cherry', 'Lime' ],
  [ 'Banana', 'Orange', 'Lime', 'Cherry' ],
  [ 'Orange', 'Cherry', 'Lime', 'Banana' ],
  [ 'Orange', 'Cherry', 'Banana', 'Lime' ],
  [ 'Orange', 'Lime', 'Cherry', 'Banana' ],
  [ 'Orange', 'Lime', 'Banana', 'Cherry' ],
  [ 'Orange', 'Banana', 'Cherry', 'Lime' ],
  [ 'Orange', 'Banana', 'Lime', 'Cherry' ] ]

From the example output the OP seems to want to compute permutations, not combinations. — Felix Kling, Jun 01 '18 at 16:10
Good call. I got lost in the weeds and lost track of that detail. I updated the answer to produce permutations instead, which is actually a bit simpler. — chuckx, Jun 01 '18 at 16:37
Thank you chuck! Wonderful explanation! Exactly what I was looking for :). Thank you for adding to my education. — Nebri, Jun 02 '18 at 12:12

Finding all combinations of input set

1 Answers1