Cartesian Product of n sets of size s in C

Question

I am trying create an algorithm which will list the Cartesian product of n sets (NoD) which are of size s (SoD). This seems to work in almost all cases, following the expected pattern of counting upward (you can observe this if you print the Cartesian product of 3 sets of 4). However, there are two major issues outlined below:

(1) For some values the power function seems to be giving me some off answers. If I want 2 sets of 14 I get 196 (which is correct since 14^2 = 196), however if I want 2 sets of 20 the computer is telling me 399 (it should be 400). Is this because I typecasted doubles into integers (the math header only takes and produces doubles) or something weird?

(2) Is there a cutoff for how many lines by computer is willing to print? If the input gets large enough, though the algorithm's combination method seems to be working, the first line it prints is not [0 0 0 0] but something like [3 2 1 4]. I can literally see it ticking through all possible sets but then it won't let me scroll all the way back and read them.

#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);
}

Do not use floating-point computations when you want integer arithmetic. — John Bollinger, Jun 02 '18 at 00:25
@JohnBollinger I corrected that typo. Additionally, I meant to say double, not float (since the math header file deals in doubles and not integers). Could that still be the issue? — Krivand, Jun 02 '18 at 00:51
`double` is still a floating-point type. Do not use floating-point computations when you want integer arithmetic. Truncation / rounding errors are a common problem arising from doing so. — John Bollinger, Jun 02 '18 at 00:57
@JohnBollinger thanks, I'll just use a loop to do the power calculation instead. — Krivand, Jun 02 '18 at 01:26
Please don't use floating point. See [Is Floating Point Broken?](https://stackoverflow.com/questions/588004/is-floating-point-math-broken) — Ṃųỻịgǻňạcểơửṩ, Jun 02 '18 at 01:48

Cartesian Product of n sets of size s in C

0 Answers0