Декартово произведение n-множеств в C

Я пишу программу на 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;
 }

c cartesian
person Anton Petkov    schedule 18.03.2021    source источник
comment
Отвечает ли это на ваш вопрос? алгоритм эффективного декартова произведения   -  person Mark Benningfield    schedule 18.03.2021
comment
К сожалению, нет, я уже искал, но ничего не нашел относительно проблемы.   -  person Anton Petkov    schedule 18.03.2021
comment
Отредактируйте в своем посте пример содержимого входного файла, который вы используете.   -  person ryyker    schedule 18.03.2021
comment
Вы можете реализовать одометр, как в моем ответе здесь. (Извините за вилку.)   -  person M Oehm    schedule 18.03.2021
comment
(Прошу прощения, но как предлагаемый дубликат является хорошим ответом на вопрос, как реализовать декартово множество для n элементов?)   -  person M Oehm    schedule 18.03.2021
comment
Информация об итерации по n последовательностям находится здесь .   -  person Eric Postpischil    schedule 18.03.2021

Ответы (1)


arrow_upward
1
arrow_downward

Вы можете реализовать декартовы произведения с помощью счетчика одометра:

  • Установите все текущие элементы на первые элементы в каждом списке.
  • Обработать текущее состояние, например распечатайте это.
  • Продвиньте первый список. Если вы дойдете до конца, сбросьте состояние на начало этого списка и перейдите к следующему списку и так далее. Если вы дойдете до конца последнего списка, все готово.

Итак, предполагая, что вы считали информацию из файлов в 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;
}

Этот подход не ограничивается тремя списками. (Если вы точно знаете, сколько у вас списков, вы, конечно, можете использовать вложенные циклы.)

person M Oehm    schedule 18.03.2021