// PermuteBits.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 and a minimum bit width appropriate to contain each digit.
// For example, an 8 digit set will consist of the numbers (0,1,2,3,4,5,6,7)
// and will require a minimum of 3 bits to contain the biggest number of that
// set, 7, but you can give it more bits per digit if you want, to demonstrate
// that the algorithm works with any bit width, and therefore any number base.

// All permutations of the desired set will be generated using the algorithm discussed
// in "A Permutation on Combinatorial Algorithms" in a bit-packed 64 bit integer.
// Each permutation will be verified against an array based 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
#define MIN_BITWIDTH 3
#define MAX_BITWIDTH 8


UINT64 indexPermutations;
BYTE SpareSet[MAX_ELEMENTS];

// Generates the next permutation 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[nIndexPermutations]
// before nIndexPermutations is advanced, to stay in sync.
bool ValidatePermutation(UINT64 permutation, BYTE setSize, BYTE bitWidth)
{
 UINT64 mask;
 UINT64 shift;

 GeneratePermutation(SpareSet, setSize);
 mask = 1 << bitWidth;
 mask -= 1;
 for(BYTE tmp = 0; tmp < setSize; tmp++)
 {
     shift = ((setSize - 1) - tmp) * bitWidth;
     if((BYTE)((permutation >> shift) & mask) != SpareSet[tmp])
     {
        printf("Error: Permuation is invalid!\n");
        return false; // <-- debug breakpoint
     }
 }
 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;
}


// Writes 'count' permutations to global Permutations at 'indexPermutations'
void GeneratePermutations(UINT64 *Permutations, UINT64 count, BYTE setSize, BYTE bitWidth)
{
 UINT64 p, mask, maskBase;
 UINT64 shiftA, shiftB;

 maskBase = 1 << bitWidth;
 maskBase -= 1;
 for(UINT64 i = 0; i < count; i++)
 {
     // Index is pointing at the next location.
     // Copy previous permutation to next location and permutate in place...
     p = Permutations[indexPermutations-1];

     // Find the largest index k such that a[k] < a[k + 1].
     mask = maskBase;
     short k, l, largestIndex = -1;
     for(k = (setSize - 2); k >= 0; k--)
     {
         // if(pTable[k] < pTable[k+1])
         shiftA = ((setSize - 1) - k) * bitWidth;
         shiftB = ((setSize - 1) - (k+1)) * bitWidth;
         if( ((p >> shiftA) & mask) < ((p >> shiftB) & mask) )
         {
            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;
     shiftA = ((setSize - 1) - k) * bitWidth;
     for(l = (setSize - 1); l >= 0; l--)
     {
         // if(a[k] < a[l])
         shiftB = ((setSize - 1) - l) * bitWidth;
         if( ((p >> shiftA) & mask) < ((p >> shiftB) & mask) )
         {
            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 = a[k];
     shiftA = ((setSize - 1) - k) * bitWidth;
     shiftB = ((setSize - 1) - l) * bitWidth;
     UINT64 tmpA = ((p >> shiftA) & mask);
     UINT64 tmpB = ((p >> shiftB) & mask);
     // a[k] = a[l];
     mask <<= shiftA;
     p |= mask;
     p ^= mask;
     p |= (tmpB << shiftA);
     // a[l] = tmp;
     mask = maskBase;
     mask <<= shiftB;
     p |= mask;
     p ^= mask;
     p |= (tmpA << shiftB);
     // Reverse the sequence from a[k + 1] up to and including the final element a[n].
     ++k; l = setSize - 1;
     while(l > k)
     {
           shiftA = ((setSize - 1) - k) * bitWidth;
           shiftB = ((setSize - 1) - l) * bitWidth;
           // tmp = a[k];
           mask = maskBase;
           tmpA = ((p >> shiftA) & mask);
           tmpB = ((p >> shiftB) & mask);
           // a[k] = a[l];
           mask <<= shiftA;
           p |= mask;
           p ^= mask;
           p |= (tmpB << shiftA);
           // a[l] = tmp;
           mask = maskBase;
           mask <<= shiftB;
           p |= mask;
           p ^= mask;
           p |= (tmpA << shiftB);
           ++k; --l;
     }
     Permutations[indexPermutations] = p;
     if(!ValidatePermutation(p, setSize, bitWidth))
     {
        break;
     }	 
     ++indexPermutations;
 }
}

void addDifferences(UINT64 *Permutations, UINT64 count, UINT64 offset, BYTE setSize, BYTE bitWidth)
{
 for(UINT64 n = 0; n < count; n++)
 {
     Permutations[indexPermutations] = Permutations[indexPermutations - 1];
     Permutations[indexPermutations] += (Permutations[offset] - Permutations[offset - 1]);
     if(!ValidatePermutation(Permutations[indexPermutations], setSize, bitWidth))
     {
        break;
     }	 
     --offset;
     ++indexPermutations;
 }
}

// Generate all permutations of the set of size 'setSize'
// each packed into 'bitWidth' bits...
void recurseTree(UINT64 *Permutations, BYTE digits, BYTE setSize, BYTE bitWidth)
{
 if(digits > 3)
 {
    recurseTree(Permutations, digits-1, setSize, bitWidth);
 }

 // 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, setSize, bitWidth);
 
 // 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 - 2;
 count = Factorial(digits)/2-1;
 addDifferences(Permutations, count, offset, setSize, bitWidth);
 // ('indexPermutations' was incremented by addDifferences())

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

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


void ShowPermutations(UINT64 *Permutations, UINT64 nCountPermutations, BYTE setSize, BYTE bitWidth)
{
 UINT64 mask;
 mask = 1 << bitWidth;
 mask -= 1;
 for(UINT64 i = 0; i < nCountPermutations; i++)
 {
     for(BYTE j = 0; j < setSize; j++)
     {
         UINT64 shift = ((setSize - 1) - j) * bitWidth;
         printf("%d", (BYTE)((Permutations[i] >> shift) & mask));
     }
     printf("\n");
 }
}

void WritePermutations(UINT64 *Permutations, UINT64 countPermutations, BYTE setSize, BYTE bitWidth)
{
 char outstr[64], numstr[16];
 LPBYTE Elements;
 UINT64 i, shift, mask;
 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];
 mask = 1 << bitWidth;
 mask -= 1;
 for(i = 0; i < countPermutations; i++)
 {
     for(j = 0; j < setSize; j++)
     {
         shift = ((setSize - 1) - j) * bitWidth;
         Elements[j] = (BYTE)((Permutations[i] >> shift) & mask) + '0';
     }
     Elements[j] = '\0';
     strcat((char *)Elements, "\n");
     fputs((char *)Elements, fp);
 }
 fclose(fp);
 delete [] Elements;
}

void ShowDiffs(UINT64 *Permutations, UINT64 nCountPermutations)
{
 char numstr[64];
 UINT64 diff;
 for(UINT64 i = 1; i < nCountPermutations; i++)
 {
     diff = (Permutations[i] - Permutations[i-1]);
     _i64toa(diff, numstr, 10);
     printf(numstr);
     printf("\n");
 }
}

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

 if(argc < 3)
 {  
    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;
 }
 printf("Bit width: %s\n", argv[2]);
 bitWidth = atoi(argv[2]);
 if((bitWidth < MIN_BITWIDTH) ||  (bitWidth > MAX_BITWIDTH))
 {  
    bBadInput = true;
    goto ERR_OUT;
 }

 if((setSize * bitWidth) > 64)
 {  
    bBadInput = true;
    goto ERR_OUT;
 }

 maxPermutations = Factorial(setSize);
 Permutations = new UINT64 [(unsigned)maxPermutations];
 ZeroMemory(Permutations, sizeof((unsigned)maxPermutations));

 BYTE tmp;
 UINT64 val, shift;

 // Generate the elements in ascending order
 val = permutation = 0;
 for(tmp = 0; tmp < setSize; tmp++)
 {
     shift = ((setSize - 1) - tmp) * bitWidth;
     permutation |= (val << shift);
     SpareSet[tmp] = tmp;
     ++val;
     printf("%d ", SpareSet[tmp]);
 }
 printf("\n\n");
 
 Permutations[0] = permutation;
 indexPermutations = 1;

 recurseTree(Permutations, setSize, setSize, bitWidth);

 // ShowPermutations(Permutations, indexPermutations, setSize, bitWidth);
 // WritePermutations(Permutations, indexPermutations, setSize, bitWidth);
 // ShowDiffs(Permutations, indexPermutations);

 // 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);

ERR_OUT:
 if(bBadInput)
 {
    printf("Usage: Supply number digits in set to permutate: %d thru %d,\n", MIN_ELEMENTS, MAX_ELEMENTS);
    printf("followed by a space, then desired bitwidth of digits: %d thru %d\n", MIN_BITWIDTH, MAX_BITWIDTH);
 }
 if(Permutations != NULL)
    delete [] Permutations;
 printf("\nAny key exits\n");
 while(!_kbhit());
 return 0;
}