0
  • 平台：首选多平台，但我现在正在寻找任何东西。
  • 语言：C 是首选，但我应该能够翻译其他语言。

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

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

1 回答 1

2

没有固定点的排列称为紊乱。以下 C 代码使用来自 Wikipedia 链接的交替求和公式。

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

您可以将整数换成 bignums 或 doubles。在后一种情况下，您应该得到一个准确无误的答案。如果答案不适合双偶数，则 ln(n!/e) = ln(1) + ln(2) + ... + ln(n) - 1 = lgamma(n + 1.0) - 1.0if you have lgammaavailable in<math.h>是一个很好的近似值紊乱数的自然对数。

于 2013-07-17T00:58:01.643 回答