计算完全替代的密码排列

Question

• 平台:首选多平台，但目前我正在寻找任何平台。
• 语言:C 是首选，但我应该能够翻译其他语言。

我正在编写一个程序，使用替换密码来加密明文。由于缺少更好的术语“密码”排列，我正在尝试计算总数。我的意思是，我想计算所有不替代明文本身的可能排列。意思是 00000000(NULL) 不能替换为 00000000(NULL)。我知道我可以通过以下方式生成 n 大小的 block 的所有可能排列。

n(size) = 3(1、2、3 是被排列的唯一值)

• 123
• 213
• 231
• 321
• 312
• 132
• 123

问题是，只有 231 和 312 没有将明文替换为自身。我可以使用条件语句来确定排列是否有效，但我更喜欢一种只计算有效排列的方法。我希望已经有一种简单的方法可以做到这一点，但我不知道如何用谷歌来表达这个问题。因此，总结一下我的问题，我需要一种有效的方法来计算所有可能的密码排列，这些密码排列不会使明文未被替换。

以下代码将为 n 个唯一值生成所有可能的排列。但只有当 n!可以使用普通整数数据类型表示。

#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");
    }
}
}

Answer 1

没有固定点的排列称为 derangements .以下 C 代码使用维基百科链接中的交替求和公式。

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;
}

您可以将整数换成大数或 double 。在后一种情况下，您应该会得到一个准确度几 ulp 以内的答案。如果答案不符合双偶数，ln(n!/e) = ln(1) + ln(2) + ... + ln(n) - 1 = lgamma(n + 1.0) - 1.0如果你有 lgamma可用 <math.h>是紊乱次数自然对数的极好近似值。