我正在使用组合学,我想知道是否有一个算法打印给定数组的子序列的所有布置.也就是说,如果我给这个算法的序列“ABCDEF”它将打印： 一个, B, C, d, E, F, AB, AC, 广告, AE, AF, 公元前, BD, 是
一个,
B,
C,
d,
E,
F,
AB,
AC,
广告,
AE,
AF,
公元前,
BD,
是,
BF,
光盘,
CE,
CF,
DE,
DF,
EF,
ABC,
ABD,
ABE,
ABF,
ACD,
高手,
ACF,
ADE,
ADF,
AEF,
BCD,
BCE,
BCF,
BDE,
BDF,
BEF,
CDE,
CDF,
CEF,
DEF,
A B C D,
ABCE,
ABCF,
ABDE,
ABDF,
ABEF,
ACDE,
ACDF,
ACEF,
ADEF,
BCDE,
BCDF,
BCEF,
BDEF,
CDEF,
ABCDE,
ABCDF,
ABCEF,
ABDEF,
ACDEF,
BCDEF,
ABCDEF,
或者对于一个更简单的情况,如果我给它1234,它将打印：
1,2,3,4,12,13,14,23,24,34,123,124,134,234,1234.
正如你所看到的那样,它不是一个任意的排列,它只是一个子序列的最后一个成员的排列,它仍然会重新获得一个子序列.
我试图在c中创建一个函数但是我真的很困惑,我的想法是创建一个保持子序列大小的int L,另一个树整数保持子序列的头部,一个标志着与头部的分离以及与给定数量的角色滑动的分离,但它太过于混乱.
谁能帮我这个 ？
我的代码是：
int Stringsize( char m[] ){
int k;
for(k=0;;k++){
if( m[k] == '\0') break;
}
return (k-1);
}
void StringOrdM(char m[]){
int q,r,s,k;
for(k=0;k<=Stringsize(m);k++)
for(q=0;q<=Stringsize(m);q++)
for(s=q;s<=Stringsize(m);s++ )
printf("%c",m[q]);
for(r=q+1; r<=Stringsize(m) && (r-q+1)<= k ;r++ )
printf("%c", m[r] );
}
对于ABCD,它打印A,A,A,A,B,B,B,C,C,D,AA,AB,AC,AD,BC,BD,CC,CD,DD,…所以它不是是的,因为它不断重复A的4次B等等,当它应该是A,B,C,D,AB,AC,AD,BC,BD,CD,……
根据torstenvl的回答,我做了这个代码并且它完美地工作.如果有任何问题请告诉我.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void)
{
char str[] = "1234";
size_t len = strlen(str); // Array length (in elements)
char *A = malloc(sizeof(char) * len);
strcpy(A,str);
size_t elbp = (1<<len) - 1; // Element selection bit pattern
size_t i, j; // Iterators
int a = 0, b = 0, n = 0;
char **arr = malloc(sizeof(char*) * (10000)); //allocating memory
if (A[0] >= 'A' && A[0] <= 'Z') //If the string given is "ABCD...." transfer 'A' to '1' ; 'C' to '3' ...etc
for(int i = 0; i < len; i++)
A[i] = A[i] - 'A' + '1';
// Cycle through all the bit patterns
for (i = 1; i<=elbp; i++)
{
arr[b] = malloc(sizeof(char) * len);
// For each bit pattern, store in arr[b] the 'checked' elements
for (j = 0, a = 0; j < len; j++)
if (i & (1<<j))
arr[b][a++] = A[j];
b++;
}
int *num = calloc(sizeof(int) ,10000);
for (i = 0; i < b; i++)
num[i] = strtol(arr[i], NULL, 10); //convert char to int
for (i = 0; i < b; i++) //sort array numbers from smallest to largest
for (a = 0; a < i; a++)
if (num[i] < num[a])
{
n = num[i];
num[i] = num[a];
num[a] = n;
}
char *result = calloc(sizeof(char),10000);
for (i = 0, a = 0; i<b; i++)
a += sprintf(&result[a], "%d,", num[i]); //convert int to char and store it in result[a]
result[a - 1] = '\0'; //remove the last ','
len = strlen(result);
if (str[0] >= 'A' && str[0] <= 'Z') //if the string given is "ABCD..." transfer '1' to 'A' ; '12' to 'AB' ; '13' to 'AC'.....etc
for (i = 0; i < len; i++)
if(result[i] != ',')
result[i] = 'A' + (result[i] - '1') ;
///test
printf("%s",result);
return 0;
}
“1234”的输出：
1,2,3,4,12,13,14,23,24,34,123,124,134,234,1234
“123456789”的输出：
1,2,3,4,5,6,7,8,9,12,13,14,15,16,17,18,19,23,24,25,26,27,28,29,34,35,36,37,38,39,45,46,47,48,49,56,57,58,59,67,68,69,78,79,89,123,124,125,126,127,128,129,134,135,136,137,138,139,145,146,147,148,149,156,157,158,159,167,168,169,178,179,189,234,235,236,237,238,239,245,246,247,248,249,256,257,258,259,267,268,269,278,279,289,345,346,347,348,349,356,357,358,359,367,368,369,378,379,389,456,457,458,459,467,468,469,478,479,489,567,568,569,578,579,589,678,679,689,789,1234,1235,1236,1237,1238,1239,1245,1246,1247,1248,1249,1256,1257,1258,1259,1267,1268,1269,1278,1279,1289,1345,1346,1347,1348,1349,1356,1357,1358,1359,1367,1368,1369,1378,1379,1389,1456,1457,1458,1459,1467,1468,1469,1478,1479,1489,1567,1568,1569,1578,1579,1589,1678,1679,1689,1789,2345,2346,2347,2348,2349,2356,2357,2358,2359,2367,2368,2369,2378,2379,2389,2456,2457,2458,2459,2467,2468,2469,2478,2479,2489,2567,2568,2569,2578,2579,2589,2678,2679,2689,2789,3456,3457,3458,3459,3467,3468,3469,3478,3479,3489,3567,3568,3569,3578,3579,3589,3678,3679,3689,3789,4567,4568,4569,4578,4579,4589,4678,4679,4689,4789,5678,5679,5689,5789,6789,12345,12346,12347,12348,12349,12356,12357,12358,12359,12367,12368,12369,12378,12379,12389,12456,12457,12458,12459,12467,12468,12469,12478,12479,12489,12567,12568,12569,12578,12579,12589,12678,12679,12689,12789,13456,13457,13458,13459,13467,13468,13469,13478,13479,13489,13567,13568,13569,13578,13579,13589,13678,13679,13689,13789,14567,14568,14569,14578,14579,14589,14678,14679,14689,14789,15678,15679,15689,15789,16789,23456,23457,23458,23459,23467,23468,23469,23478,23479,23489,23567,23568,23569,23578,23579,23589,23678,23679,23689,23789,24567,24568,24569,24578,24579,24589,24678,24679,24689,24789,25678,25679,25689,25789,26789,34567,34568,34569,34578,34579,34589,34678,34679,34689,34789,35678,35679,35689,35789,36789,45678,45679,45689,45789,46789,56789,123456,123457,123458,123459,123467,123468,123469,123478,123479,123489,123567,123568,123569,123578,123579,123589,123678,123679,123689,123789,124567,124568,124569,124578,124579,124589,124678,124679,124689,124789,125678,125679,125689,125789,126789,134567,134568,134569,134578,134579,134589,134678,134679,134689,134789,135678,135679,135689,135789,136789,145678,145679,145689,145789,146789,156789,234567,234568,234569,234578,234579,234589,234678,234679,234689,234789,235678,235679,235689,235789,236789,245678,245679,245689,245789,246789,256789,345678,345679,345689,345789,346789,356789,456789,1234567,1234568,1234569,1234578,1234579,1234589,1234678,1234679,1234689,1234789,1235678,1235679,1235689,1235789,1236789,1245678,1245679,1245689,1245789,1246789,1256789,1345678,1345679,1345689,1345789,1346789,1356789,1456789,2345678,2345679,2345689,2345789,2346789,2356789,2456789,3456789,12345678,12345679,12345689,12345789,12346789,12356789,12456789,13456789,23456789,123456789
“ABCDEF”的输出：
A,B,C,D,E,F,AB,AC,AD,AE,AF,BC,BD,BE,BF,CD,CE,CF,DE,DF,EF,ABC,ABD,ABE,ABF,ACD,ACE,ACF,ADE,ADF,AEF,BCD,BCE,BCF,BDE,BDF,BEF,CDE,CDF,CEF,DEF,ABCD,ABCE,ABCF,ABDE,ABDF,ABEF,ACDE,ACDF,ACEF,ADEF,BCDE,BCDF,BCEF,BDEF,CDEF,ABCDE,ABCDF,ABCEF,ABDEF,ACDEF,BCDEF,ABCDEF