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

I would do it as follows.

Terms

• N: number of persons
• A(n,i): the set of all permutations that satisfy the ordering requirements ("feasible permutation") among the first n family members such that the person age i is last, 2 <= i <= n.

Objective

Determine the union of A(N,i) taken over all i=2..N.

Algorithm

n = 2

There is but one way to order persons 1 and 2:

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

n = 3

and two ways to order the first 3:

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

n = 4

We're starting to get something a little more interesting when we consider the first four. Initially, disregard the requirement that adjacent members differ in age by at most two years.

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

Notice how these sets were determined. Consider A(4,2). We take the single permutation in A(3,2), and insert 4 into each of two possible locations.

We next remove all combinations that don't satisfy the adjacent age difference requirement, and are left with the following:

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

Again, first calculate the sets for n=5 without reference to the adjacent age requirement:

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 }

Notice how these sets were generated combinatorially from A(4,2), A(4,3), A(4,4) and A(5,2). To compute A(5,2), for example, for each permuation in A(4,2) (there's just one), we insert 5 into each position after the first and before the last.

Now remove all but the feasible permuations, leaving us with:

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 }

Continue in this fashion until A(N,i) have been computed for all i=2,...N.

If N => 5, the feasible permutations would be the union of these four sets:

{ [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 }

I expect additional logic could be applied to speed the calculations, by eliminating groups of permutations at one time.

Answer 2

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.

Answer 3

Create a method f that takes N and returns an array of the possible arrays. In doing this, use recursion. When N = 1, you know that the possibility is only [1], so the output should be [[1]]. Otherwise, calculate f(N - 1). To get f(N) from it, consider which positions N can be inserted into in each array in f(N - 1).

Answer 4

I'm not sure whether an optimized algorithm for this problem exists, but a brute-force approach that comes to my mind is backtracking.

It is more efficient than iterating over all possible precomputed permutations, as it can immediately stop if the first non-matching pair is found. So, it can prune huge parts of the search space (in other words, it does not have to look at all N! permutations).