这是一个面试问题，我没有回答出来，但我仍然很好奇如何解决。
你有一个N人的大家庭，1,2,3，…，分别为N岁。你想给你的大家庭拍张照片。你所有的家庭成员都将被安排在一排。
"我是这家人的朋友，建议安排家人如下:"
- 1岁的家庭成员坐在这一排的左端。
- 每两个家庭成员坐在一起的年龄差不能超过2岁。
输入:整数N, 1≤N≤55。
Output:摄影师可以拍摄的照片数量。
示例->输入: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时变得很慢。因为它正在对30万个排列进行排序。从这里开始，花费的时间是二次的(我相信，仍然在计算)。
我该如何着手改善这种状况?
我不是真的在这里寻找代码样本，更多的想法，应该使用哪种算法来有效地排序排列?我应该写我自己的排列吗(可能是的)。
沿着这些行，我复制了这个版本的QuickPerm https://stackoverflow.com/a/2390969/1265528
在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
如果我们绘制出可能的过渡，应该会更清楚如何弄清楚:
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的图是一样的。所以我们有C_(n-1)个序列，以1,2开头。
- 1、3、2,……我们可以在这里做同样的事情，因为下一步必须是4。重新排列图，从4开始，我们得到从1,3,2开始的C_(n-3)序列。
- 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。
我不确定是否存在针对此问题的优化算法，但我想到的一种蛮力方法是回溯。
它比遍历所有可能的预先计算的排列更有效，因为如果找到第一个不匹配的排列对，它可以立即停止。因此，它可以减少搜索空间的很大一部分(换句话说，它不必查看所有的N!排列)。
创建一个方法f，它接受N并返回一个可能的数组的数组。在这样做时，使用递归。当N = 1时，您知道可能性只有[1]，因此输出应该是[[1]]。否则，计算f(N - 1)。要从中获得f(N)，请考虑N可以插入到f(N - 1)的每个数组中的哪个位置。
我会这样做。
-
N:人数 -
A(n,i):在n的第一个家族成员中满足排序要求("可行排列")的所有排列的集合，使得i的年龄是最后一个，2 <= i <= n。
目标/strong>
确定A(N,i)接管所有i=2..N的并集。
n = 2
对person 1和person 2排序只有一种方法:
A(2,2) = { [1,2] }
n = 3
和前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 }
我希望可以应用额外的逻辑来加速计算，通过一次消除排列组。