C中n集的笛卡尔乘积

Question

我正在编写一个C程序，该程序应该打印n集合的笛卡尔乘积，其中每个集合的元素是一个文件中的文本行，n文件的名称作为命令行参数传递。到目前为止，我设法把每一行都读成了字符串矩阵。然而，我无法理解如何编写打印产品的算法。

以下是我目前所拥有的：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define LSIZ 128
#define RSIZ 10
int main(int argc, char *argv[])
{
char input[LSIZ];
int n = argc;
char *sets[argc - 1][RSIZ];
int i = 0;
int j = 0;
int y = 1;
FILE *file = NULL;
if (argc == 1)
{
printf("nofiles");
}
else
{
while (--argc > 0)
{
if ((file = fopen(argv[y], "r")) == NULL)
{
printf("cat: failed to open %sn", *argv);
return 1;
}
else
{
for (j = 0; j < RSIZ && fgets(input, sizeof(input), file); ++j)
{
int lineLen = strlen(input) + 1;
sets[i][j] = strncpy(malloc(lineLen), input, lineLen);
}
fclose(file);
j = 0;
}
i++;
y++;
}
}
return 0;
}

Answer 1

您可以使用类似里程表的计数器来实现笛卡尔乘积：

• 将所有当前项目设置为每个列表中的第一个项目
• 处理当前状态，例如打印
• 推进第一个列表。如果到达末尾，请将状态重置为该列表的开头，然后继续下一个列表，依此类推。如果到达最后一个列表的末尾，则完成

因此，假设您已将文件中的信息读取到以NULL结尾的字符串列表中，则可以执行以下操作：

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
int main(int argc, char *argv[])
{
const char *adj1[] = {"little", "big", "huge", NULL};
const char *adj2[] = {"red", "yellow", "grey", "orange", NULL};
const char *noun[] = {"house", "car", NULL};

const char **list[3] = {adj1, adj2, noun};
const char **curr[3];

unsigned n = sizeof(list) / sizeof(*list);
unsigned count = 0;
bool done = false;

for (unsigned i = 0; i < n; i++) {
curr[i] = list[i];
}

while (!done) {
unsigned i = 0;
printf("%s %s %sn", *curr[0], *curr[1], *curr[2]);
count++;
curr[i]++;
while (*curr[i] == NULL) {
curr[i] = list[i];      // back to beginning
i++;                    // move to next list

if (i == n) {           // stop when the last list is exhausted
done = true;
break;
}
curr[i]++;              // ... and increment that
}      
}

printf("%u combinations.n", count);
return 0;
}

这种方法并不局限于三个列表。(如果你确切地知道你有多少列表，你当然可以使用嵌套循环。(