我如何将Javascript中的数组中的30个不同数字的7个数字的所有可能组合输出？

Question

例如，我用这样的循环生成数组。

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

  }
 console.log(array);

我想输出数组中所有可能的 7 组数字的组合。例如，示例输出可能如下所示：[1,5,14,4,30,23,19]。如果我想用组合公式计算可能的组合。它会是这样的： n!/r!(n-r)!

这将是一个巨大的数字。我找到了一个 permutation solution here，但它所做的是根据数组的长度打印出所有可能的数字。但我的需求是从总共30个整数中找出7个数字的可能组合。

我如何用 javascript.

从逻辑上和实践上解决这个问题

Answer 1

首先：这将生成 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)

基本上这个算法得到以下参数：

in : 从
set：petmutation 的当前部分，包含我们目前添加的所有元素
last_from_input：我们添加到集合中的最后一个元素的索引
at_element：当前正在搜索的集合中元素的索引

这个算法基本上是添加一个比上次添加的元素索引更高的元素，然后递归地继续搜索下一个元素。如果设置完整，则可以进行处理。如果完成集合所需的元素多于无法完成集合的剩余元素，我们可以中断这部分搜索。这在效率方面没有得到最佳实施，但我试图让事情变得简单

现在我们可以用这种方式简单地生成所有排列：

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

Answer 2

猜猜这就是你想要的？

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

输出为：

[ [ 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 ] ]

更新

这个需要的内存要少得多，因为它不会存储任何东西，它只会打印输出。但还是怀疑实用性。

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

我如何将Javascript中的数组中的30个不同数字的7个数字的所有可能组合输出？

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

javascript

arrays

algorithm

combinations

subset