Databases
StackOverflow2013
Postsdbo
POBetter algorithm to riffle shuffle (or interleave) multiple lists of varying lengths
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POBetter algorithm to riffle shuffle (or interleave) multiple lists of varying lengths
    primarykey
    data
    text
    <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>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USAdeel Zafar Soomro
    1. USAdeel Zafar Soomro
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POBetter algorithm to riffle shuffle (or interleave) multiple lists of varying lengths
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POBetter algorithm to riffle shuffle (or interleave) multiple lists of varying lengths
      1. USPaŭlo Ebermann
      1. VTFavorite
    3. VO
      singulars
      1. POBetter algorithm to riffle shuffle (or interleave) multiple lists of varying lengths
      1. This table or related slice is empty.
      1. VTUpMod
    1. COOne problem is that if a series, say "XYZ", has much (two) more items than all the others, then it's impossible not have a side-by-side appearnce.
      singulars
      1. POBetter algorithm to riffle shuffle (or interleave) multiple lists of varying lengths
      1. USypercubeᵀᴹ
    2. CO@ypercube: Indeed, when one list has more than twice as many items as all other lists combined, there will be adjacent entries that belong to the same list. However, this is usually not the case. I'm looking for algorithms that do better in avoiding such adjacency problems.
      singulars
      1. POBetter algorithm to riffle shuffle (or interleave) multiple lists of varying lengths
      1. USAdeel Zafar Soomro
    3. CODo you want it _random_? Do you accept a deterministic solution?
      singulars
      1. POBetter algorithm to riffle shuffle (or interleave) multiple lists of varying lengths
      1. USDr. belisarius
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload