/*===================================================================*/
/* C program for distribution from the Combinatorial Object Server.  */
/* Generate permutations by transposing adjacent elements            */
/* via the Steinhaus-Johnson-Trotter algorithm.  This is             */
/* the same version used in the book "Combinatorial Generation."     */
/* Both the permutation (in one-line notation) and the positions     */
/* being transposed (as a 2-cycle) are output.                       */
/* The program can be modified, translated to other languages, etc., */
/* so long as proper acknowledgement is given (author and source).   */  
/* Programmer: Frank Ruskey, 1995.                                   */
/* The latest version of this program may be found at the site       */
/* http://sue.uvic.ca/~cos/inf/perm/PermInfo.html                    */
/*===================================================================*/

/*
 * Original code for this was borrowed from the above.  It has been
 * modified and simplified to work with the rest of the code
 * in the cipher software package.
 *
 * Modified by wart@ugcs.caltech.edu for use with the cipher
 * software.
 */

#include<stdio.h>

#define BASE 12
#define BASELEN 10
#define DUMP_INTERVAL 100000

typedef struct PermInfo {
    int length;
    int dir[BASE];
    int p[BASE];
    int pi[BASE];
    unsigned long long BaseArr[BASELEN];
    char *key;
    int ikey[26];
    unsigned long long count;
} PermInfo;

PermInfo pInfo;

long long
S(char *string)
{
    unsigned long long val=0;
    int c, letval, i;

    for(i=0; i < strlen(string); i++) {
	c = string[i] - 'a';

	if (pInfo.ikey[c] == -1) {
	    fprintf(stderr, "Invalid character in string:  %c\n", c+'a');
	    abort();
	}

	letval = pInfo.p[pInfo.ikey[c]];

	val += letval * pInfo.BaseArr[strlen(string) - i - 1];
    }

    return val;
}

long long
C(char c)
{
    if (pInfo.ikey[c-'a'] == -1) {
	fprintf(stderr, "Invalid character in string:  %c\n", c);
	abort();
    }

    return (long long)(pInfo.p[pInfo.ikey[c-'a']]);
}

#define CHARACTERS "provesunaimd";

int
resultValid()
{
//    if (C('p') != 1) return 0;
    if (!C('p')) return 0;
    if (!C('s')) return 0;
    if (!C('u')) return 0;
    if (!C('i')) return 0;

    if (S("prove") * S("sun") == S("ipiudsem")) {
    if (S("prove") * C('n') == S("uarirm")) {
	    return 1;
    }
    }

    return 0;
}

/*
 * Function called by PermCmd.  This does all of the work.
 */

int
doPerm (int n)
{
    int i, result;

    if (n >= pInfo.length) {
	int valid;
	pInfo.count++;
	valid = resultValid();
	/*
	if (valid || pInfo.count%DUMP_INTERVAL == 0) {
	*/
	if (valid) {
	    if (valid)
		printf("Solution  %10ld:  ", pInfo.count);
	    else
		printf("Iteration %10ld:  ", pInfo.count);

	    for(i=0; i < pInfo.length; i++) {
		printf("%3c", pInfo.key[pInfo.pi[i]]);
	    }
	    printf("\n                       ");
	    for(i=0; i < pInfo.length; i++) {
		printf("%3d", i);
	    }
	    printf("\n\n");
	}
    } else {
	result = doPerm(n+1);
	if (result)
	    return result;

	for (i=0; i<n; ++i) {
	    int z;
	    /*
	     * Move(n, dir[n]);
	     */
	    z = pInfo.p[pInfo.pi[n]+pInfo.dir[n]];
	    pInfo.p[pInfo.pi[n]] = z;
	    pInfo.p[pInfo.pi[n]+pInfo.dir[n]] = n;
	    pInfo.pi[z] = pInfo.pi[n];
	    pInfo.pi[n] = pInfo.pi[n] + pInfo.dir[n];

	    result = doPerm(n+1);
	    if (result)
		return result;
	}
	pInfo.dir[n] = -pInfo.dir[n];
    }

    return 0;
}

int
main(int argc, char **argv)
{
    char *key;
//    PermInfo pInfo;
    int i;

    pInfo.key = CHARACTERS;
    pInfo.count = 0;

    if (strlen(pInfo.key) != BASE) {
	fprintf(stderr, "Invalid key length:  %d.  Must be %d\n",
		strlen(pInfo.key), BASE);
	exit(1);
    }

    for(i=0; i < 26; i++)
	pInfo.ikey[i] = -1;

    pInfo.length = BASE;
    for(i=0; i < BASE; i++) {
	pInfo.p[i] = pInfo.pi[i] = i;
	pInfo.dir[i] = -1;

	pInfo.ikey[pInfo.key[i] - 'a'] = i;
    }

    pInfo.BaseArr[0] = 1;
    for(i=1; i < BASELEN; i++)
	pInfo.BaseArr[i] = BASE * pInfo.BaseArr[i-1];

    doPerm(0);
}