C语言中创建变长字符串的数组数组及整合幂集分组数组并通过三重指针传递的方法咨询
C语言中创建变长字符串的数组数组及整合幂集分组数组并通过三重指针传递的方法咨询
最近我在折腾一个C语言的小项目:生成一个集合的幂集,而且要求幂集里的子集必须按元素个数(基数)分组排序——先输出空集,再是所有单元素子集,接着双元素、三元素……直到全集。Python里用itertools.combinations几行代码就搞定了,但我想自己用纯C实现,现在已经写出了能正确输出结果的代码,但卡在了一个点上:怎么把按基数分组的各个字符串数组整合到一个大数组里,并用三重指针char ***来传递这个大数组?
先给大家看看我目前的完整代码:
#include <stdio.h> void length(char *set, int *n) { *n = 0; for (int i = 0; set[i] != '\0'; i++) { *n = *n + 1; } } void expo(int *n, int *x) { *x = 1; for (int i = 0; i < *n; i++) { *x = *x * 2; } } void bin_cof(int *n, int *k, int *nCk) { int _k; *nCk = 1; if (*k > *n - *k) { _k = *n - *k; } else { _k = *k; } for (int i = 0; i < _k; i++) { *nCk = *nCk * (*n - i) / (1 + i); } } void edges(char *set, char **current, char **last, int *n, int *k) { for (int i = 0; i < *k; i++) { current[i] = set + i; } current[*k] = set + *n; for (int i = 0; i < *k; i++) { last[i] = set + i + *n - *k; } last[*k] = set + *n; } void successor(char *set, char **current, char **last, int *k) { int con; for (int i = *k - 1; i >= 0; i--) { if (current[i] != last[i]) { con = i; break; } } char *i = set; for (; i != current[con]; i++); int poi = (int)(i - set); for (; con < *k; con++) { current[con] = set + 1 + poi; poi++; } } void gen_comb(char *set, int *n, int *k, int *nCk, char **pointer) { char *current[*k + 1], *last[*k + 1]; edges(set, current, last, n, k); for (int j = 0; j < *nCk; j++) { for (int i = 0; i < *k + 1; i++) { pointer[j][i] = *(current[i]); } successor(set, current, last, k); } } void powerset(char *set) { int n; length(set, &n); for (int k = 0; k <= n; k++) { int nCk; bin_cof(&n, &k, &nCk); char combination[nCk][k+1], *pointer[nCk]; for (int i = 0; i < nCk; i++) { pointer[i] = combination[i]; } gen_comb(set, &n, &k, &nCk, pointer); printf("\nSet x has %d subset with cardinality %d :\n{ %s", nCk, k, pointer[0]); for (int i = 1; i < nCk; i++) { printf(", %s", pointer[i]); } printf(" }\n"); } printf("\n"); } int main(void) { for (;;) { char set[30]; printf("Give me a string set, x = "); if (scanf("%s", set) == 0) { printf("\nError!!"); break; } int n, x; length(set, &n); expo(&n, &x); printf("\n\nIn total set x has %d subsets which are sorted in the order of low to \nhigh cardinality below ->\n ", x); powerset(set); printf("\n"); } return 1; }
现在这个代码运行是没问题的,比如输入ABCDEF,会输出按基数分组的所有子集:从空集(基数0)到全集(基数6),每个分组对应一个字符串数组,比如基数0的是combination0[1][1],基数1的是combination1[6][2],一直到基数6的combination6[1][7]。
我的问题是:怎么把这些长度各不相同的分组数组整合到一个大的数组结构里,然后用char ***这种三重指针来传递这个大结构?毕竟每个分组的行数(组合数)和列数(k+1)都不一样,直接用固定大小的数组肯定不行,想请教下有没有合适的实现思路?
内容来源于stack exchange
相关产品推荐
相关产品推荐

