fold_sample.py

def sample(x):
    """
          1
      2       3
    4   5   6   7
    =
    4 2 6 1 3 5 7
    >>> list(sample(['a', 'b', 'c', 'd', 'e', 'f', 'g']))
    [('d', 1), ('b', 2), ('f', 2), ('a', 3), ('c', 3), ('e', 3), ('g', 3)]
    """
    def pivot(x):
        p = len(x) // 2
        l = x[:p]
        r = x[p+1:]
        return x[p], l, r
    q = deque([(x, 0)])
    while q:
        x = q.popleft()
        p, l, r = pivot(x[0])
        depth = x[1] + 1
        if l: q.append((l, depth))
        if r: q.append((r, depth))
        yield p, depth