// PermuteArray.cpp : Defines the entry point for the console application.
// Copyright (C) April 30, 2011 -  George W. Taylor - All rights reserved

// This console app takes as command line arguments the number of digits in
// the desired set. For example, an 8 digit set will consist of the numbers
// (0,1,2,3,4,5,6,7)

// All permutations of the desired set will be generated using the algorithm
// discussed in "A Permutation on Combinatorial Algorithms" and each permutation
// will be verified against set permuted via conventional means.

// See http://www.tropicalcoder.com/APermutationOnCombinatorialAlgorithms.htm

#include <Windows.h>
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
#include <memory.h>

#define MAX_ELEMENTS 10
#define MIN_ELEMENTS 4

UINT64 indexPermutations;
BYTE SpareSet[MAX_ELEMENTS];


// Generates the next permutation in the series in place
void GeneratePermutation(LPBYTE Elements, BYTE setSizeBytes)
{
 // Find the largest index k such that a[k] < a[k + 1].
 short k, l, largestIndex = -1;
 for(k = (setSize - 2); k >= 0; k--)
 {
     if(Elements[k] < Elements[k+1])
     {
        if(k > largestIndex)largestIndex = k; 
     }
 }

 // If no such index exists, the permutation is the last permutation.
 if(largestIndex == -1)return;

 // Find the largest index l such that a[k] < a[l].
 // Since k + 1 is such an index, l is well defined and satisfies k < l.
 k = largestIndex;
 largestIndex = -1;
 for(l = (setSize - 1); l >= 0; l--)
 {
     if(Elements[k] < Elements[l])
     {
        if(l > largestIndex)largestIndex = l; 
     }
 }

 // Swap a[k] with a[l].
 l = largestIndex;
 BYTE tmp = Elements[k];
 Elements[k] = Elements[l];
 Elements[l] = tmp;

 // Reverse the sequence from a[k + 1] up to and including the final element a[n].
 ++k; l = setSizeBytes - 1;
 while(l > k)
 {
       tmp = Elements[k];
       Elements[k] = Elements[l];
       Elements[l] = tmp;
       ++k; --l;
 }
}

// This function will verify each permutation generated
// by checking it against the independently generated permutation.
// SpareSet[] is initialized together with Permutations[0]
// with the same set before we begin.
// This function is called every single time
// a new permutation is created in Permutations[]
// before indexPermutations is advanced, to stay in sync.
bool ValidatePermutation(LPBYTE pCurrentPermutation, BYTE setSizeBytes)
{
 GeneratePermutation(SpareSet, setSizeBytes);
 for(BYTE tmp = 0; tmp < setSizeBytes; tmp++)
 {
     if(pCurrentPermutation[tmp] != SpareSet[tmp])
     {
        printf("Error: Permuation is invalid!\n");
        return false;
     }
 }
 return true;
}

 // Get the factorial of NumDigits >= 3
UINT64 Factorial(unsigned NumDigits)
{
 UINT64 factorial = 2;
 for(unsigned n = 3; n <= NumDigits; n++)
 {
     factorial *= n;
 }
 return factorial;
}

unsigned SubtractArrays(LPBYTE Larger, LPBYTE Smaller, BYTE setSizeBytes)
{
 char i, Elements[MAX_ELEMENTS+1];
 UINT64 larger, smaller;

 for(i = 0; i < setSizeBytes; i++)
 {
     Elements[i] = Larger[i] + '0';
 }
 Elements[i] = '\0';
 larger = _atoi64(Elements);
 for(i = 0; i < setSizeBytes; i++)
 {
     Elements[i] = Smaller[i] + '0';
 }
 Elements[i] = '\0';
 smaller = _atoi64(Elements);
 return (unsigned)(larger - smaller);
}

void AddArray(LPBYTE Digits, UINT value, BYTE setSizeBytes)
{
 char i, Elements[MAX_ELEMENTS+1];
 for(i = 0; i < setSizeBytes; i++)
 {
     Elements[i] = Digits[i] + '0';
 }
 Elements[i] = '\0';
 UINT64 digits = _atoi64(Elements) + value;
 _i64toa(digits, Elements, 10);

 // Need leading zero?
 i = (char)strlen(Elements);
 if(i == setSizeBytes)
 {
    for(i = 0; i < setSizeBytes; i++)
    {
        Digits[i] = Elements[i] - '0';
    }
 }else
 {
    Digits[0] = 0;
    for(i = 0; i < (setSizeBytes - 1); i++)
    {
        Digits[i+1] = Elements[i] - '0';
    }
 }
}

// Writes 'count' permutations to global Permutations at [curIndex]
void GeneratePermutations(LPBYTE Permutations, UINT64 count, BYTE setSizeBytes)
{
 LPBYTE pTable;

 for(UINT64 i = 0; i < count; i++)
 {
     // Index is pointing at the next location.
     // Copy previous permutation to next location and permutate in place...
     memcpy(&Permutations[indexPermutations], &Permutations[indexPermutations - setSizeBytes], setSizeBytes);
     pTable = &Permutations[indexPermutations];

     // Find the largest index k such that a[k] < a[k + 1].
     short k, l, largestIndex = -1;
     for(k = (setSize - 2); k >= 0; k--)
     {
         if(pTable[k] < pTable[k+1])
         {
            if(k > largestIndex)largestIndex = k; 
         }
     }
     // If no such index exists, the permutation is the last permutation.
     if(largestIndex == -1)break;

     // Find the largest index l such that a[k] < a[l].
     k = largestIndex;
     largestIndex = -1;
     for(l = (setSize - 1); l >= 0; l--)
     {
         if(pTable[k] < pTable[l])
         {
            if(l > largestIndex)largestIndex = l; 
         }
     }
     // Since k + 1 is such an index, l is well defined and satisfies k < l.

     // Swap a[k] with a[l].
     l = largestIndex;
     BYTE tmp = pTable[k];
     pTable[k] = pTable[l];
     pTable[l] = tmp;
     // Reverse the sequence from a[k + 1] up to and including the final element a[n].
     ++k; l = setSizeBytes - 1;
     while(l > k)
     {
           tmp = pTable[k];
           pTable[k] = pTable[l];
           pTable[l] = tmp;
           ++k; --l;
     }
     if(!ValidatePermutation(&Permutations[indexPermutations], setSizeBytes))
     {
        break; // <-- debug breakpoint
     }	 
     indexPermutations += setSizeBytes;
 }
}

void addDifferences(LPBYTE Permutations, UINT64 count, UINT64 offset, BYTE setSizeBytes)
{
 for(UINT64 n = 0; n < count; n++)
 {
     memcpy(&Permutations[indexPermutations], &Permutations[indexPermutations - setSizeBytes], setSizeBytes);
     unsigned difference = SubtractArrays(&Permutations[offset], &Permutations[offset - setSizeBytes], setSizeBytes);
     AddArray(&Permutations[indexPermutations], difference, setSizeBytes);
     if(!ValidatePermutation(&Permutations[indexPermutations], setSizeBytes))
     {
        break;
     }	 
     offset -= setSizeBytes;
     indexPermutations += setSizeBytes;
 }
}

// Generate all permutations from the set of size 'setSizeBytes'
// initially found at Permutations[0]
void recurseTree(LPBYTE Permutations, int digits, int setSizeBytes)
{
 if(digits > 3)
 {
    recurseTree(Permutations, digits-1, setSizeBytes);
 }

 // How many permutations required for current subset?
 UINT64 count = Factorial(digits)/2;
 if(digits > 3)++count;

 // From this subtract what we already have from previous subsets...
 int numDigits = digits;
 while(--numDigits >= 3)
 {
       count -= Factorial(numDigits);
 }

 // Generate the permutations for upper half of main body
 GeneratePermutations(Permutations, count, setSizeBytes);
 
 // Remainder for current subset computed by adding differences.
 // Iterating backwards through the permutations just generated,
 // get the differences and add them to current/next permutations.
 // ('indexPermutations' was incremented by GeneratePermutations()) 
 UINT64 offset = indexPermutations - (setSizeBytes * 2);
 count = Factorial(digits)/2-1;
 addDifferences(Permutations, count, offset, setSizeBytes);
 // ('indexPermutations' was incremented by addDifferences())

 if(digits > 3)
 {
    // Are we done yet?
    if((indexPermutations/setSizeBytes) == Factorial(setSizeBytes))return; 

    // Now get the next permutation in the main sequence
	// - the unique centre piece for the set
    GeneratePermutations(Permutations, 1, setSizeBytes);
    recurseTree(Permutations, digits-1, setSizeBytes);
 }
}

void ShowPermutations(LPBYTE Permutations, UINT64 nCountPermutations, BYTE setSizeBytes)
{
 UINT64 nIndexPermutations = 0;
 for(UINT64 i = 0; i < nCountPermutations; i++)
 {
     for(BYTE j = 0; j < setSizeBytes; j++)
     {
         printf("%d", Permutations[nIndexPermutations + j]);
     }
     printf("\n");
     nIndexPermutations += setSizeBytes;
 }
}

void WritePermutations(LPBYTE Permutations, UINT64 countPermutations, BYTE setSize)
{
 char outstr[64], numstr[16];
 LPBYTE Elements;
 UINT64 i, index;
 FILE *fp;
 BYTE j;

 _itoa(setSize, numstr, 10);
 strcpy(outstr, numstr);
 strcat(outstr, "DigitSetPermutations.txt");
 fp = fopen(outstr, "wt");
 if(fp == NULL)return;

 Elements = new BYTE [setSize+2];
 for(i = 0; i < countPermutations; i++)
 {
	 index = i * setSize;
     for(j = 0; j < setSize; j++)
     {
         Elements[j] = Permutations[index+j] + '0';
     }
     Elements[j] = '\0';
     strcat((char *)Elements, "\n");
     fputs((char *)Elements, fp);
 }
 fclose(fp);
 delete [] Elements;
}

void ShowDiffs(LPBYTE Permutations, UINT64 nCountPermutations, BYTE setSizeBytes)
{
 char numstr[16];
 unsigned diff;
 UINT64 nIndexPermutations = setSizeBytes;
 for(UINT64 i = 1; i < nCountPermutations; i++)
 {
     diff = SubtractArrays(&Permutations[nIndexPermutations], &Permutations[nIndexPermutations-setSizeBytes], setSizeBytes);
     _itoa(diff, numstr, 10);
     printf(numstr);
     printf("\n");
     nIndexPermutations += setSizeBytes;
 }
}

int main(int argc, char* argv[])
{
 LPBYTE Permutations = NULL;
 UINT64 maxPermutations;
 BYTE setSize;
 bool bBadInput = false;

 if(argc < 2)
 {  
    bBadInput = true;
    goto ERR_OUT;
 }

 printf("Set size: %s\n", argv[1]);
 setSize = atoi(argv[1]);
 if((setSize < MIN_ELEMENTS) ||  (setSize > MAX_ELEMENTS))
 {  
    bBadInput = true;
    goto ERR_OUT;
 }

 maxPermutations = Factorial(setSize);
 Permutations = new BYTE [(unsigned)maxPermutations * setSize];
 ZeroMemory(Permutations, ((unsigned)maxPermutations * setSize));

 BYTE tmp, Elements[MAX_ELEMENTS];

 // Generate the elements in ascending order
 for(tmp = 0; tmp < setSize; tmp++)
 {
     SpareSet[tmp] =  Elements[tmp] = tmp;
     printf("%d ", Elements[tmp]);
 }
 printf("\n");
 
 memcpy(&Permutations[0], Elements, setSize);
 indexPermutations = setSize;
 recurseTree(Permutations, setSize, setSize);

 // ShowPermutations(Permutations, maxPermutations, setSize);
 // WritePermutations(Permutations, maxPermutations, setSize);
 // ShowDiffs(Permutations, maxPermutations, setSize);

 // Show last permuatation
 for(tmp = 0; tmp < setSize; tmp++)
 {
     printf("%d ", SpareSet[tmp]);
 }
 printf("\n");

 printf("\nCount permutations expected: %I64d\n", maxPermutations);
 printf("\nCount generated: %I64d\n", indexPermutations / setSize);

ERR_OUT:
 if(bBadInput)
 {
    printf("Usage: Supply number digits in set to permutate %d thru %d as command line arugument\n", MIN_ELEMENTS, MAX_ELEMENTS);
 }
 if(Permutations != NULL)
    delete [] Permutations;
 printf("\nAny key exits\n");
 while(!_kbhit());
 return 0;
}