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 %s\n", *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 %s\n", *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;
}

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

C 中 n 集的笛卡尔积

Cartesian Product of n-sets in C

c

cartesian