How would I output all the possible combination of 7 numbers from 30 different numbers in an array in Javascript?

Question

For example I've array generated with the loop like this.

var array=[];
for(var i=1; i<=30; i++)
  {
   array.push(i);

  }
 console.log(array);

I want to output the combination of all the possible group of 7 numbers from the array. For example a sample output may look like : [1,5,14,4,30,23,19]. If I would to calculate the possible combination with the combination formula. It would be something like this: n!/r!(n-r)!

And it is going to be a huge number. I've found a permutation solution here, but what it does is that it prints out all the possible numbers according to the length of array. But my need is to find out the possible combination of 7 numbers from total 30 integers.

How would I solve this problem logically and practically with javascript.

Do you mean you just want to calculate how many combinations there will be? — BenM, Aug 23 '15 at 20:10
@BenM, No I can do that rather I want to print out all the possible combinations in arrays. — user2906838, Aug 23 '15 at 20:12
There would be `10,260,432,000` possible combinations. I don't think your computer would be able to print that in a reasonable time. — blex, Aug 23 '15 at 20:13
@blex I think there should only be just over 2 million combinations (30 choose 7). — Paul, Aug 23 '15 at 20:14
ya @blex but I am wondering for the possible alternative to this problem, no matter how much time would it takes. — user2906838, Aug 23 '15 at 20:15
@blex, the order can be random or symmetric but the thing I need is all the possible combinations of numbers in array. — user2906838, Aug 23 '15 at 20:16
something like in this [fiddle] [fiddle]:(http://jsfiddle.net/zgprr84q/1/) — user2906838, Aug 23 '15 at 20:20
but the number of integer in the outputted array should be less than the actual array which we permute. — user2906838, Aug 23 '15 at 20:24
You can be pretty sure that, about this kind of common algorithms, _everything_ is already [done](http://stackoverflow.com/a/11495614/5247200) — David, Aug 23 '15 at 20:30

score 0 · Answer 1 · 2015-08-23T21:05:35.303

First of all: this will generate bincoef(7,30) sets of integers, which is roughly 2mio. sets, so you should really consider whether you need this amount of data, since this algorithm will generate a mass of data and will require quite a lot of data. I can only offer pseudocode, since my javascript knowledge is rather basic.

void nextPermutation(int[] in, int[] set, int last_from_input, int at_element)
    //we can't generate further permutations from this position, since
    //there is aren't enough elements in the input-array left
    if(last_from_input >= 30 - at_element)
        return

    //the set is filled -> process the produced set
    if(at_element === 7)
        print(set)//process permutation
        return

    //add one element to the set and proceed with further elements
    for(int i in ]last_from_input, length(in) - (7 - at_element)[
        set[at_element] = in[i]

        nextPermutation(in , set , i, at_element + 1)

Basically this algorithm gets the following arguments:

in : the 30 integer to select from
set: the current part of the petmutation containing all elements we've added so far
last_from_input: the index of the last element from in we added to set
at_element: the index of the element in the set we're currently searching

This algorithm basically adds one element that has a higher index than the last added element and continue searching recursively searching for the next element. If the set is complete it can be processed. If there are more elements required to complete the set than elements left in in it's impossible to complete the set, we can break off with this part of the search. This is not optimally implemented regarding efficiency but I tried to keep things simple

Now we can simply generate all permutations in this way:

void genPermutations(int[] in)
    nextPermutation(in , new int[7],-1,0)

thanks can you please tell me more about your approach. Are all those arguments should be passed in nextPermutation? — user2906838, Aug 23 '15 at 20:30
@Bergi, it's ok, I need to know the approach but I found same alike solution in javascript too. So thanks! — user2906838, Aug 23 '15 at 20:37

rodic · Accepted Answer · 2015-08-23T21:30:09.933

0

guess this is what you're after?

function cartesian_product(xs, ys) {
    var result = [];
    for(var i = 0; i < xs.length; i++) {
        for (var j = 0; j < ys.length; j++) {
            // transform [ [1, 2], 3 ] => [ 1, 2, 3 ] and append it to result []
            result.push([].concat.apply([], [ xs[i], ys[j] ]));
        }
    }
    return result;
}

function cartesian_power(xs, n) {
    var result = xs;
    for(var i = 1; i < n; i++) {
        result = cartesian_product(result, xs)
    }
    return result;
}

// in your case params are [ 1, 2... 30] and 7
console.log(cartesian_power([1, 2, 3, 4], 2));

output is:

[ [ 1, 1 ],
  [ 1, 2 ],
  [ 1, 3 ],
  [ 1, 4 ],
  [ 2, 1 ],
  [ 2, 2 ],
  [ 2, 3 ],
  [ 2, 4 ],
  [ 3, 1 ],
  [ 3, 2 ],
  [ 3, 3 ],
  [ 3, 4 ],
  [ 4, 1 ],
  [ 4, 2 ],
  [ 4, 3 ],
  [ 4, 4 ] ]

UPDATE

this one will require much less memory, since it will not store anything, it will just print the output. but still doubt it's practical.

function print_combs(arr, n, out) {
    if (n === 0) {
        console.log(out);
    } else {
        for(var i = 0; i < arr.length; i++) {
            print_combs(arr, n-1, out+arr[i]);
        }
    }
}

print_combs([1, 2, 3, 4], 2, "");

edited Aug 23 '15 at 21:30

answered Aug 23 '15 at 20:48

rodic

445
4
10

Thanks @rodic, this is actually I'm looking for. But how can i handle the operation if I would to deal with the array of 30 or 40 integers? Are there any way to output without any crash? – user2906838 Aug 23 '15 at 20:53
don't know really, don't think this is something you should do in js. in case of array with length 30 and 7 nums the output array will have 30**7 arrays, that's a lot. – rodic Aug 23 '15 at 21:00
ya, the computer can't handle it. – user2906838 Aug 23 '15 at 21:02
thanks! do you know what is the practical approach to solve this problem? – user2906838 Aug 24 '15 at 06:49
if all you need is 7 of 30, maybe you could precompute it. now, not sure how long it will take to generate a file (a lot i'm sure), but it will be huge. for one row you would need 7 bytes + 1 byte for new line. there are 30**7 combs, so it will take about 163 gigabytes. – rodic Aug 24 '15 at 09:10

How would I output all the possible combination of 7 numbers from 30 different numbers in an array in Javascript?

2 Answers2

Linked