def chunk( seq, size, pad=None ):
    '''
    Slice a list into consecutive disjoint 'chunks' of
    length equal to size. The last chunk is padded if necessary.

    >>> list(chunk(range(1,10),3))
    [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
    >>> list(chunk(range(1,9),3)) 
    [[1, 2, 3], [4, 5, 6], [7, 8, None]]
    >>> list(chunk(range(1,8),3)) 
    [[1, 2, 3], [4, 5, 6], [7, None, None]]
    >>> list(chunk(range(1,10),1)) 
    [[1], [2], [3], [4], [5], [6], [7], [8], [9]]
    >>> list(chunk(range(1,10),9)) 
    [[1, 2, 3, 4, 5, 6, 7, 8, 9]]
    >>> for X in chunk([],3): print X
    >>>
    '''
    n = len(seq)
    mod = n % size
    for i in xrange(0, n-mod, size):
        yield seq[i:i+size]
    if mod:
        padding = [pad] * (size-mod)
        yield seq[-mod:] + padding
            
def columnise( seq, numcols, pad=None ):
    '''
    >>> columnise(range(1,10),3) 
    [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
    >>> columnise(range(1,9),3) 
    [(1, 4, 7), (2, 5, 8), (3, 6, None)]
    >>> columnise(range(1,8),3)
    [(1, 4, 7), (2, 5, None), (3, 6, None)]
    '''
    return zip( *chunk(seq, numcols, pad) )

def kslice( seq, k ):
    '''
    Generate all slices of seq that have length k.

    >>> list(kslice(range(1,4), 2))
    [[1, 2], [1, 3], [2, 3]]
    >>> [''.join(s) for s in kslice( 'abcd', 3 )] 
    ['abc', 'abd', 'acd', 'bcd']
    '''
    for s in nksubsets( len(seq), k ):
        yield [ seq[i-1] for i in s ]

def nksubsets( n, k ):
    '''
    Generate all subsets of S(n) that have k items.
    S(n) = {1, 2, 3, ..., n}

    >>> list(nksubsets(3, 2)) 
    [[1, 2], [1, 3], [2, 3]]
    '''
    m = n - k + 1
    indexer = range(0, k)
    seq = range(1, k+1)
    last = range(m, n+1)
    yield seq[:]
    while seq != last:
        high_value = -1
        high_index = -1
        for i in indexer:
            val = seq[i]
            if val > high_value and val < m + i:
                high_value = val
                high_index = i
        for j in range(k - high_index):
            seq[j+high_index] = high_value + j + 1
        yield seq[:]

def subsequence_ascending( seq ):
    '''based on original C code by Lucian Bentea
 
    >>> subsequence_ascending( [1, 2, 3, 4] ) 
    [1, 2, 3, 4]
    >>> subsequence_ascending( [4, 3, 2, 1] ) 
    [4]
    >>> subsequence_ascending( [1, 0, 2, 0, 3, 0, 4] ) 
    [1, 2, 3, 4]
    >>> subsequence_ascending( [1, 9, 2, 9, 3, 9, 4] ) 
    [1, 9, 9, 9]
    >>> subsequence_ascending( [1, 9, 2, 8, 3, 2, 4] ) 
    [1, 2, 3, 4]
    >>> subsequence_ascending( [1, 9, 2, 8, 3, 7, 4] ) 
    [1, 2, 3, 7]
    >>> subsequence_ascending( [1, 1, 1, 1] ) 
    [1, 1, 1, 1]
    >>> subsequence_ascending( [] ) 
    []
    '''
    if not seq: return []
    n = len( seq )
    U = [1] * n
    V = [0] * n
    for i in xrange( n-2, -1, -1 ):
        max_ = 0
        imax = 0
        seq_i = seq[i]
        for j in xrange( i+1, n ):
            if U[j] > max_ and seq_i <= seq[j]:
                max_ = U[j]
                imax = j
        U[i] = 1 + max_
        V[i] = imax
    max_ = U[0]
    imax = 0
    for i in xrange( 1, n ):
        if U[i] > max_:
            max_ = U[i]
            imax = i
    ret = []
    while True:
        ret.append( seq[imax] )
        imax = V[imax]
        if not imax:
            break
    return ret

def itemwise_intersect( *args ):
    '''
    >>> itemwise_intersect('##a##b#a', '%%a%%b%a')
    set([(2, 'a'), (7, 'a'), (5, 'b')])
    '''
    m = min( map( len, args ) )
    s = set(enumerate(args[0][:m]))
    for t in ( set(enumerate(X[:m])) for X in args[1:] ):
        s.intersection_update(t)
    return s

def _test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    _test()