如何制作一个能够高效输出的排列组合

Question

这是一个面试题，我没能回答出来，但仍然想知道如何解决。

你有一个由N个人组成的大家庭，分别为1岁、2岁、3岁、...、N岁。 你想拍下一张你们大家庭的照片。所有家庭成员都要排在同一排中。

“我是家庭的朋友，建议安排家庭成员如下：”

1. 1岁的家庭成员坐在行的左端。 2. 每两个相邻的家庭成员之间的年龄差不能超过2岁。

输入：整数N，1 ≤ N ≤ 55。

输出：摄影师可以拍摄的可能照片数量。

例子-> 输入：4，输出：4

与条件匹配的数组：

[1,2,3,4][1,2,4,3][1,3,2,4][1,3,4,2]

另一个例子：

输入：5，输出：6

与条件匹配的数组：

[1,2,3,4,5][1,2,3,5,4][1,2,4,3,5][1,2,4,5,3][1,3,2,4,5][1,3,5,4,2]

我用Ruby解决了这个问题，因为它是我选择的工具。首先生成每个排列，然后通过检查条件#1来过滤它们，确保数组的第一个条目等于1，这很快。其次，从左到右遍历每个数组，并确保每对之间的绝对值差不超过2，这很慢。

当N > 9时，我的实现会变得非常缓慢，因为它要排序300k个排列。从那里开始，所需的时间是二次的（我认为，还在弄清楚）。

我应该如何改善这种情况？我这里并不是在寻找代码示例，更多的是想法，哪种算法应该用于有效地对排列进行排序？我应该编写自己的排列吗（可能是的）。

沿着这些思路，我复制了QuickPerm的这个版本 https://dev59.com/jnE95IYBdhLWcg3wPrkI#2390969

在results << yield(a)周围添加了一个条件，只选择以1开头的数组，但我不确定如何最好地实现之前提到的其余条件。

编辑

这是令人非常失望的解决方案。

我真的想找出如何生成排列，而不是表示可能正确排列数量的整数。

def number_of_possible_perms(n_persons)
  array = []
  array[0] = 0
  array[1] = array[2] = 1
  for i in 3..n_persons
    array[i] = array[i-1] + array[i-3] + 1
  end
  return array[n_persons]
end

- James

---

尝试在这里应用动态规划。从左边开始。每个阶段可能的组合不能太多。例如，如果前两个条目是1,3，则下一个条目只能是2或4，不能是5或更多。 - Abhishek Bansal

我不认为这是一个动态规划（DP）问题。DP是一种寻找最优解的技术，给定一个目标。当存在多个最优解时（例如，如果所有满足排列要求的解都具有值“1”，而其他解都具有值“0”，在“状态变量”的适当定义下），DP可以用于找到一个可行的排列，但不能找到所有排列。动态规划使用递归，而递归可能在这里是合适的，但这并不意味着DP是合适的。 - Cary Swoveland

@CarySwoveland 我认为你可能混淆了定义。DP 不仅仅是一种优化技术 - 它通常用于描述解决某些递归问题的“自底向上”方法。根据 Jared 的答案，看起来这正是那种 DP 的完美问题类型。 - Max

@user1990169，我曾经教授过一些优化技巧的课程，其中包括动态规划。你的评论让我想知道术语是否已经发生了变化。例如，根据这个和这个，我认为还没有变化。 - Cary Swoveland

据我所知，动态规划是一种解决问题的通用技术，其中问题可以分解为更简单的子问题，并通过解决这些子问题，我们可以以高效的方式得到原始问题的解决方案。我不知道这是否仅适用于优化问题。但是，我将撤回“动态规划”一词，并将其替换为“类似于动态规划优化技术的技术”。 - Abhishek Bansal

Answer 1

如果我们列出可能发生的过渡情况，那么就可以更清楚地弄清楚如何解决这个问题：

  2   6---8
 /|\ /|\ /|\
1 | 4 | 7 | 10...etc
 \|/ \|/ \|/
  3---5   9

让我们考虑一个起点为1，触及每个数字一次的路径总数为C_n，其中n为节点数。让我们考虑一些可能的情况：

- C_1 = 1 - C_2 = 1 - C_3 = 2

现在假设n>3。让我们考虑一些可能的序列：

1、2、... 我们知道如果从这个方向开始，我们可以通过删除1并将2设置为起点来重新排列图形，这与从1到n-1的图形相同。因此，以1、2开头的序列有C_(n-1)种。

1、3、2、... 我们也可以采用相同的方法，因为下一步必须是4。将图表重新排列以从4开始，我们有C_(n-3)个以1、3、2开头的序列。

1、3、4、... 我们有两种可能性：要么我们只有4个节点和1个序列(1,3,4,2)，要么我们有多于4个节点和0个序列。

1、3、5、... 我们再次有两个可能性：要么我们只有4个节点和0个序列，要么我们有多于4个节点和1个序列(一旦你上升了2个节点(在3之后)，你必须继续上升2个节点直到到达终点，然后下降2个节点)。

因此，我们现在有C_n = C_(n-1) + C_(n-3) + 1。

- Jared Windover-Kroes

---

有人能提供一个简单的代码示例来实现这个吗？任何编程语言都可以。 - James

@JamesGibsonWeber 给你，用 Ruby 编写：c = [1, 1, 2]; i = 2; c[i += 1] = c[i - 1] + c[i - 3] + 1 while i < N-1，其中 N 是人数。 - Max

Haskell：let cs = [1,1,2] ++ (map (+1) $ zipWith (+) cs (drop 2 cs)) @JamesGibsonWeber - Philipp Claßen

Answer 2

我会按照以下方式实现。

术语

• N：人数
• A(n,i)：对于前n个家庭成员，满足顺序要求（“可行排列”）的所有排列集合，使得年龄为i的人最后，2 <= i <= n。

目标

确定对于所有i=2..N，取A(N,i)的并集。

算法

n = 2

只有一种方式可以把人员1和2排序：

A(2,2) = { [1,2] }

n = 3

并且有两种方式来排序前三个：

A(3,2) = { [1,3,2] }
A(3,3) = { [1,2,3] }

n = 4

当我们考虑前四个时，我们开始得到一些更有趣的东西。最初，忽略相邻成员年龄差不超过两岁的要求。

A(4,2) = { [1,4,3,2], [1,3,4,2] }
A(4,3) = { [1,4,2,3], [1,2,4,3] }
A(4,4) = { [1,3,2,4], [1,2,3,4] }

请注意这些集合是如何确定的。考虑 A(4,2)。我们取 A(3,2) 中的单个排列，并将 4 插入到两个可能的位置中的每一个。

接下来，我们删除所有不满足相邻年龄差要求的组合，最终得到以下结果：

A(4,2) = { [1,3,4,2] }
A(4,3) = { [1,2,4,3] }
A(4,4) = { [1,3,2,4], [1,2,3,4] }

n=5

再次，首先计算n=5的集合，不考虑相邻年龄要求：

A(5,2) = { [1,5,3,4,2], [1,3,5,4,2], [1,3,4,5,2] }
A(5,3) = { [1,5,2,4,3], [1,2,5,4,3], [1,2,4,5,3] }
A(5,4) = { [1,5,3,2,4], [1,3,5,2,4], [1,3,2,5,4], 
           [1,5,2,3,4], [1,2,5,3,4], [1,2,3,5,4] }
A(5,5) = { [1,3,4,2,5], [1,2,4,3,5], [1,3,2,4,5], [1,2,3,4,5 }

请注意，这些集合是通过组合生成的，包括 A(4,2)、A(4,3)、A(4,4) 和 A(5,2)。例如，要计算 A(5,2)，对于 A(4,2) 中的每个排列（只有一个），我们在第一个和最后一个位置之间插入 5。

现在删除所有不可行的排列，留下以下内容：

A(5,2) = { [1,3,5,4,2], [1,3,4,5,2] }
A(5,3) = { }
A(5,4) = { [1,3,5,2,4], [1,2,3,5,4] }
A(5,5) = { [1,2,4,3,5], [1,3,2,4,5], [1,2,3,4,5 }

继续这种方式，直到计算出所有i=2,...N的A(N,i)。

如果N => 5，可行的排列将是以下四个集合的并集：

{ [1,3,5,4,2], [1,3,4,5,2], [1,3,5,2,4], [1,2,3,5,4],
  [1,2,4,3,5], [1,3,2,4,5], [1,2,3,4,5 }

我预计可以应用额外的逻辑来加速计算，通过一次性消除一组排列。

- Cary Swoveland

Answer 3

我不确定是否存在针对此问题的优化算法，但我想到的一种暴力方法是回溯算法。

它比迭代所有可能的预计算排列更有效，因为如果找到第一个不匹配的对，它可以立即停止。因此，它可以修剪搜索空间的大部分（换句话说，它不必查看所有N！排列）。

- Philipp Claßen

Answer 4

创建一个名为f的方法，该方法接受N并返回可能数组的数组。在此过程中，请使用递归。当N= 1时，您知道可能性只有[1]，因此输出应为[[1]]。否则，请计算f(N-1)。要从中获取f(N)，请考虑可以将N插入到f(N-1)中每个数组中的哪些位置。

- sawa

---

我相信你应该找到 f(N) = f(N-1) + f(N-3) + 1（其中f(n)是n个人可能排序的数量）。 - Peter de Rivaz