title: Better algorithm to riffle shuffle (or interleave) multiple lists of varying lengths
body: <p>I like to watch my favorite TV shows on the go.  I have all episodes of each show I'm following in my playlist.  Not all shows consist of the same number of episodes.  Unlike some who prefer marathons, I like to interleave episodes of one show with those of another.</p>
  
  <p>For example, if I have a show called ABC with 2 episodes, and a show called XYZ with 4 episodes, I would like my playlist to look like:</p>
  
  <pre><code>XYZe1.mp4
  ABCe1.mp4
  XYZe2.mp4
  XYZe3.mp4
  ABCe2.mp4
  XYZe4.mp4
  </code></pre>
  
  <p>One way to generate this interleaved playlist is to represent each show as a list of episodes and perform a riffle shuffle on all shows.  One could write a function that would compute, for each episode, its position on a unit-time interval (between 0.0 and 1.0 exclusive, 0.0 being beginning of season, 1.0 being end of season), then sort all episodes according to their position.</p>
  
  <p>I wrote the following simple function in Python 2.7 to perform an in-shuffle:</p>
  
  <pre><code>def riffle_shuffle(piles_list):
      scored_pile = ((((item_position + 0.5) / len(pile), len(piles_list) - pile_position), item) for pile_position, pile in enumerate(piles_list) for item_position, item in enumerate(pile))
      shuffled_pile = [item for score, item in sorted(scored_pile)]
      return shuffled_pile
  </code></pre>
  
  <p>To get the playlist for the above example, I simply need to call:</p>
  
  <pre><code>riffle_shuffle([['ABCe1.mp4', 'ABCe2.mp4'], ['XYZe1.mp4', 'XYZe2.mp4', 'XYZe3.mp4', 'XYZe4.mp4']])
  </code></pre>
  
  <p>This works fairly well most of the time.  However, there are cases where results are non-optimal--two adjacent entries in the playlist are episodes from the same show.  For example:</p>
  
  <pre><code>&gt;&gt;&gt; riffle_shuffle([['ABCe1', 'ABCe2'], ['LMNe1', 'LMNe2', 'LMNe3'], ['XYZe1', 'XYZe2', 'XYZe3', 'XYZe4', 'XYZe5']])
  ['XYZe1', 'LMNe1', 'ABCe1', 'XYZe2', 'XYZe3', 'LMNe2', 'XYZe4', 'ABCe2', 'LMNe3', 'XYZe5']
  </code></pre>
  
  <p>Notice that there are two episodes of 'XYZ' that appear side-by-side.  This situation can be fixed trivially (manually swap 'ABCe1' with 'XYZe2').</p>
  
  <p>I am curious to know if there are better ways to interleave, or perform riffle shuffle, on multiple lists of varying lengths.  I would like to know if you have solutions that are simpler, more efficient, or just plain elegant.</p>
  
  <hr>
  
  <p>Solution proposed by belisarius (thanks!):</p>
  
  <pre><code>import itertools
  def riffle_shuffle_belisarius(piles_list):
      def grouper(n, iterable, fillvalue=None):
          args = [iter(iterable)] * n
          return itertools.izip_longest(fillvalue=fillvalue, *args)
      if not piles_list:
          return []
      piles_list.sort(key=len, reverse=True)
      width = len(piles_list[0])
      pile_iters_list = [iter(pile) for pile in piles_list]
      pile_sizes_list = [[pile_position] * len(pile) for pile_position, pile in enumerate(piles_list)]
      grouped_rows = grouper(width, itertools.chain.from_iterable(pile_sizes_list))
      grouped_columns = itertools.izip_longest(*grouped_rows)
      shuffled_pile = [pile_iters_list[position].next() for position in itertools.chain.from_iterable(grouped_columns) if position is not None]
      return shuffled_pile
  </code></pre>
  
  <p>Example run:</p>
  
  <pre><code>&gt;&gt;&gt; riffle_shuffle_belisarius([['ABCe1', 'ABCe2'], ['LMNe1', 'LMNe2', 'LMNe3'], ['XYZe1', 'XYZe2', 'XYZe3', 'XYZe4', 'XYZe5']])
  ['XYZe1', 'LMNe1', 'XYZe2', 'LMNe2', 'XYZe3', 'LMNe3', 'XYZe4', 'ABCe1', 'XYZe5', 'ABCe2']
  </code></pre>