Декартово произведение n множеств размера s в C - PullRequest
Новая
       32

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

0 голосов
/ 02 июня 2018

Я пытаюсь создать алгоритм, который будет перечислять декартово произведение n наборов (NoD), которые имеют размер s (SoD).Похоже, что это работает почти во всех случаях, следуя ожидаемой схеме подсчета в сторону увеличения (вы можете наблюдать это, если печатаете декартово произведение из 3 наборов по 4).Тем не менее, есть две основные проблемы, описанные ниже:

(1) Для некоторых значений функция мощности, кажется, дает мне некоторые ответы.Если я хочу 2 набора по 14, я получаю 196 (что правильно, поскольку 14 ^ 2 = 196), однако, если я хочу 2 набора по 20, компьютер сообщает мне 399 (это должно быть 400).Это потому, что я типизировал удваивающиеся числа до целых (математический заголовок только принимает и производит числа)?Если ввод становится достаточно большим, хотя метод комбинирования алгоритма, кажется, работает, первая строка, которую он печатает, - это не [0 0 0 0], а что-то вроде [3 2 1 4].Я буквально вижу, как он тикает через все возможные наборы, но тогда он не даст мне прокрутить весь путь назад и прочитать их. 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

void counter(int* NoD, int* SoD, int* ticker, int* indexer, int* numPoss)
{
    for (int i = 0; i < *numPoss; i++)
    {
        printf("\n");
        for (int k = 0; k < *NoD; k++)
        {
        printf("%i\t", *(ticker+k));

        }
        if (*(ticker +*indexer) == (*SoD-1))
        {
            if (*(ticker + *indexer -1) < *SoD-1)
            {
                *(ticker + *indexer -1) = *(ticker + *indexer -1)+1;
                *indexer = *NoD-1;
                *(ticker +*indexer) = 0;
            }
            else
            {
                while (*(ticker +*indexer) >= *SoD-1)
                {
                    *indexer = *indexer - 1;
                }
                *(ticker + *indexer) = *(ticker + *indexer)+1;
                    for (int i = *indexer+1; i < *NoD; i++)
                    {
                        *indexer = *indexer +1;
                        *(ticker +*indexer) = 0;
                    }
            }
        }
    else
    {
        *(ticker +*indexer) = *(ticker +*indexer)+1;
    }
    }
    }


void main()
{
int NoD, SoD;
puts("enter number of sets\n");
scanf("%i", &NoD);
puts("enter size of sets\n");
scanf("%i", &SoD);
int* ticker = (int*)malloc(NoD*sizeof(int));
    for (int i = 0; i < NoD; i++)
    {
        *(ticker + i) = 0;
    }

int indexer = NoD-1;
int numPoss = (int)pow((double)SoD,(double)NoD);
counter(&NoD, &SoD, ticker, &indexer, &numPoss);
printf("the number of cartesian products is %i\n", numPoss);
}
...