我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含8个字母的数组,并希望从中选择3个字母。那么你应该得到:
8! / ((8 - 3)! * 3!) = 56
数组(或单词),每个数组由3个字母组成。
当前回答
这是一个为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);
}
其他回答
Haskell中的简单递归算法
import Data.List
combinations 0 lst = [[]]
combinations n lst = do
(x:xs) <- tails lst
rest <- combinations (n-1) xs
return $ x : rest
我们首先定义特殊情况,即选择零元素。它产生一个单一的结果,这是一个空列表(即一个包含空列表的列表)。
对于n> 0, x遍历列表中的每一个元素xs是x之后的每一个元素。
Rest通过对组合的递归调用从xs中选取n - 1个元素。该函数的最终结果是一个列表,其中每个元素都是x: rest(即对于x和rest的每个不同值,x为头部,rest为尾部的列表)。
> combinations 3 "abcde"
["abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde"]
当然,由于Haskell是懒惰的,列表是根据需要逐渐生成的,因此您可以部分计算指数级的大组合。
> let c = combinations 8 "abcdefghijklmnopqrstuvwxyz"
> take 10 c
["abcdefgh","abcdefgi","abcdefgj","abcdefgk","abcdefgl","abcdefgm","abcdefgn",
"abcdefgo","abcdefgp","abcdefgq"]
下面是我最近用Java写的一段代码,它计算并返回从“outOf”元素中“num”元素的所有组合。
// author: Sourabh Bhat (heySourabh@gmail.com)
public class Testing
{
public static void main(String[] args)
{
// Test case num = 5, outOf = 8.
int num = 5;
int outOf = 8;
int[][] combinations = getCombinations(num, outOf);
for (int i = 0; i < combinations.length; i++)
{
for (int j = 0; j < combinations[i].length; j++)
{
System.out.print(combinations[i][j] + " ");
}
System.out.println();
}
}
private static int[][] getCombinations(int num, int outOf)
{
int possibilities = get_nCr(outOf, num);
int[][] combinations = new int[possibilities][num];
int arrayPointer = 0;
int[] counter = new int[num];
for (int i = 0; i < num; i++)
{
counter[i] = i;
}
breakLoop: while (true)
{
// Initializing part
for (int i = 1; i < num; i++)
{
if (counter[i] >= outOf - (num - 1 - i))
counter[i] = counter[i - 1] + 1;
}
// Testing part
for (int i = 0; i < num; i++)
{
if (counter[i] < outOf)
{
continue;
} else
{
break breakLoop;
}
}
// Innermost part
combinations[arrayPointer] = counter.clone();
arrayPointer++;
// Incrementing part
counter[num - 1]++;
for (int i = num - 1; i >= 1; i--)
{
if (counter[i] >= outOf - (num - 1 - i))
counter[i - 1]++;
}
}
return combinations;
}
private static int get_nCr(int n, int r)
{
if(r > n)
{
throw new ArithmeticException("r is greater then n");
}
long numerator = 1;
long denominator = 1;
for (int i = n; i >= r + 1; i--)
{
numerator *= i;
}
for (int i = 2; i <= n - r; i++)
{
denominator *= i;
}
return (int) (numerator / denominator);
}
}
#include <stdio.h>
unsigned int next_combination(unsigned int *ar, size_t n, unsigned int k)
{
unsigned int finished = 0;
unsigned int changed = 0;
unsigned int i;
if (k > 0) {
for (i = k - 1; !finished && !changed; i--) {
if (ar[i] < (n - 1) - (k - 1) + i) {
/* Increment this element */
ar[i]++;
if (i < k - 1) {
/* Turn the elements after it into a linear sequence */
unsigned int j;
for (j = i + 1; j < k; j++) {
ar[j] = ar[j - 1] + 1;
}
}
changed = 1;
}
finished = i == 0;
}
if (!changed) {
/* Reset to first combination */
for (i = 0; i < k; i++) {
ar[i] = i;
}
}
}
return changed;
}
typedef void(*printfn)(const void *, FILE *);
void print_set(const unsigned int *ar, size_t len, const void **elements,
const char *brackets, printfn print, FILE *fptr)
{
unsigned int i;
fputc(brackets[0], fptr);
for (i = 0; i < len; i++) {
print(elements[ar[i]], fptr);
if (i < len - 1) {
fputs(", ", fptr);
}
}
fputc(brackets[1], fptr);
}
int main(void)
{
unsigned int numbers[] = { 0, 1, 2 };
char *elements[] = { "a", "b", "c", "d", "e" };
const unsigned int k = sizeof(numbers) / sizeof(unsigned int);
const unsigned int n = sizeof(elements) / sizeof(const char*);
do {
print_set(numbers, k, (void*)elements, "[]", (printfn)fputs, stdout);
putchar('\n');
} while (next_combination(numbers, n, k));
getchar();
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的答案是完整的,不幸的是我还不能投票。这个答案很简单,但只适用于你想要三样东西的时候。
我的实现在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支持,它足以满足我的需求