28 A collection of iteration utilities.
38 from .
import git_version
41 __author__ =
"Kipp Cannon <kipp.cannon@ligo.org>"
42 __version__ =
"git id %s" % git_version.id
43 __date__ = git_version.date
57 A generator for iterating over the elements of multiple sequences
58 simultaneously. With N sequences given as input, the generator
59 yields all possible distinct N-tuples that contain one element from
60 each of the input sequences.
64 >>> x = MultiIter([0, 1, 2], [10, 11])
66 [(0, 10), (1, 10), (2, 10), (0, 11), (1, 11), (2, 11)]
68 The elements in each output tuple are in the order of the input
69 sequences, and the left-most input sequence is iterated over first.
71 Internally, the input sequences themselves are each iterated over
72 only once, so it is safe to pass generators as arguments. Also,
73 this generator is significantly faster if the longest input
74 sequence is given as the first argument. For example, this code
76 >>> lengths = range(1, 12)
77 >>> for x in MultiIter(*map(range, lengths)):
81 runs approximately 5 times faster if the lengths list is reversed.
83 if len(sequences) > 1:
90 head = tuple((x,)
for x
in sequences[0])
95 for t
in sequences[0]:
101 A generator for iterating over all choices of n elements from the
102 input sequence vals. In each result returned, the original order
103 of the values is preserved.
107 >>> x = choices(["a", "b", "c"], 2)
109 [('a', 'b'), ('a', 'c'), ('b', 'c')]
111 The order of combinations in the output sequence is always the
112 same, so if choices() is called twice with two different sequences
113 of the same length the first combination in each of the two output
114 sequences will contain elements from the same positions in the two
115 different input sequences, and so on for each subsequent pair of
120 >>> x = choices(["a", "b", "c"], 2)
121 >>> y = choices(["1", "2", "3"], 2)
123 [(('a', 'b'), ('1', '2')), (('a', 'c'), ('1', '3')), (('b', 'c'), ('2', '3'))]
125 Furthermore, the order of combinations in the output sequence is
126 such that if the input list has n elements, and one constructs the
127 combinations choices(input, m), then each combination in
128 choices(input, n-m).reverse() contains the elements discarded in
129 forming the corresponding combination in the former.
133 >>> x = ["a", "b", "c", "d", "e"]
134 >>> X = list(choices(x, 2))
135 >>> Y = list(choices(x, len(x) - 2))
138 [(('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'))]
140 NOTE: this generator is identical to the itertools.combinations()
141 generator in Python's standard library. This routine was written
142 before Python provided that functionality, and is now only
143 preserved for two reasons. The first is to maintain this API for
144 existing codes that were written before the standard library
145 provided the capability. But the second reason is because the
146 Python standard library doesn't make the guarantees that we do,
147 here, about the order of the results. Specifically, there is no
148 guarantee that itertools.combinations() is repeatable, nor is there
149 a statement on how to obtain the inverse of the sequence as
150 described above. At the time of writing the order in which results
151 are produced is identical to this generator and in all use cases
152 they are exact substitutes for each other, and new code should use
153 itertools.combinations(). Be careful making assumptions about the
154 order of the results, add safety checks where needed, and if a
155 problem arises this generator can be used as a fall-back.
161 for i, v
in enumerate(vals[:-n]):
163 for c
in choices(vals[i+1:], n):
177 Yield the unique items of an iterable, preserving order.
178 http://mail.python.org/pipermail/tutor/2002-March/012930.html
182 >>> x = uniq([0, 0, 2, 6, 2, 0, 5])
188 if e
not in temp_dict:
189 yield temp_dict.setdefault(e, e)
194 Yield the non-unique items of an iterable, preserving order. If an
195 item occurs N > 0 times in the input sequence, it will occur N-1
196 times in the output sequence.
200 >>> x = nonuniq([0, 0, 2, 6, 2, 0, 5])
208 temp_dict.setdefault(e, e)
211 def flatten(sequence, levels = 1):
214 >>> nested = [[1,2], [[3]]]
215 >>> list(flatten(nested))
223 for y
in flatten(x, levels - 1):
238 Like Python's filter() builtin, but modifies the sequence in place.
242 >>> l = list(range(10))
243 >>> inplace_filter(lambda x: x > 5, l)
247 Performance considerations: the function iterates over the
248 sequence, shuffling surviving members down and deleting whatever
249 top part of the sequence is left empty at the end, so sequences
250 whose surviving members are predominantly at the bottom will be
254 for source
in range(len(sequence)):
255 if func(sequence[source]):
256 sequence[target] = sequence[source]
258 del sequence[target:]
270 def inorder(*iterables, **kwargs):
272 A generator that yields the values from several ordered iterables
278 >>> y = [1.5, 2.5, 3.5, 4.5]
279 >>> z = [1.75, 2.25, 3.75, 4.25]
280 >>> list(inorder(x, y, z))
281 [0, 1, 1.5, 1.75, 2, 2.25, 2.5, 3, 3.5, 3.75, 4.25, 4.5]
282 >>> list(inorder(x, y, z, key=lambda x: x * x))
283 [0, 1, 1.5, 1.75, 2, 2.25, 2.5, 3, 3.5, 3.75, 4.25, 4.5]
285 >>> x.sort(key=lambda x: abs(x-3))
286 >>> y.sort(key=lambda x: abs(x-3))
287 >>> z.sort(key=lambda x: abs(x-3))
288 >>> list(inorder(x, y, z, key=lambda x: abs(x - 3)))
289 [3, 2.5, 3.5, 2.25, 3.75, 2, 1.75, 4.25, 1.5, 4.5, 1, 0]
292 >>> y = [4.5, 3.5, 2.5, 1.5]
293 >>> z = [4.25, 3.75, 2.25, 1.75]
294 >>> list(inorder(x, y, z, reverse = True))
295 [4.5, 4.25, 3.75, 3.5, 3, 2.5, 2.25, 2, 1.75, 1.5, 1, 0]
296 >>> list(inorder(x, y, z, key = lambda x: -x))
297 [4.5, 4.25, 3.75, 3.5, 3, 2.5, 2.25, 2, 1.75, 1.5, 1, 0]
299 NOTE: this function will never reverse the order of elements in
300 the input iterables. If the reverse keyword argument is False (the
301 default) then the input sequences must yield elements in increasing
302 order, likewise if the keyword argument is True then the input
303 sequences must yield elements in decreasing order. Failure to
304 adhere to this yields undefined results, and for performance
305 reasons no check is performed to validate the element order in the
308 reverse = kwargs.pop(
"reverse",
False)
309 keyfunc = kwargs.pop(
"key",
lambda x: x)
311 raise TypeError(
"invalid keyword argument '%s'" % list(kwargs.keys())[0])
313 for iterable
in iterables:
314 next_ = functools.partial(next, iter(iterable))
317 nextvals[next_] = keyfunc(nextval), nextval, next_
318 except StopIteration:
324 select =
lambda seq: max(seq, key =
lambda elem: elem[0])
326 select =
lambda seq: min(seq, key =
lambda elem: elem[0])
327 if len(nextvals) > 1:
329 _, val, next_ = select(nextvals.values())
333 nextvals[next_] = keyfunc(nextval), nextval, next_
334 except StopIteration:
336 if len(nextvals) < 2:
341 (_, val, next_), = nextvals.values()
346 except StopIteration:
361 Yields integers in the range [lo, hi) where 0 <= lo < hi. Each
362 return value is a two-element tuple. The first element is the
363 random integer, the second is the natural logarithm of the
364 probability with which that integer will be chosen.
366 The CDF for the distribution from which the integers are drawn goes
367 as [integer]^{n}, where n > 0. Specifically, it's
369 CDF(x) = (x^{n} - lo^{n}) / (hi^{n} - lo^{n})
371 n = 1 yields a uniform distribution; n > 1 favours larger
372 integers, n < 1 favours smaller integers.
375 raise ValueError(
"require 0 <= lo < hi: lo = %d, hi = %d" % (lo, hi))
377 raise ValueError(
"n <= 0: %g" % n)
381 lnP = math.log(1. / (hi - lo))
383 raise ValueError(
"[lo, hi) domain error")
387 yield rnd(lo, hi), lnP
390 lnP = numpy.arange(lo, hi + 1, dtype =
"double")**n
394 lnP = tuple(numpy.log(lnP[1:] - lnP[:-1]))
395 if numpy.isinf(lnP).any():
396 raise ValueError(
"[lo, hi) domain error")
398 beta = lo**n / (hi**n - lo**n)
400 alpha = hi / (1. + beta)**n
404 index = int(flr(alpha * (rnd() + beta)**n))
408 yield index, lnP[index - lo]
def inorder(*iterables, **kwargs)
A generator that yields the values from several ordered iterables in order.
def inplace_filter(func, sequence)
Like Python's filter() builtin, but modifies the sequence in place.
def flatten(sequence, levels=1)
Example: nested = [[1,2], [[3]]] list(flatten(nested)) [1, 2, [3]].
def randindex(lo, hi, n=1.)
Yields integers in the range [lo, hi) where 0 <= lo < hi.
def nonuniq(iterable)
Yield the non-unique items of an iterable, preserving order.
def choices(vals, n)
A generator for iterating over all choices of n elements from the input sequence vals.
def uniq(iterable)
Yield the unique items of an iterable, preserving order.
def MultiIter(*sequences)
A generator for iterating over the elements of multiple sequences simultaneously.