How to make a permutation that tailors output efficiently

Question

This was an interview question, which I failed to answer, but am still curious about how to solve.

You have big family of N persons, 1, 2, 3, ..., N years old respectively. You want to take a picture of your very large family.There were to be present all of your family members arranged in one row.

"I, a friend of the family, advised to arrange the family members as follows:"

1. The 1 year old family member is to sit at the left end of the row.
2. The difference in ages of every two family members sitting beside of each other mustn’t exceed 2 years.

Input: integer number N, 1 ≤ N ≤ 55.

Output: The number of possible photos that can be made by the photographer.

Example -> Input: 4, Output: 4

Arrays that match the conditions:

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

Another Example:

Input: 5 Output: 6

Arrays that match the conditions:

[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]

I "solved" this problem, in Ruby, my tool of choice, by generating every permutation and filtering them, first by checking condition #1, making sure that the first entry of the array == 1, which is nice and quick.

Second by walking each array from left to right and ensuring the absolute value difference of each pair does not exceed 2. Which is terrible and slow.

My implementation, gets very slow when N > 9. As it is sorting through 300k permutations. From there the time taken is quadratic(I believe, still figuring this out).

How should I go about improving this situation?

I'm not really looking for code samples here, more ideas, which algorithm should be used to sort the permutations efficiently? Should I write my own permutation(probably yes).

Along those lines I did copy this version of QuickPerm https://stackoverflow.com/a/2390969/1265528

Added a condition around the results << yield(a) to only pick the arrays starting with 1, but I'm not sure how to best implement the rest of the aforementioned conditions from there.

EDIT

Here is the incredibly disappointing solution.

I really wanted to figure out how to generate the permutations, not an integer representing the number of possible correct permutations. -

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

If we map out the possible transitions, it should make it clearer how to figure this out:

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

Let the total number of paths that touch every number only once and begin at 1 be C_n where n is the number of nodes. Let's consider some possible cases:

• C_1 = 1
• C_2 = 1
• C_3 = 2

Now suppose n > 3. Let's consider some possible sequences:

• 1,2,... we know that if it begins this way, we can rearrange our graph by removing 1 and setting 2 as the start, and it's identical to the graph from 1 to n-1. So we have C_(n-1) sequences beginning with 1,2.
• 1,3,2,... we can do the same thing here since our next step must be 4. Rearrange the graph to begin at 4 and we have C_(n-3) sequences beginning with 1,3,2.
• 1,3,4,... We have two possibilities here: either we have only 4 nodes and 1 sequence (1,3,4,2) or we have more than 4 nodes and 0 sequences.
• 1,3,5,... We have two possibilities again: either we have only 4 nodes and 0 sequences or we have more than 4 nodes and 1 sequence (once you've gone up by 2 (after 3) you must go up by 2 until you reach the end, and then go down by 2).

So we now have that C_n = C_(n-1) + C_(n-3) + 1.