如何进行有效定制输出的排列

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]

我通过生成每个排列并过滤它们来"解决"这个问题,首先通过检查条件#1,确保数组的第一个条目== 1,这很好,很快.

其次,从左到右走每个阵列,确保每对的绝对值差异不超过2.这是可怕的和缓慢的.

当N> 9时,我的实现变得非常慢.因为它正在排序300k排列.从那里开始的时间是二次的(我相信,仍然可以解决这个问题).

我应该如何改善这种情况？

我不是真的在这里寻找代码示例,更多的想法,应该使用哪种算法来有效地排列排列？我应该写自己的排列(可能是的).

沿着这些方向我复制了这个版本的QuickPerm /sf/answers/167367861/

添加了一个条件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

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开始,我们有从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.