我想写一个函数,它将一个字母数组作为参数,并选择一些字母.

假设您提供了8个字母的数组,并希望从中选择3个字母.然后你应该得到:

8! / ((8 - 3)! * 3!) = 56

数组(或单词)返回,每个包含3个字母.

我需要一种计算组合的方法,而不会耗尽内存.这是我到目前为止所拥有的.

public static long combination(long n, long k) // nCk
{
    return (divideFactorials(factorial(n), ((factorial(k) * factorial((n - k))))));
}

public static long factorial(long n)
{
    long result;
    if (n <= 1) return 1;
    result = factorial(n - 1) * n;
    return result;
}

public static long divideFactorials(long numerator, long denominator)
{
    return factorial(Math.Abs((numerator - denominator)));
}

我已将其标记为C#,但理想情况下,解决方案应该与语言无关.

为了探索一些解决方案,我需要产生所有可能性.我是通过使用位屏蔽来实现的,如下所示:

for (long i = 0; i < 1L << NB; i++) {
    System.out.println(Long.toBinaryString(i));
    if(checkSolution(i)) {
        this.add(i); // add i to solutions
    }
}
this.getBest(); // get the solution with lowest number of 1

这让我去探索(如果NB = 3):

000
001
010
011
100
101
110
111

我的问题是最好的解决方案是数量最少的那个1.所以,为了在我找到解决方案后立即停止搜索,我希望有一个不同的顺序并生成这样的东西:

000
001
010
100
011
101
110
111

这将使搜索速度更快,因为我可以在获得第一个解决方案后立即停止搜索.但我不知道如何更改循环以获得此输出...

PS:NB未定义......

我在Node.js服务器上有一些性能敏感的代码需要计算组合.从这个SO答案中,我使用这个简单的递归函数来计算n选择k:

function choose(n, k) {
    if (k === 0) return 1;
    return (n * choose(n-1, k-1)) / k;
}

然后因为我们都知道迭代几乎总是比递归更快,所以我根据乘法公式编写了这个函数:

function choosei(n,k){
    var result = 1;
    for(var i=1; i <= k; i++){
        result *= (n+1-i)/i;
    }
    return result;
}

我在我的机器上运行了一些基准测试.以下是其中一个的结果:

Recursive x 178,836 ops/sec ±7.03% (60 runs sampled)
Iterative x 550,284 ops/sec ±5.10% (51 runs sampled)
Fastest is Iterative

结果一致表明,迭代方法确实比Node.js中的递归方法快3到4倍(至少在我的机器上).

这可能足以满足我的需求,但有没有办法让它更快？我的代码必须具有相当大的价值非常频繁调用这个函数,有时会n和k,所以速度越快越好.

编辑

在使用le_m和Mike的解决方案运行了一些测试之后,事实证明,虽然两者都比我提出的迭代方法快得多,但Mike使用Pascal三角形的方法似乎比le_m的日志表方法略快.

Recursive x 189,036 …