我想写一个函数,它以一个字母数组作为参数,并从中选择一些字母。
假设您提供了一个包含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);
}
其他回答
我有一个用于project euler的排列算法,用python编写:
def missing(miss,src):
"Returns the list of items in src not present in miss"
return [i for i in src if i not in miss]
def permutation_gen(n,l):
"Generates all the permutations of n items of the l list"
for i in l:
if n<=1: yield [i]
r = [i]
for j in permutation_gen(n-1,missing([i],l)): yield r+j
If
n<len(l)
你应该有所有你需要的组合,没有重复,你需要吗?
它是一个生成器,所以你可以这样使用它:
for comb in permutation_gen(3,list("ABCDEFGH")):
print comb
基于java解决方案的短php算法返回k元素从n(二项式系数)的所有组合:
$array = array(1,2,3,4,5);
$array_result = NULL;
$array_general = NULL;
function combinations($array, $len, $start_position, $result_array, $result_len, &$general_array)
{
if($len == 0)
{
$general_array[] = $result_array;
return;
}
for ($i = $start_position; $i <= count($array) - $len; $i++)
{
$result_array[$result_len - $len] = $array[$i];
combinations($array, $len-1, $i+1, $result_array, $result_len, $general_array);
}
}
combinations($array, 3, 0, $array_result, 3, $array_general);
echo "<pre>";
print_r($array_general);
echo "</pre>";
相同的解决方案,但在javascript:
var newArray = [1, 2, 3, 4, 5];
var arrayResult = [];
var arrayGeneral = [];
function combinations(newArray, len, startPosition, resultArray, resultLen, arrayGeneral) {
if(len === 0) {
var tempArray = [];
resultArray.forEach(value => tempArray.push(value));
arrayGeneral.push(tempArray);
return;
}
for (var i = startPosition; i <= newArray.length - len; i++) {
resultArray[resultLen - len] = newArray[i];
combinations(newArray, len-1, i+1, resultArray, resultLen, arrayGeneral);
}
}
combinations(newArray, 3, 0, arrayResult, 3, arrayGeneral);
console.log(arrayGeneral);
如果你可以使用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的答案是完整的,不幸的是我还不能投票。这个答案很简单,但只适用于你想要三样东西的时候。
#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;
}
短快C实现
#include <stdio.h>
void main(int argc, char *argv[]) {
const int n = 6; /* The size of the set; for {1, 2, 3, 4} it's 4 */
const int p = 4; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
int comb[40] = {0}; /* comb[i] is the index of the i-th element in the combination */
int i = 0;
for (int j = 0; j <= n; j++) comb[j] = 0;
while (i >= 0) {
if (comb[i] < n + i - p + 1) {
comb[i]++;
if (i == p - 1) { for (int j = 0; j < p; j++) printf("%d ", comb[j]); printf("\n"); }
else { comb[++i] = comb[i - 1]; }
} else i--; }
}
要查看它有多快,请使用这段代码并测试它
#include <time.h>
#include <stdio.h>
void main(int argc, char *argv[]) {
const int n = 32; /* The size of the set; for {1, 2, 3, 4} it's 4 */
const int p = 16; /* The size of the subsets; for {1, 2}, {1, 3}, ... it's 2 */
int comb[40] = {0}; /* comb[i] is the index of the i-th element in the combination */
int c = 0; int i = 0;
for (int j = 0; j <= n; j++) comb[j] = 0;
while (i >= 0) {
if (comb[i] < n + i - p + 1) {
comb[i]++;
/* if (i == p - 1) { for (int j = 0; j < p; j++) printf("%d ", comb[j]); printf("\n"); } */
if (i == p - 1) c++;
else { comb[++i] = comb[i - 1]; }
} else i--; }
printf("%d!%d == %d combination(s) in %15.3f second(s)\n ", p, n, c, clock()/1000.0);
}
使用cmd.exe (windows)测试:
Microsoft Windows XP [Version 5.1.2600]
(C) Copyright 1985-2001 Microsoft Corp.
c:\Program Files\lcc\projects>combination
16!32 == 601080390 combination(s) in 5.781 second(s)
c:\Program Files\lcc\projects>
祝你有愉快的一天。