164 lines
3.4 KiB
C
164 lines
3.4 KiB
C
|
|
#include <stdio.h>
|
|
#include <time.h>
|
|
|
|
/************************** Function Prototypes **************************/
|
|
|
|
int shift(
|
|
int number,
|
|
int setOneSize,
|
|
int setTwoSize,
|
|
int subtractionValue,
|
|
int shiftIteration,
|
|
int subtractionIteration,
|
|
int **permutations_next_index);
|
|
|
|
int subtract(
|
|
int number,
|
|
int setOneSize,
|
|
int setTwoSize,
|
|
int subtractionValue,
|
|
int shiftIteration,
|
|
int subtractionIteration,
|
|
int **permutations_next_index);
|
|
|
|
/************************** Algorithm **************************/
|
|
|
|
int shift(
|
|
long number,
|
|
int setOneSize,
|
|
int setTwoSize,
|
|
int subtractionValue,
|
|
int shiftIteration,
|
|
int subtractionIteration,
|
|
int **permutations_next_index)
|
|
{
|
|
|
|
int i;
|
|
for (i = 0; i < setOneSize; ++i)
|
|
{
|
|
if (shiftIteration >= setOneSize)
|
|
{
|
|
return 0;
|
|
}
|
|
number = number << 1;
|
|
shiftIteration++;
|
|
*(*permutations_next_index += 1) = number;
|
|
subtractionValue = (subtractionValue << 1) + 1;
|
|
subtract(
|
|
number,
|
|
setOneSize,
|
|
setTwoSize,
|
|
subtractionValue,
|
|
shiftIteration,
|
|
subtractionIteration,
|
|
permutations_next_index);
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
int subtract(
|
|
long number,
|
|
int setOneSize,
|
|
int setTwoSize,
|
|
int subtractionValue,
|
|
int shiftIteration,
|
|
int subtractionIteration,
|
|
int **permutations_next_index)
|
|
{
|
|
|
|
int i;
|
|
for (i = 0; i < setTwoSize - 1; ++i)
|
|
{
|
|
if (subtractionIteration >= setTwoSize - 1)
|
|
{
|
|
return 0;
|
|
}
|
|
number -= subtractionValue;
|
|
subtractionIteration++;
|
|
subtractionValue = subtractionValue << 1;
|
|
*(*permutations_next_index += 1) = number;
|
|
shift(
|
|
number,
|
|
setOneSize,
|
|
setTwoSize,
|
|
subtractionValue,
|
|
shiftIteration,
|
|
subtractionIteration,
|
|
permutations_next_index);
|
|
}
|
|
return 0;
|
|
}
|
|
|
|
// unsigned long factorial(unsigned long n)
|
|
// {
|
|
// return (n == 1 || n == 0) ? 1 : factorial(n - 1) * n;
|
|
// }
|
|
|
|
/************************** Main **************************/
|
|
|
|
int main(int argc, char const *argv[])
|
|
{
|
|
|
|
if (argc != 4)
|
|
{
|
|
printf(" Usage: ./algorithm4.py [set 1 count] [set 2 count]\n");
|
|
return 0;
|
|
}
|
|
|
|
// if (!isdigit(argv[1]) || !isdigit(argv[2]))
|
|
// {
|
|
// printf("ERROR: invalid parameters. Please input numbers!");
|
|
// printf(" Usage: ./algorithm4.py [set 1 count] [set 2 count]\n");
|
|
// return 0;
|
|
// }
|
|
|
|
int setOne = atoi(argv[1]);
|
|
int setTwo = atoi(argv[2]);
|
|
|
|
long permutation_count = atoi(argv[3]);
|
|
|
|
long permutations[permutation_count];
|
|
|
|
// create a pointer to access the next free index of the array
|
|
int *permutations_next_index = &permutations[0];
|
|
|
|
// initialize the first position in the array with 0b000011111
|
|
long num = 1;
|
|
int j;
|
|
for (j = 1; j < setTwo; ++j)
|
|
{
|
|
num = (num << 1) + 1;
|
|
}
|
|
permutations[0] = num;
|
|
|
|
|
|
clock_t begin = clock();
|
|
|
|
// call the shift function and begin the algorithm's calculations
|
|
shift(permutations[0], setOne, setTwo, 0, 0, 0, &permutations_next_index);
|
|
|
|
clock_t end = clock();
|
|
double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
|
|
|
|
/* Print out all the permutations (in decimal format) */
|
|
// printf("[\n");
|
|
// int i;
|
|
// for (i = 0; i < permutation_count; ++i)
|
|
// {
|
|
// if (i == (permutation_count - 1))
|
|
// {
|
|
// printf("%4d", permutations[i]);
|
|
// }
|
|
// else
|
|
// {
|
|
// printf("%4d, ", permutations[i]);
|
|
// }
|
|
// }
|
|
// printf("\n]\n");
|
|
|
|
printf("Execution Time: %f seconds\n", time_spent);
|
|
|
|
return 0;
|
|
}
|