0

我用 C 编写了一个基本的排列程序。用户输入一个数字，它会打印出该数字的所有排列。

基本上，这就是它的工作原理（主要算法是用于找到下一个更高排列的算法）：

int currentPerm = toAscending(num);
int lastPerm = toDescending(num);
int counter = 1;

printf("%d", currentPerm);

while (currentPerm != lastPerm)
{
   counter++;
   currentPerm = nextHigherPerm(currentPerm);
   printf("%d", currentPerm);
}

但是，当输入的数字包含重复的数字（重复）时，不会生成一些排列，因为它们是重复的。计数器显示的数字与预期的不同 - 它没有显示数字中位数的阶乘，而是显示了一个较小的数字，只有唯一的排列。

例如：

num = 1234567
counter = 5040 (!7 - all unique)

num = 1123456
counter = 2520

num = 1112345
counter = 840

我希望它把重复/重复的数字视为不同的数字——我不想只生成唯一的排列——而是生成所有的排列，不管它们是否重复和重复。

4

4 回答 4

1

嗯...为什么不直接计算输入字符串长度的阶乘呢？;)

于 2012-11-12T20:52:07.877 回答
1

当您有 3 个字母（例如 ABC）时，您可以制作：ABC, ACB, BAC, BCA, CAB, CBA、6 种组合（6！）。如果其中 2 个字母像 AAB 一样重复，您可以做出：AAB、ABA、BAA，它不是 3！那是什么？它来自哪里？重复数字或字母时计算它的真正方法是使用组合->( n k ) = n! / ( n! * ( n! - k! ) )

我们再做一个说明性的例子：AAAB，那么可能的组合AAAB, AABA, ABAA, BAAA只有四种组合，如果你用公式计算它们4C3 = 4.

生成所有这些列表的正确程序如何：

  • 将数字存储在数组中。例子ABCD。
  • 将数组的 0 元素设置为枢轴元素，并将其从临时数组中排除。A {BCD}
  • 然后，当您想要所有组合（即使是重复的）时，将时间数组的元素向右或向左移动（随您的喜好），直到到达第 n 个元素。

A{BCD}------------A{CDB}------------A{DBC}

  • 再次执行第二步，但使用临时数组。

A{B{CD}}------------A{C{DB}}------------A{D{BC}}

  • 再次执行第三步，但在第二个临时数组内。

A{B{CD}}------------A{C{DB}}------------A{D{BC}}

A{B{DC}}------------A{C{BD}}------------A{D{CB}}

  • 转到第一个数组并移动数组，BCDA，将 B 设置为枢轴，然后执行此操作，直到找到所有组合。
于 2012-11-12T21:56:15.073 回答
1

我希望它将重复/重复的数字视为不同的数字 - 我不想只计算唯一排列的数量。

如果唯一nextHigherPerm()使用的信息是传入的数字，那么您就不走运了。考虑nextHigherPerm(122)。该函数如何知道122它已经看到了多少个版本？应该nextHigherPerm(122)返回122还是212？除非您单独跟踪生成器的当前状态，否则无法知道。

于 2012-11-12T21:03:38.597 回答
0

为什么不将其转换为字符串，然后将您的程序视为一个字谜生成器呢？

于 2012-11-12T21:08:25.670 回答