我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
JavaScript,基于生成器,递归方法:
function *nCk(n,k){ for(var i=n-1;i>=k-1;--i) if(k===1) yield [i]; else for(var temp of nCk(i,k-1)){ temp.unshift(i); yield temp; } } function test(){ try{ var n=parseInt(ninp.value); var k=parseInt(kinp.value); log.innerText=""; var stop=Date.now()+1000; if(k>=1) for(var res of nCk(n,k)) if(Date.now()<stop) log.innerText+=JSON.stringify(res)+" "; else{ log.innerText+="1 second passed, stopping here."; break; } }catch(ex){} } n:<input id="ninp" oninput="test()"> >= k:<input id="kinp" oninput="test()"> >= 1 <div id="log"></div>
通过这种方式(减少i和unshift()),它以递减的顺序生成组合和组合内的元素,有点赏心悦目。 测试在1秒后停止,因此输入奇怪的数字是相对安全的。
其他回答
递归,一个很简单的答案,combo,在Free Pascal中。
procedure combinata (n, k :integer; producer :oneintproc);
procedure combo (ndx, nbr, len, lnd :integer);
begin
for nbr := nbr to len do begin
productarray[ndx] := nbr;
if len < lnd then
combo(ndx+1,nbr+1,len+1,lnd)
else
producer(k);
end;
end;
begin
combo (0, 0, n-k, n-1);
end;
“producer”处理为每个组合生成的产品数组。
《计算机编程艺术,卷4A:组合算法,第1部分》第7.2.1.3节中算法L(字典组合)的C代码:
#include <stdio.h>
#include <stdlib.h>
void visit(int* c, int t)
{
// for (int j = 1; j <= t; j++)
for (int j = t; j > 0; j--)
printf("%d ", c[j]);
printf("\n");
}
int* initialize(int n, int t)
{
// c[0] not used
int *c = (int*) malloc((t + 3) * sizeof(int));
for (int j = 1; j <= t; j++)
c[j] = j - 1;
c[t+1] = n;
c[t+2] = 0;
return c;
}
void comb(int n, int t)
{
int *c = initialize(n, t);
int j;
for (;;) {
visit(c, t);
j = 1;
while (c[j]+1 == c[j+1]) {
c[j] = j - 1;
++j;
}
if (j > t)
return;
++c[j];
}
free(c);
}
int main(int argc, char *argv[])
{
comb(5, 3);
return 0;
}
下面是一个使用宏的Lisp方法。这适用于Common Lisp,也适用于其他Lisp方言。
下面的代码创建了'n'个嵌套循环,并为列表lst中的'n'个元素的每个组合执行任意代码块(存储在body变量中)。变量var指向一个包含用于循环的变量的列表。
(defmacro do-combinations ((var lst num) &body body)
(loop with syms = (loop repeat num collect (gensym))
for i on syms
for k = `(loop for ,(car i) on (cdr ,(cadr i))
do (let ((,var (list ,@(reverse syms)))) (progn ,@body)))
then `(loop for ,(car i) on ,(if (cadr i) `(cdr ,(cadr i)) lst) do ,k)
finally (return k)))
让我们看看…
(macroexpand-1 '(do-combinations (p '(1 2 3 4 5 6 7) 4) (pprint (mapcar #'car p))))
(LOOP FOR #:G3217 ON '(1 2 3 4 5 6 7) DO
(LOOP FOR #:G3216 ON (CDR #:G3217) DO
(LOOP FOR #:G3215 ON (CDR #:G3216) DO
(LOOP FOR #:G3214 ON (CDR #:G3215) DO
(LET ((P (LIST #:G3217 #:G3216 #:G3215 #:G3214)))
(PROGN (PPRINT (MAPCAR #'CAR P))))))))
(do-combinations (p '(1 2 3 4 5 6 7) 4) (pprint (mapcar #'car p)))
(1 2 3 4)
(1 2 3 5)
(1 2 3 6)
...
由于默认情况下不存储组合,因此存储空间保持在最小值。选择主体代码而不是存储所有结果的可能性也提供了更大的灵活性。
遵循Haskell代码同时计算组合数和组合,由于Haskell的惰性,您可以得到其中的一部分而无需计算另一部分。
import Data.Semigroup
import Data.Monoid
data Comb = MkComb {count :: Int, combinations :: [[Int]]} deriving (Show, Eq, Ord)
instance Semigroup Comb where
(MkComb c1 cs1) <> (MkComb c2 cs2) = MkComb (c1 + c2) (cs1 ++ cs2)
instance Monoid Comb where
mempty = MkComb 0 []
addElem :: Comb -> Int -> Comb
addElem (MkComb c cs) x = MkComb c (map (x :) cs)
comb :: Int -> Int -> Comb
comb n k | n < 0 || k < 0 = error "error in `comb n k`, n and k should be natural number"
comb n k | k == 0 || k == n = MkComb 1 [(take k [k-1,k-2..0])]
comb n k | n < k = mempty
comb n k = comb (n-1) k <> (comb (n-1) (k-1) `addElem` (n-1))
它是这样工作的:
*Main> comb 0 1
MkComb {count = 0, combinations = []}
*Main> comb 0 0
MkComb {count = 1, combinations = [[]]}
*Main> comb 1 1
MkComb {count = 1, combinations = [[0]]}
*Main> comb 4 2
MkComb {count = 6, combinations = [[1,0],[2,0],[2,1],[3,0],[3,1],[3,2]]}
*Main> count (comb 10 5)
252
这是一个c++解决方案,我提出使用递归和位移位。它也可以在C语言中工作。
void r_nCr(unsigned int startNum, unsigned int bitVal, unsigned int testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1)
{
unsigned int n = (startNum - bitVal) << 1;
n += bitVal ? 1 : 0;
for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s
cout << (n >> (i - 1) & 1);
cout << endl;
if (!(n & testNum) && n != startNum)
r_nCr(n, bitVal, testNum);
if (bitVal && bitVal < testNum)
r_nCr(startNum, bitVal >> 1, testNum);
}
你可以在这里找到这是如何工作的解释。