CODEWITHSUNDEEP
calgorithmpermutation
John Vulconshinz
John Vulconshinz

Reputation: 1148

Calculating Completely Substituted Cypher Permutations

I am writing a program that cyphers plaintext using a substitution cypher. I am trying to calcuate the total number of, for lack of a better term "cypher" permutations. What I mean is, I want to calculate all the possible permutations that do not substitute the plaintext as itself. Meaning 00000000(NULL) cannot be substituted as 00000000(NULL). I know I can generate all the possible permutations of a block of n size in the following way.

n(size) = 3 (1, 2, 3 are the unique values being permutated)

The problem is, only 231 and 312 do not substitute plaintext as itself. I could use conditional statments to determine if a permutation is valid but I would prefer a way that calculates only the valid permutations. I am hoping that there is already a simple way to do this but I do not know how to word the question in order to google it. So to sum up my question, I need an efficient way to calculate all the possible cypher permutations that do not leave plaintext unsubstituted.

The following code will generate all possible permutations for n number of unique values. But it will only work when n! is representable using a normal integer data type.

#include <stdlib.h>
#include <stdio.h>

int main()
{
int current_perm = 0;
int num_perms = 1;
int cypher_size = 0;
int buffer = 0;

int *cypher = NULL;

printf("Input the number of unique values in the cypher(The cypher's size) : ");
scanf("%i", &cypher_size);

if((cypher = malloc(sizeof(int)*(cypher_size+1))) == NULL)
{
    perror("ERROR: Failed to allocate memory for the cypher ");
    return 1;
}

int i = cypher_size;
int j = 0;

while(i > 0)
{
    cypher[i-1] = i;
    num_perms *= i;
    i--;
}

for(j = 0; j < cypher_size; j++) {printf("%i ", cypher[j]);}
printf("\n");

for(current_perm = 1; current_perm < num_perms;)
{
    for(i = 0; i < cypher_size-1; i++, current_perm++)
    {
        buffer = cypher[i+1];
        cypher[i+1] = cypher[i];
        cypher[i] = buffer;

        for(j = 0; j < cypher_size; j++) {printf("%i ", cypher[j]);}
        printf("\n");
    }
}
}

Upvotes: 0

Views: 102

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65498

Permutations with no fixed points are called derangements. The following C code uses the alternating sum formula from the Wikipedia link.

static int nder(int n) {
    int m = 1;
    int f = 1;
    for (int k = n; k > 0; k--) {
        f *= k;
        m = f - m;
    }
    return m;
}

You can swap out ints for bignums or doubles. In the latter case, you should get an answer that's within a couple ulp of being accurate. If the answer won't fit in a double even, ln(n!/e) = ln(1) + ln(2) + ... + ln(n) - 1 = lgamma(n + 1.0) - 1.0 if you have lgamma available in <math.h> is an excellent approximation of the natural log of the number of derangements.

Upvotes: 2

Related Questions