title: How to make a permutation that tailors output efficiently
body: <p>This was an interview question, which I failed to answer, but am still curious about how to solve.</p>
  
  <p>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. </p>
  
  <p>"I, a friend of the family, advised to arrange the family members as follows:"</p>
  
  <ol>
  <li>The 1 year old family member is to sit at the left end of the row.</li>
  <li>The difference in ages of every two family members sitting beside of each other mustn’t exceed 2 years.</li>
  </ol>
  
  <p>Input: integer number N, 1 ≤ N ≤ 55.</p>
  
  <p>Output: The number of possible photos that can be made by the photographer.</p>
  
  <p>Example -> Input: 4, Output: 4 </p>
  
  <p>Arrays that match the conditions:</p>
  
  <p>[1,2,3,4][1,2,4,3][1,3,2,4][1,3,4,2]</p>
  
  <p>Another Example:</p>
  
  <p>Input: 5 Output: 6</p>
  
  <p>Arrays that match the conditions:</p>
  
  <p>[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]</p>
  
  <p>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. </p>
  
  <p>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.</p>
  
  <p>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).</p>
  
  <p>How should I go about improving this situation? </p>
  
  <p>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).</p>
  
  <p>Along those lines I did copy this version of QuickPerm <a href="https://stackoverflow.com/a/2390969/1265528">https://stackoverflow.com/a/2390969/1265528</a></p>
  
  <p>Added a condition around the <code>results &lt;&lt; yield(a)</code> 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.</p>
  
  <p><strong>EDIT</strong></p>
  
  <p>Here is the incredibly disappointing solution. </p>
  
  <p>I really wanted to figure out how to generate the permutations, not an integer representing the number of possible correct permutations. -</p>
  
  <pre><code>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
  </code></pre>