4

我有一段时间无法应对的有趣问题。我们有 N 个字母和 N 对应于它们的信封，这意味着所有的字母和信封都被寻址（具有相同的排列）。任务是找出没有固定点的字母的可能排列数量 - 每个字母都在与该字母不同的信封中。当字母（和信封）通过一些 N 排列来处理时，问题就很容易了。然后我们所要做的就是找到 N 错位的数量（http://en.wikipedia.org/wiki/Derangement）。

但总的来说，这个问题可能更有趣。我们得到数字 N 和 N 数字 - 第 i 个数字表示第 i 个字母（和信封）的地址。第一个数字是 0（所以我们有编号为 [0,...,N-1] 的字母和信封）。那么我们有多少精神错乱呢？例如，我们给出：

 5 
 1 1 2 2 3

那么答案是 4，因为我们只有 4 种情况，每个字母都在不对应的信封中，它们是：

2 2 1 3 1
2 2 3 1 1 
2 3 1 1 2
3 2 1 1 2

（所以我们不区分地址相同的字母）。

为了：

6
0 0 0 1 1 1

答案是 1。因为：1 1 1 0 0 0 是唯一的方法。

我差点忘了.. 1<=N<=15 就足够了。

我想知道是否有任何方法可以快速计算它以及如何做到这一点。

我应该如何使用算法？

4

2 回答 2

2

第一次尝试，将其视为一个简单的动态规划问题。

所以你从左到右工作，对于信封列表中的每个位置，对于你可以留下的每组可能的字母，找出你可以到达那个点的方法的数量。前进很容易，你只需要一组，你知道有多少种方法可以到达那里，然后对于你可以放入下一个信封的每封信，你将结果集的总和乘以有多少种方法达到这一点。当您到达信封列表的末尾时，您会发现剩下 0 个字母的方法有多少，这就是您的答案。

对于您的第二个示例，可能会按以下方式进行：

Step 0: next envelope 1
  {1: 2, 2: 2, 3: 1}: 1
    -> {1: 2, 2: 1, 3: 1}
    -> {1: 2, 2: 2}

Step 1: next envelope 1
  {1: 2, 2: 1, 3: 1}: 1
    -> {1: 2, 2: 1}
    -> {1: 2, 3: 1}
  {1: 2, 2: 2}: 1
    -> {1: 2, 2: 1}

Step 2: next envelope 2
  {1: 2, 2: 1}: 2
    -> {1: 1, 2: 1}
  {1: 2, 3: 1}: 1
    -> {1: 1, 3: 1}
    -> {1: 2}

Step 3: next envelope 2
  {1: 1, 2: 1}: 2
    -> {2: 1}
  {1: 1, 3: 1}: 1
    -> {1: 1}
    -> {3: 1}
  {1: 2}: 1
    -> {1: 1}

Step 4: next envelope 3
  {2: 1}: 2
    -> {}
  {1: 1}: 2
    -> {}
  {3: 1}: 1
    // Dead end.

Step 5:
  {}: 4

这有效，并将让您了解您要求的计算范围。在 15 时，您有 2^15 = 32768 个可能的子集来跟踪哪些是非常可行的。不过，大约 20 岁时，您将开始耗尽内存。

我们可以改进吗？答案是我们可以。我们的大部分精力都花在了记住，比如说，到目前为止，我们是否使用了标记为 8 的信封，还是使用了标记为 9 的信封。但我们不在乎这个。决定有多少种完成方式的不是我们使用的是信封 8 还是 9。而是图案。有多少个标签有 x 个信封和 y 个字母。不是哪个标签是哪个，只是有多少。

因此，如果我们只跟踪该信息，在每一步我们都可以抓取一个带有标签的信封，其中包含最多的信封，如果有平局，我们将选择剩下的字母最少的信封（如果还有领带，我们真的不在乎我们得到哪一个）。像以前一样进行计算，但中间状态要少得多。（我们不会像您那样将信封排成一行。但是对带有信封的最后一封信进行稳定的排序，您将获得上面的列表。）

让我们使用符号[x y]: z来表示留下带有信封和字母的z标签。我们有一个这样的标签列表然后你的例子可以表示为。对于过渡，我们将采用其中一个标签，并使用另一个标签的字母（给我们一个过渡到），或者我们将采用其中一个标签，并使用标签中的字母（给我们一个过渡到)。xy1 1 2 2 3{[2 2]: 2, [1 1]: 1}[2 2]{[2 1]: 1, [1 2]: 1, [1 1]: 1}[2 2][1 1]{[2 2]: 1, [1 2]: 1, [1 0]: 1}

让我们进行计算。我将列出状态、到达那里的方式以及您所做的转换：

Step 1:
  {[2 2]: 2, [1 1]: 1}: 1
    -> 1 * {[2 1]: 1, [1 2]: 1, [1 1]: 1}
    -> 1 * {[2 2]: 1, [1 2]: 1, [1 0]: 1}

Step 2:
  {[2 1]: 1, [1 2]: 1, [1 1]: 1}: 1
    -> 1 * {[1 1]: 3}
    -> 1 * {[1 1]: 1, [1 2]: 1, [1 0]: 1}
  {[2 2]: 1, [1 2]: 1, [1 0]: 1}: 1
    -> 1 * {[1 2]: 1, [1 1]: 1, [1 0]: 1}

Step 3:
  {[1 1]: 3}: 1
       // This is 2x because once the label is chosen, there are 2 letters to use.
    -> 2 * {[0 1]: 1, [1 0]: 1, [1 1]: 1}
  {[1 1]: 1, [1 2]: 1, [1 0]: 1}: 2
    -> 1 * {[1 0]: 1, [1 2]: 1, [0 0]: 1}
    -> 1 * {[1 1]: 2, [0 0]: 1}
  {[1 2]: 1, [1 1]: 1, [1 0]: 1}: 1
    -> 1 * {[1 1]: 2, [0 0]: 1}
    -> 1 * {[1 2]: 1, [1 0]: 1, [0 0]: 1}

Step 4:
  {[0 1]: 1, [1 0]: 1, [1 1]: 1}: 2
    -> 1 * {[1 1]: 1, [0 0]: 2}
    -> 1 * {[1 0]: 1, [0 1]: 1, [0 0]: 1}
  {[1 0]: 1, [1 2]: 1, [0 0]: 1}: 2
    -> 1 * {[1 1]: 1, [0 0]: 2}
  {[1 1]: 2, [0 0]: 1}: 2
    -> 1 * {[1 0]: 1, [0 1]: 1, [0 0]: 1}

Step 5:
  {[1 1]: 1, [0 0]: 2}: 4
    // dead end
  {[1 0]: 1, [0 1]: 1, [0 0]: 1}: 4
    -> 1 * {[0 0]: 3}

所以答案是4。

这似乎是一项疯狂的工作——远远超过枚举。它是！

但是它可以扩展。用 100 封信和信封试一试，它应该运行得很快。

于 2012-06-29T21:43:48.130 回答
0

15 个“正常”排列将需要 1.3*10^9 次暴力尝试，但通过使用相同的键，我们剩下的排列要少得多。

让我们用你的例子：5张卡片，1 1 2 2 3

设置一个排列数组

5 4 3 2 1

并准备通过像数字一样从右到左递减来遍历它。忽略所有不是排列的组合。

5 4 3 2 1 忽略

5 4 3 2 0 忽略

5 4 3 1 5 忽略

...

5 4 3 1 2 好

有争议的是，这可以通过更好的排列算法得到极大的改进，但这并不容易，我必须考虑一下。

下一步是生成您的比较。排列数组选择一个排列：

5 4 3 1 2 表示 3 2 2 1 1

这将测试你的精神错乱。可以大大加快比较速度的一件事是您可以跳过无效的组合。

如果开头的 5 选择了错误的项目，您可以跳过所有 5 个 XXXX 排列并继续 4 5 3 2 1。

每次你发现一个错乱，增加一个计数器。完毕。

于 2012-06-29T20:22:51.943 回答