Module iterutils

A generator for iterating over the elements of multiple sequences simultaneously. With N sequences given as input, the generator yields all possible distinct N-tuples that contain one element from each of the input sequences.

Example:

>>> x = MultiIter([0, 1, 2], [10, 11])
>>> list(x)
[(0, 10), (1, 10), (2, 10), (0, 11), (1, 11), (2, 11)]

The elements in each output tuple are in the order of the input sequences, and the left-most input sequence is iterated over first.

Internally, the input sequences themselves are each iterated over only once, so it is safe to pass generators as arguments. Also, this generator is significantly faster if the longest input sequence is given as the first argument. For example, this code

>>> lengths = range(1, 12)
>>> for x in MultiIter(*map(range, lengths)):
...     pass
...

runs approximately 5 times faster if the lengths list is reversed.

A generator for iterating over all choices of n elements from the input sequence vals. In each result returned, the original order of the values is preserved.

Example:

>>> x = choices(["a", "b", "c"], 2)
>>> list(x)
[('a', 'b'), ('a', 'c'), ('b', 'c')]

The order of combinations in the output sequence is always the same, so if choices() is called twice with two different sequences of the same length the first combination in each of the two output sequences will contain elements from the same positions in the two different input sequences, and so on for each subsequent pair of output combinations.

Example:

>>> x = choices(["a", "b", "c"], 2)
>>> y = choices(["1", "2", "3"], 2)
>>> zip(x, y)
[(('a', 'b'), ('1', '2')), (('a', 'c'), ('1', '3')), (('b', 'c'), ('2', '3'))]

Furthermore, the order of combinations in the output sequence is such that if the input list has n elements, and one constructs the combinations choices(input, m), then each combination in choices(input, n-m).reverse() contains the elements discarded in forming the corresponding combination in the former.

Example:

>>> x = ["a", "b", "c", "d", "e"]
>>> X = list(choices(x, 2))
>>> Y = list(choices(x, len(x) - 2))
>>> Y.reverse()
>>> zip(X, Y)
[(('a', 'b'), ('c', 'd', 'e')), (('a', 'c'), ('b', 'd', 'e')), (('a', 'd'), ('b', 'c', 'e')), (('a', 'e'), ('b', 'c', 'd')), (('b', 'c'), ('a', 'd', 'e')), (('b', 'd'), ('a', 'c', 'e')), (('b', 'e'), ('a', 'c', 'd')), (('c', 'd'), ('a', 'b', 'e')), (('c', 'e'), ('a', 'b', 'd')), (('d', 'e'), ('a', 'b', 'c'))]

A generator that yields the values from several ordered iterables in order.

Example:

>>> x = [0, 1, 2, 3]
>>> y = [1.5, 2.5, 3.5, 4.5]
>>> z = [1.75, 2.25, 3.75, 4.25]
>>> list(inorder(x, y, z))
[0, 1, 1.5, 1.75, 2, 2.25, 2.5, 3, 3.5, 3.75, 4.25, 4.5]
>>> list(inorder(x, y, z, key=lambda x: x * x))
[0, 1, 1.5, 1.75, 2, 2.25, 2.5, 3, 3.5, 3.75, 4.25, 4.5]

>>> x.sort(key=lambda x: abs(x-3))
>>> y.sort(key=lambda x: abs(x-3))
>>> z.sort(key=lambda x: abs(x-3))
>>> list(inorder(x, y, z, key=lambda x: abs(x - 3)))
[3, 2.5, 3.5, 2.25, 3.75, 2, 1.75, 4.25, 1.5, 4.5, 1, 0]

>>> x = [3, 2, 1, 0]
>>> y = [4.5, 3.5, 2.5, 1.5]
>>> z = [4.25, 3.75, 2.25, 1.75]
>>> list(inorder(x, y, z, reverse = True))
[4.5, 4.25, 3.75, 3.5, 3, 2.5, 2.25, 2, 1.75, 1.5, 1, 0]
>>> list(inorder(x, y, z, key = lambda x: -x))
[4.5, 4.25, 3.75, 3.5, 3, 2.5, 2.25, 2, 1.75, 1.5, 1, 0]

NOTE: this function will never reverse the order of elements in the input iterables. If the reverse keyword argument is False (the default) then the input sequences must yield elements in increasing order, likewise if the keyword argument is True then the input sequences must yield elements in decreasing order. Failure to adhere to this yields undefined results, and for performance reasons no check is performed to validate the element order in the input sequences.

Like Python's filter() builtin, but modifies the sequence in place.

Example:

>>> l = range(10)
>>> inplace_filter(lambda x: x > 5, l)
>>> l
[6, 7, 8, 9]

Performance considerations: the function iterates over the sequence, shuffling surviving members down and deleting whatever top part of the sequence is left empty at the end, so sequences whose surviving members are predominantly at the bottom will be processed faster.

Yield the non-unique items of an iterable, preserving order. If an item occurs N > 0 times in the input sequence, it will occur N-1 times in the output sequence.

Example:

>>> x = nonuniq([0, 0, 2, 6, 2, 0, 5])
>>> list(x)
[0, 2, 0]

Yields integers in the range [lo, hi) where 0 <= lo < hi.  Each
return value is a two-element tuple.  The first element is the
random integer, the second is the natural logarithm of the
probability with which that integer will be chosen.

The CDF for the distribution from which the integers are drawn goes
as [integer]^{n}, where n > 0.  Specifically, it's

        CDF(x) = (x^{n} - lo^{n}) / (hi^{n} - lo^{n})

n = 1 yields a uniform distribution;  n > 1 favours larger
integers, n < 1 favours smaller integers.

Yield the unique items of an iterable, preserving order. http://mail.python.org/pipermail/tutor/2002-March/012930.html

Example:

>>> x = uniq([0, 0, 2, 6, 2, 0, 5])
>>> list(x)
[0, 2, 6, 5]