我想写一个函数，它以一个字母数组作为参数，并从中选择一些字母。
假设您提供了一个包含8个字母的数组，并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词)，每个数组由3个字母组成。
当前回答
为此，我在SQL Server 2005中创建了一个解决方案，并将其发布在我的网站上:http://www.jessemclain.com/downloads/code/sql/fn_GetMChooseNCombos.sql.htm
下面是一个例子来说明用法:
SELECT * FROM dbo.fn_GetMChooseNCombos('ABCD', 2, '')
结果:
Word
----
AB
AC
AD
BC
BD
CD
(6 row(s) affected)
其他回答
我可以给出这个问题的递归Python解决方案吗?
def choose_iter(elements, length):
for i in xrange(len(elements)):
if length == 1:
yield (elements[i],)
else:
for next in choose_iter(elements[i+1:], length-1):
yield (elements[i],) + next
def choose(l, k):
return list(choose_iter(l, k))
使用示例:
>>> len(list(choose_iter("abcdefgh",3)))
56
我喜欢它的简洁。
这是一个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);
}
你可以在这里找到这是如何工作的解释。
下面是c++中的迭代算法，它不使用STL，也不使用递归，也不使用条件嵌套循环。这样更快，它不执行任何元素交换，也不会给堆栈带来递归负担，还可以通过分别用mallloc()、free()和printf()替换new、delete和std::cout轻松地移植到ANSI C。
如果你想用不同或更长的字母显示元素，那么改变*字母参数以指向不同于"abcdefg"的字符串。
void OutputArrayChar(unsigned int* ka, size_t n, const char *alphabet) {
for (int i = 0; i < n; i++)
std::cout << alphabet[ka[i]] << ",";
std::cout << endl;
}
void GenCombinations(const unsigned int N, const unsigned int K, const char *alphabet) {
unsigned int *ka = new unsigned int [K]; //dynamically allocate an array of UINTs
unsigned int ki = K-1; //Point ki to the last elemet of the array
ka[ki] = N-1; //Prime the last elemet of the array.
while (true) {
unsigned int tmp = ka[ki]; //Optimization to prevent reading ka[ki] repeatedly
while (ki) //Fill to the left with consecutive descending values (blue squares)
ka[--ki] = --tmp;
OutputArrayChar(ka, K, alphabet);
while (--ka[ki] == ki) { //Decrement and check if the resulting value equals the index (bright green squares)
OutputArrayChar(ka, K, alphabet);
if (++ki == K) { //Exit condition (all of the values in the array are flush to the left)
delete[] ka;
return;
}
}
}
}
int main(int argc, char *argv[])
{
GenCombinations(7, 4, "abcdefg");
return 0;
}
重要提示:字母参数*必须指向至少N个字符的字符串。你也可以传递一个在其他地方定义的字符串地址。
组合:从“7选4”中选择。
Python中的简短示例:
def comb(sofar, rest, n):
if n == 0:
print sofar
else:
for i in range(len(rest)):
comb(sofar + rest[i], rest[i+1:], n-1)
>>> comb("", "abcde", 3)
abc
abd
abe
acd
ace
ade
bcd
bce
bde
cde
为了解释，递归方法用下面的例子描述:
示例:A B C D E 3的所有组合是:
A与其余2的所有组合(B C D E) B与其余2的所有组合(C D E) C与其余2的所有组合(D E)
这是一个简单的JS解决方案:
function getAllCombinations(n, k, f1) { indexes = Array(k); for (let i =0; i< k; i++) { indexes[i] = i; } var total = 1; f1(indexes); while (indexes[0] !== n-k) { total++; getNext(n, indexes); f1(indexes); } return {total}; } function getNext(n, vec) { const k = vec.length; vec[k-1]++; for (var i=0; i<k; i++) { var currentIndex = k-i-1; if (vec[currentIndex] === n - i) { var nextIndex = k-i-2; vec[nextIndex]++; vec[currentIndex] = vec[nextIndex] + 1; } } for (var i=1; i<k; i++) { if (vec[i] === n - (k-i - 1)) { vec[i] = vec[i-1] + 1; } } return vec; } let start = new Date(); let result = getAllCombinations(10, 3, indexes => console.log(indexes)); let runTime = new Date() - start; console.log({ result, runTime });
