我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
在Python中,利用递归的优势和所有事情都是通过引用完成的事实。对于非常大的集合,这将占用大量内存,但其优点是初始集合可以是一个复杂的对象。它只会找到唯一的组合。
import copy
def find_combinations( length, set, combinations = None, candidate = None ):
# recursive function to calculate all unique combinations of unique values
# from [set], given combinations of [length]. The result is populated
# into the 'combinations' list.
#
if combinations == None:
combinations = []
if candidate == None:
candidate = []
for item in set:
if item in candidate:
# this item already appears in the current combination somewhere.
# skip it
continue
attempt = copy.deepcopy(candidate)
attempt.append(item)
# sorting the subset is what gives us completely unique combinations,
# so that [1, 2, 3] and [1, 3, 2] will be treated as equals
attempt.sort()
if len(attempt) < length:
# the current attempt at finding a new combination is still too
# short, so add another item to the end of the set
# yay recursion!
find_combinations( length, set, combinations, attempt )
else:
# the current combination attempt is the right length. If it
# already appears in the list of found combinations then we'll
# skip it.
if attempt in combinations:
continue
else:
# otherwise, we append it to the list of found combinations
# and move on.
combinations.append(attempt)
continue
return len(combinations)
你可以这样使用它。传递'result'是可选的,所以你可以用它来获取可能组合的数量…尽管这样做效率很低(最好通过计算来完成)。
size = 3
set = [1, 2, 3, 4, 5]
result = []
num = find_combinations( size, set, result )
print "size %d results in %d sets" % (size, num)
print "result: %s" % (result,)
您应该从测试数据中得到以下输出:
size 3 results in 10 sets
result: [[1, 2, 3], [1, 2, 4], [1, 2, 5], [1, 3, 4], [1, 3, 5], [1, 4, 5], [2, 3, 4], [2, 3, 5], [2, 4, 5], [3, 4, 5]]
如果你的集合是这样的,它也会工作得很好:
set = [
[ 'vanilla', 'cupcake' ],
[ 'chocolate', 'pudding' ],
[ 'vanilla', 'pudding' ],
[ 'chocolate', 'cookie' ],
[ 'mint', 'cookie' ]
]
其他回答
c#简单算法。 (我发布它是因为我试图使用你们上传的那个,但由于某种原因我无法编译它——扩展一个类?所以我自己写了一个,以防别人遇到和我一样的问题)。 顺便说一下,除了基本的编程,我对c#没什么兴趣,但是这个工作得很好。
public static List<List<int>> GetSubsetsOfSizeK(List<int> lInputSet, int k)
{
List<List<int>> lSubsets = new List<List<int>>();
GetSubsetsOfSizeK_rec(lInputSet, k, 0, new List<int>(), lSubsets);
return lSubsets;
}
public static void GetSubsetsOfSizeK_rec(List<int> lInputSet, int k, int i, List<int> lCurrSet, List<List<int>> lSubsets)
{
if (lCurrSet.Count == k)
{
lSubsets.Add(lCurrSet);
return;
}
if (i >= lInputSet.Count)
return;
List<int> lWith = new List<int>(lCurrSet);
List<int> lWithout = new List<int>(lCurrSet);
lWith.Add(lInputSet[i++]);
GetSubsetsOfSizeK_rec(lInputSet, k, i, lWith, lSubsets);
GetSubsetsOfSizeK_rec(lInputSet, k, i, lWithout, lSubsets);
}
GetSubsetsOfSizeK(set of type List<int>, integer k)
您可以修改它以遍历您正在处理的任何内容。
好运!
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秒后停止,因此输入奇怪的数字是相对安全的。
《计算机编程艺术,卷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;
}
如果你可以使用SQL语法——比如,如果你使用LINQ访问一个结构或数组的字段,或者直接访问一个数据库,其中有一个名为“Alphabet”的表,只有一个字符字段“Letter”,你可以适应以下代码:
SELECT A.Letter, B.Letter, C.Letter
FROM Alphabet AS A, Alphabet AS B, Alphabet AS C
WHERE A.Letter<>B.Letter AND A.Letter<>C.Letter AND B.Letter<>C.Letter
AND A.Letter<B.Letter AND B.Letter<C.Letter
这将返回所有3个字母的组合,不管你在表格“字母表”中有多少个字母(它可以是3,8,10,27等)。
如果你想要的是所有的排列,而不是组合(也就是说,你想要“ACB”和“ABC”被视为不同的,而不是只出现一次),只需删除最后一行(and一行),就完成了。
Post-Edit:重新阅读问题后,我意识到需要的是通用算法,而不仅仅是选择3个项目的特定算法。Adam Hughes的答案是完整的,不幸的是我还不能投票。这个答案很简单,但只适用于你想要三样东西的时候。
一个简洁的Javascript解决方案:
Array.prototype.combine=function combine(k){
var toCombine=this;
var last;
function combi(n,comb){
var combs=[];
for ( var x=0,y=comb.length;x<y;x++){
for ( var l=0,m=toCombine.length;l<m;l++){
combs.push(comb[x]+toCombine[l]);
}
}
if (n<k-1){
n++;
combi(n,combs);
} else{last=combs;}
}
combi(1,toCombine);
return last;
}
// Example:
// var toCombine=['a','b','c'];
// var results=toCombine.combine(4);