algorithm - 有限制的排列

Question

我遇到了一段时间以来无法解决的有趣问题。我们有 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 就够了

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

我应该如何处理算法？

Answer 1

第一次尝试，把它当作一个简单的动态规划问题。

所以你从左到右工作，对于信封列表中的每个位置，对于你可以留下的每组可能的字母，找出你可以到达那个点的方法的数量。向前移动很容易，你只需要一个集合，你知道有多少种方法可以到达那里，然后对于你可以放入下一个信封的每个字母，你将结果集的总和增加有多少种方法达到这一点。当您到达信封列表的末尾时，您会发现还有多少种方法可以让 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 标签，带有 x 信封和 y 剩下的字母。我们有一个这样的标签列表然后你的 1 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 个字母和信封，它应该运行得很快。