Generators for Certain Alternating Groups With Applications to Cryptography for LeetArxiv

Symmetric.c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//Run : clear && gcc Symmetric.c -lm -o m.o && ./m.o
//Code walkthrough : https://leetarxiv.substack.com/p/generators-for-certain-alternating
int factorial(int n)
{
	assert(n > 0 && n < 12);
	int result = 1;for (int i = 2; i <= n; i++){result *= i;}
	return result;
}

void swap(int *a, int *b) 
{
	int temp = *a;
	*a = *b;
	*b = temp;
}


void PrintCycleNotationAndParity(int length, int *array)
{
	int parity = 0;
	//Initialize all visits to 0 (not visited)
	int *visited = calloc(length, sizeof(int));
	for(int i = 0; i < length; i++)
	{
		if(!visited[i])
		{
			printf("(");
			int current = i;
			printf("%d", current + 1);
			visited[current] = 1;
			current = array[current] - 1;
			for(; current != i; current = array[current] - 1)
			{
				printf(" %d", current + 1);
				visited[current] = 1;
			}
			printf(")");
			parity += 1;
		}
	}
	free(visited);
	if(parity % 2 == 0){printf("\tOdd");}
	else{printf("\tEven");}
}


void GeneratePermutations(int *arr, int start, int n)
{
	if(start == n) 
	{
		//Print the current permutation
		for(int i = 0; i < n; i++){printf("%d ", arr[i]);}
		
		//Print Cycle Notation and Parity
		PrintCycleNotationAndParity(n, arr);
		printf("\n");
		return;
	}
	for(int i = start; i < n; i++)
	{
		swap(&arr[start], &arr[i]);
		GeneratePermutations(arr, start + 1, n);
		swap(&arr[start], &arr[i]);  
	}
}

int main()
{
	int n = 3;  
	int arr[n];
	//Initialize the array with 1 to n
	for(int i = 0; i < n; i++){arr[i] = i + 1;}
	printf("All permutations in S_%d:\n", n);
	GeneratePermutations(arr, 0, n);
	return 0;
}