我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
在c#中:
public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> elements, int k)
{
return k == 0 ? new[] { new T[0] } :
elements.SelectMany((e, i) =>
elements.Skip(i + 1).Combinations(k - 1).Select(c => (new[] {e}).Concat(c)));
}
用法:
var result = Combinations(new[] { 1, 2, 3, 4, 5 }, 3);
结果:
123
124
125
134
135
145
234
235
245
345
其他回答
我的实现在c/c++
#include <unistd.h>
#include <stdio.h>
#include <iconv.h>
#include <string.h>
#include <errno.h>
#include <stdlib.h>
int main(int argc, char **argv)
{
int opt = -1, min_len = 0, max_len = 0;
char ofile[256], fchar[2], tchar[2];
ofile[0] = 0;
fchar[0] = 0;
tchar[0] = 0;
while((opt = getopt(argc, argv, "o:f:t:l:L:")) != -1)
{
switch(opt)
{
case 'o':
strncpy(ofile, optarg, 255);
break;
case 'f':
strncpy(fchar, optarg, 1);
break;
case 't':
strncpy(tchar, optarg, 1);
break;
case 'l':
min_len = atoi(optarg);
break;
case 'L':
max_len = atoi(optarg);
break;
default:
printf("usage: %s -oftlL\n\t-o output file\n\t-f from char\n\t-t to char\n\t-l min seq len\n\t-L max seq len", argv[0]);
}
}
if(max_len < 1)
{
printf("error, length must be more than 0\n");
return 1;
}
if(min_len > max_len)
{
printf("error, max length must be greater or equal min_length\n");
return 1;
}
if((int)fchar[0] > (int)tchar[0])
{
printf("error, invalid range specified\n");
return 1;
}
FILE *out = fopen(ofile, "w");
if(!out)
{
printf("failed to open input file with error: %s\n", strerror(errno));
return 1;
}
int cur_len = min_len;
while(cur_len <= max_len)
{
char buf[cur_len];
for(int i = 0; i < cur_len; i++)
buf[i] = fchar[0];
fwrite(buf, cur_len, 1, out);
fwrite("\n", 1, 1, out);
while(buf[0] != (tchar[0]+1))
{
while(buf[cur_len-1] < tchar[0])
{
(int)buf[cur_len-1]++;
fwrite(buf, cur_len, 1, out);
fwrite("\n", 1, 1, out);
}
if(cur_len < 2)
break;
if(buf[0] == tchar[0])
{
bool stop = true;
for(int i = 1; i < cur_len; i++)
{
if(buf[i] != tchar[0])
{
stop = false;
break;
}
}
if(stop)
break;
}
int u = cur_len-2;
for(; u>=0 && buf[u] >= tchar[0]; u--)
;
(int)buf[u]++;
for(int i = u+1; i < cur_len; i++)
buf[i] = fchar[0];
fwrite(buf, cur_len, 1, out);
fwrite("\n", 1, 1, out);
}
cur_len++;
}
fclose(out);
return 0;
}
这里我的实现在c++,它写所有的组合到指定的文件,但行为可以改变,我在生成各种字典,它接受最小和最大长度和字符范围,目前只有ANSI支持,它足以满足我的需求
在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' ]
]
这是一个优雅的Scala通用实现,如99个Scala问题所述。
object P26 {
def flatMapSublists[A,B](ls: List[A])(f: (List[A]) => List[B]): List[B] =
ls match {
case Nil => Nil
case sublist@(_ :: tail) => f(sublist) ::: flatMapSublists(tail)(f)
}
def combinations[A](n: Int, ls: List[A]): List[List[A]] =
if (n == 0) List(Nil)
else flatMapSublists(ls) { sl =>
combinations(n - 1, sl.tail) map {sl.head :: _}
}
}
void combine(char a[], int N, int M, int m, int start, char result[]) {
if (0 == m) {
for (int i = M - 1; i >= 0; i--)
std::cout << result[i];
std::cout << std::endl;
return;
}
for (int i = start; i < (N - m + 1); i++) {
result[m - 1] = a[i];
combine(a, N, M, m-1, i+1, result);
}
}
void combine(char a[], int N, int M) {
char *result = new char[M];
combine(a, N, M, M, 0, result);
delete[] result;
}
在第一个函数中,m表示还需要选择多少个,start表示必须从数组中的哪个位置开始选择。
这是一个为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);
}