Recursively get all possible combinations of a set of numbers in Javascript

Question

I have a javascript application where I need to run a test of each possible combination of the numbers 0 through 6, without duplicating any number in the combination.

So: 0123456, 0123465, 0123546, 0123564 ...

(but, for example, 0123455, should not be included because 5 is duplicated)

I have done it iterativly:

function testAllCombinations(){
    for(var i = 0; i < 7; i++){
        for(var j = 0; j < 7; j++){
            if(j == i)
                continue;
            for(var k = 0; k < 7; k++){
                if(k == j || k == i)
                    continue;
                for(var l = 0; l < 7; l++){
                    if(l == k || l == j || l == i)
                        continue;
                    for(var m = 0; m < 7; m++){
                        if(m == l || m == k || m == j || m == i)
                            continue;
                        for(var n = 0; n < 7; n++){
                            if(n == m || n == l || n == k || n == j || n == i)
                                continue;
                            for(var o = 0; o < 7; o++){
                                if(o == n || o == m || o == l || o == l || o == j || o == i)
                                    continue;

                                runTest(i, j, k, l, m, n, o);
                            }
                        }
                    }
                }
            }
        }
    }
}

and it works fine, but I'd like to do it recursively, and I'm having a really hard time constructing the algorithm.

Can anyone provide me some direction?

Thanks in advance.

Combination or permutation? It looks like permutation to me. — nhahtdh, Sep 14 '13 at 05:45
Not sure if this questions is related to javascript in any way. Its a pure programming question IMO. — Neeraj, Sep 14 '13 at 05:47
possible duplicate of [permutations in javascript?](http://stackoverflow.com/questions/9960908/permutations-in-javascript) — Barmar, Sep 14 '13 at 05:48
Only relates to javascript because I wrote it in javascript, but yeah, not real js-specific. — cutmancometh, Sep 14 '13 at 06:51
Also, it's not a duplicate because this was the rare case when I wasn't looking for someone to just give me the code, but instead to help me start thinking in the right direction so I could solve it myself. I could copy and paste the code from [permutations in javascript](http://stackoverflow.com/questions/9960908/permutations-in-javascript), but in this case I was more interested in the mental exercise. Thanks all. — cutmancometh, Sep 14 '13 at 06:54
And, yes, it was permutations I was after, not combinations. Sorry for the lack of precision. — cutmancometh, Sep 14 '13 at 06:56

Johnson Wong · Answer 1 · 2013-09-14T06:34:09.390

This looks like a general question regarding recursion.

A recursive algorithm can be split into two parts, a base case, and a recursive case. First, figure out the base case, which results in a trivial result requiring no recursion. There can be more than one input resulting in a base case. Start with the most trivial input and expand from there. Pretty quickly, you'll discover the recursive cases, which are the key factors for recursive functions. You'll find that recursive cases all can be solved using a similar pattern composed of previous cases, including the base case.

So for this problem, let's say the user can enter a string and you want to print all combinations of characters in the string, let's call this invocation f(s). If the user enters a string with length 0 or 1, simply return the supplied string as there is only one combination available. Nothing special here. This is the base case.

If the user enters a string with length 2 (ex. "01"), it's pretty clear that the possible combinations are "01" and "10". How did you get this answer?
Notice that "01" = "0" + "1" and "10" = "1" + "0".
Iow, we looped through each number and combined it with the result of f(s) where s = remaining numbers.
ie. "01" = "0" + f("1") and "10" = "1" + f("0").
We already know how to solve this problem when the length is 1, so now we know how to solve the problem when the input length is 2.

Now if the input length is 3 (ex. "012"), you know the answer is "012", "021", "102", "120", "201", "210".
Notice that "012", "021" = "0" + "12", "0" + "21" and "102", "120" = "1" + "02", "1" + "20", and "201", "210" = "2" + "01", "2" + "10" Iow, we looped through each number and combined it with the the result of f(s) where s = remaining numbers. Sound familiar?
ie. "012", "021" = "0" + f("12") and "102", "120" = "1" + f("02") and "201", "210" = "2" + f("10")
We already know how to solve this problem when the length is 2, so now we know how to solve the problem when the input length is 3.

Do you see the pattern now? At each level (length of the input), we apply the same principles and so can utilize the same piece of code over and over again on subsets of the problem, eventually putting them together to form the final answer. This is what makes recursion so elegant.

Notice when the length of input is 4, we can again apply the same pattern yet again.
ie. f("0123") = "0" + f("123"), "1" + f("023"), "2" + f("013"), "3" + f("012"), and we already know how to solve this problem when the length is 3, so now we know how to solve the problem when the input length is 4.

I could go on, and also write out the solution in code, but no doubt there are better resources out there for learning recursion, so I'll let you look for them yourself. However, (I hope) my explanation is enough to get you thinking in the right direction and perhaps even solve your problem without having to read any additional resources.

Just remember the key to tackling recursion is to start with the simplest case and build up from there.

Thank you! This was what I was after: somebody to get me pointed in the right direction. I was aware of the heuristic for building a recursive algorithm, ie, start with the base case and build outward, but for some reason my brain couldn't identify the base case. It's been a long week. This was perfect. I'll work on this tomorrow and probably mark this as the answer once I get it working. — cutmancometh, Sep 14 '13 at 06:55
@cutmancometh Could you post the solution once you get it working? I'd be interested to see it. — Max Hartshorn, Sep 14 '13 at 18:07

score 0 · Answer 2 · edited Jun 20 '20 at 09:12

You might want to take a look at the following algorithm that generates the next permutation lexicographically.

The initial array must be sorted in order ascending before passing to the generation algorithm.

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.

Find the largest index l such that a[k] < a[l].

Swap the value of a[k] with that of a[l].

Reverse the sequence from a[k + 1] up to and including the final element a[n].

Recursively get all possible combinations of a set of numbers in Javascript

2 Answers2