javascript - 获取所有可能集合的算法

<分区>

输入:

[ [a1,b1,c1], [a2,b2,c2,d,2], [a3,b3], ...]

输出:

[ [a1,a2,a3], [a1,a2,b3], [a1,b2,a3], [a1,b2,b3], [a1,c2,a3], [a1,c2,b3], ... ]

所以我需要所有可能集合的组合(顺序无关紧要)。每个输出集 nth 成员都是 nth 输入集的成员。我需要高效的算法，最好是在 javascript 中。

编辑

好吧，我正在努力解决这个问题。

var input = [ [a,b,c], [a1,b1,c1], [a2,b2] ];

var combinationsNum = _.reduce(input,function(num,set){ return num*set.length; }, 1);
var output = new Array(combinationsNum);
for(var i = 0; i < output.length; ++i) output[i] = [];

for(var s = 0; s < input.length; ++s) {
    var set = input[s];
    for(var m = 0; m < set.length; ++m) {
        var memeber = set[m];
        // now I need to calculate to which output arrays I have to push this member
    }
}

// result should be
// a a1 a2
// a b1 b2
// a c1 a2
// a a1 b2
// a b1 a2
// a c1 b2
// b a1 a2
// b b1 b2
// b c1 a2
// b a1 b2
// b b1 a2
// b c1 b2
// c a1 a2
// c b1 b2
// c c1 a2
// c a1 b2
// c b1 a2
// c c1 b2

正如您在每个 set 上看到的那样，我必须以一定的间隔和时间将其每个成员推送到每个输出数组...我在计算时遇到问题...

我在这个重复问题中找到的最快方法是:

function(arg) {
    var r = [], max = arg.length-1;
    function helper(arr, i) {
        for (var j=0, l=arg[i].length; j<l; j++) {
            var a = arr.slice(0); // clone arr
            a.push(arg[i][j])
            if (i==max) {
                r.push(a);
            } else
                helper(a, i+1);
        }
    }
    helper([], 0);
    return r;
};

最佳答案

实现此目的的一种可能方法是使用递归。我不熟悉 JavaScript，以下是 C++ 版本。您可以相应地调整它。

#include <iostream>
#include <vector>

using namespace std;

vector< vector<int> > input;

void recurCombination( vector<int>& outputSoFar ) {

  // base case: If number of entries in our output = size of input array, then print it.
  if ( outputSoFar.size() == input.size() ) {
    // print outputSoFar
    return;
  }

  // else take next subarray in the input array.
  int sizeSofar = outputSoFar.size();    

  // for each element in that subarray, choose an element and recur further.
  for ( int i = 0; i < input[sizeSoFar].size(); i++ ) {
    vector<int> newSoFar( outputSoFar );
    newSoFar.push_back( input[sizeSoFar][i] );
    recurCombination( newSoFar )

  }

}

int main() {

  // read input vector
  vector<int> emptySoFar;
  recurCombination( emptySoFar );

  return 0;
}

关于javascript - 获取所有可能集合的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20042999/

上一篇：java - 当客户的帐户进行存款交易时，我是否应该使用观察者模式通知客户对象？

下一篇：algorithm - 采样率变化之间的音频淡出功能

相关文章：

c++ - 从 vector 中删除空元素

algorithm - 什么算法确定点与贝塞尔曲线的接近程度？

javascript - 扩展实现接口(interface)影子名称的类

javascript - 如何使 textarea 内容可以设置样式或设置 div 行为(如 textarea 行为)？

javascript - 如何通过 AJAX 将 JavaScript 数组传递给 Perl 脚本？

node.js - 如何使用 cognito 创建用户帐户，但使用不同的验证服务？

node.js - moment(new Date().toISOString() 始终返回相同的日期和时间

javascript - 在 IIFE 之外访问 jQuery 变量

python - 如何提高数据转json格式的性能？

node.js - 使用sdk删除stormpath 0.10中的组成员身份