如何在Javascript数组中输出来自30个不同数字的7个数字的所有可能组合?(复制)

This question already has an answer here:

这个问题已经有了答案:

Algorithm to return all combinations of k elements from n 66 answers
从n66个答案返回所有k个元素的组合的算法

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)!

我想从数组中输出所有可能的7个数的组合。例如，一个示例输出可能看起来是:[1、5、14、4、30、23、19]。如果我用组合公式计算可能的组合。应该是这样的: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.

这将是一个巨大的数字。我在这里找到了排列解，但它的作用是根据数组的长度打印出所有可能的数。但我需要从30个整数中找出7个数的可能组合。

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

如何用javascript逻辑和实际地解决这个问题。

2 个解决方案

#1

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, "");

#2

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.

首先:这将生成bincoef(7,30)组整数，大约是2mio。集合，所以你应该考虑是否需要这么多的数据，因为这个算法会生成大量的数据并且需要大量的数据。我只能提供伪代码，因为我的javascript知识相当基础。

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
在:选择的30个整数
set: the current part of the petmutation containing all elements we've added so far
set: petmutation的当前部分，包含到目前为止添加的所有元素
last_from_input: the index of the last element from in we added to set
last_from_input:添加到set中的最后一个元素的索引
at_element: the index of the element in the set we're currently searching
at_element:我们当前搜索的集合中元素的索引

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)

#1