我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
这是我想出的解决这个问题的算法。它是用c++编写的,但是可以适应几乎任何支持位操作的语言。
void r_nCr(const unsigned int &startNum, const unsigned int &bitVal, const 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);
}
你可以在这里看到它如何工作的解释。
其他回答
下面是我的JavaScript解决方案,通过使用reduce/map,它消除了几乎所有变量,功能更强大
function combinations(arr, size) { var len = arr.length; if (size > len) return []; if (!size) return [[]]; if (size == len) return [arr]; return arr.reduce(function (acc, val, i) { var res = combinations(arr.slice(i + 1), size - 1) .map(function (comb) { return [val].concat(comb); }); return acc.concat(res); }, []); } var combs = combinations([1,2,3,4,5,6,7,8],3); combs.map(function (comb) { document.body.innerHTML += comb.toString() + '<br />'; }); document.body.innerHTML += '<br /> Total combinations = ' + combs.length;
这是一个为nCk生成组合的递归程序。假设集合中的元素从1到n
#include<stdio.h>
#include<stdlib.h>
int nCk(int n,int loopno,int ini,int *a,int k)
{
static int count=0;
int i;
loopno--;
if(loopno<0)
{
a[k-1]=ini;
for(i=0;i<k;i++)
{
printf("%d,",a[i]);
}
printf("\n");
count++;
return 0;
}
for(i=ini;i<=n-loopno-1;i++)
{
a[k-1-loopno]=i+1;
nCk(n,loopno,i+1,a,k);
}
if(ini==0)
return count;
else
return 0;
}
void main()
{
int n,k,*a,count;
printf("Enter the value of n and k\n");
scanf("%d %d",&n,&k);
a=(int*)malloc(k*sizeof(int));
count=nCk(n,k,0,a,k);
printf("No of combinations=%d\n",count);
}
在VB。Net,该算法从一组数字(PoolArray)中收集n个数字的所有组合。例如,从“8,10,20,33,41,44,47”中选择5个选项的所有组合。
Sub CreateAllCombinationsOfPicksFromPool(ByVal PicksArray() As UInteger, ByVal PicksIndex As UInteger, ByVal PoolArray() As UInteger, ByVal PoolIndex As UInteger)
If PicksIndex < PicksArray.Length Then
For i As Integer = PoolIndex To PoolArray.Length - PicksArray.Length + PicksIndex
PicksArray(PicksIndex) = PoolArray(i)
CreateAllCombinationsOfPicksFromPool(PicksArray, PicksIndex + 1, PoolArray, i + 1)
Next
Else
' completed combination. build your collections using PicksArray.
End If
End Sub
Dim PoolArray() As UInteger = Array.ConvertAll("8,10,20,33,41,44,47".Split(","), Function(u) UInteger.Parse(u))
Dim nPicks as UInteger = 5
Dim Picks(nPicks - 1) As UInteger
CreateAllCombinationsOfPicksFromPool(Picks, 0, PoolArray, 0)
Array.prototype.combs = function(num) {
var str = this,
length = str.length,
of = Math.pow(2, length) - 1,
out, combinations = [];
while(of) {
out = [];
for(var i = 0, y; i < length; i++) {
y = (1 << i);
if(y & of && (y !== of))
out.push(str[i]);
}
if (out.length >= num) {
combinations.push(out);
}
of--;
}
return combinations;
}
Lisp宏为所有值r(每次取)生成代码
(defmacro txaat (some-list taken-at-a-time)
(let* ((vars (reverse (truncate-list '(a b c d e f g h i j) taken-at-a-time))))
`(
,@(loop for i below taken-at-a-time
for j in vars
with nested = nil
finally (return nested)
do
(setf
nested
`(loop for ,j from
,(if (< i (1- (length vars)))
`(1+ ,(nth (1+ i) vars))
0)
below (- (length ,some-list) ,i)
,@(if (equal i 0)
`(collect
(list
,@(loop for k from (1- taken-at-a-time) downto 0
append `((nth ,(nth k vars) ,some-list)))))
`(append ,nested))))))))
So,
CL-USER> (macroexpand-1 '(txaat '(a b c d) 1))
(LOOP FOR A FROM 0 TO (- (LENGTH '(A B C D)) 1)
COLLECT (LIST (NTH A '(A B C D))))
T
CL-USER> (macroexpand-1 '(txaat '(a b c d) 2))
(LOOP FOR A FROM 0 TO (- (LENGTH '(A B C D)) 2)
APPEND (LOOP FOR B FROM (1+ A) TO (- (LENGTH '(A B C D)) 1)
COLLECT (LIST (NTH A '(A B C D)) (NTH B '(A B C D)))))
T
CL-USER> (macroexpand-1 '(txaat '(a b c d) 3))
(LOOP FOR A FROM 0 TO (- (LENGTH '(A B C D)) 3)
APPEND (LOOP FOR B FROM (1+ A) TO (- (LENGTH '(A B C D)) 2)
APPEND (LOOP FOR C FROM (1+ B) TO (- (LENGTH '(A B C D)) 1)
COLLECT (LIST (NTH A '(A B C D))
(NTH B '(A B C D))
(NTH C '(A B C D))))))
T
CL-USER>
And,
CL-USER> (txaat '(a b c d) 1)
((A) (B) (C) (D))
CL-USER> (txaat '(a b c d) 2)
((A B) (A C) (A D) (B C) (B D) (C D))
CL-USER> (txaat '(a b c d) 3)
((A B C) (A B D) (A C D) (B C D))
CL-USER> (txaat '(a b c d) 4)
((A B C D))
CL-USER> (txaat '(a b c d) 5)
NIL
CL-USER> (txaat '(a b c d) 0)
NIL
CL-USER>