title: Generate all permutations of a list without adjacent equal elements
body: <p>When we sort a list, like</p>
  
  <pre><code>a = [1,2,3,3,2,2,1]
  sorted(a) =&gt; [1, 1, 2, 2, 2, 3, 3]
  </code></pre>
  
  <p>equal elements are always adjacent in the resulting list. </p>
  
  <p>How can I achieve the opposite task - shuffle the list so that equal elements are never (or as seldom as possible) adjacent?</p>
  
  <p>For example, for the above list one of the possible solutions is</p>
  
  <pre><code>p = [1,3,2,3,2,1,2]
  </code></pre>
  
  <p>More formally, given a list <code>a</code>, generate a permutation <code>p</code> of it that minimizes the number of pairs <code>p[i]==p[i+1]</code>. </p>
  
  <p>Since the lists are large, generating and filtering all permutations is not an option.</p>
  
  <p>Bonus question: how to generate all such permutations efficiently?</p>
  
  <p>This is the code I'm using to test the solutions: <a href="https://gist.github.com/gebrkn/9f550094b3d24a35aebd" rel="nofollow noreferrer">https://gist.github.com/gebrkn/9f550094b3d24a35aebd</a></p>
  
  <p>UPD: Choosing a winner here was a tough choice, because many people posted excellent answers. <a href="https://stackoverflow.com/a/25285879/989121">@VincentvanderWeele</a>, <a href="https://stackoverflow.com/a/25290780/989121">@David Eisenstat</a>, <a href="https://stackoverflow.com/a/25291640/989121">@Coady</a>, <a href="https://stackoverflow.com/a/25286137/989121">@enrico.bacis</a> and <a href="https://stackoverflow.com/a/25401193/989121">@srgerg</a> provided functions that generate the best possible permutation flawlessly. <a href="https://stackoverflow.com/a/25286251/989121">@tobias_k</a> and David also answered the bonus question (generate all permutations). Additional points to David for the correctness proof.</p>
  
  <p>The code from @VincentvanderWeele appears to be the fastest.</p>