/
listtools.py
465 lines (401 loc) · 14.9 KB
/
listtools.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
""" Utility functions for working with lists """
from __future__ import division, print_function, absolute_import, unicode_literals
#*****************************************************************
# pyGSTi 0.9: Copyright 2015 Sandia Corporation
# This Software is released under the GPL license detailed
# in the file "license.txt" in the top-level pyGSTi directory
#*****************************************************************
import numpy as _np
import itertools as _itertools
def remove_duplicates_in_place(l,indexToTest=None):
"""
Remove duplicates from the list passed as an argument.
In the special case when l contains WeightedGateString instances, the
duplicates are removed in such a way that the largest weight instance
of any set of duplicates is kept.
Parameters
----------
l : list
The list to remove duplicates from.
indexToTest : int, optional
If not None, the index within the elements of l to test. For
example, if all the elements of l contain 2 tuples (x,y) then
set indexToTest == 1 to remove tuples with duplicate y-values.
Returns
-------
None
"""
s = set(); n = 0
for x in l:
t = x if indexToTest is None else x[indexToTest]
#TODO: create a special duplicate removal function for use with
# WeighedGateStrings and include the below commented block:
#Special case of weighted gate strings: if collisions
# keep the hightest weight string
#if isinstance(t, _WeightedGateString) and t in s:
# for gs in l[0:n]:
# if gs == t:
# if isinstance(gs, _WeightedGateString):
# gs.weight = max(gs.weight, t.weight)
# break
if t not in s:
s.add(t)
l[n] = x; n += 1
del l[n:]
def remove_duplicates(l,indexToTest=None):
"""
Remove duplicates from the a list and return the result.
In the special case when l contains WeightedGateString instances, the
duplicates are removed in such a way that the largest weight instance
of any set of duplicates is kept.
Parameters
----------
l : list
The list to remove duplicates from.
indexToTest : int, optional
If not None, the index within the elements of l to test. For
example, if all the elements of l contain 2 tuples (x,y) then
set indexToTest == 1 to remove tuples with duplicate y-values.
Returns
-------
list
the list after duplicates have been removed.
"""
lcopy = l[:]; remove_duplicates_in_place(lcopy,indexToTest)
return lcopy
def compute_occurrence_indices(lst):
"""
Returns a 0-based list of integers specifying which occurrence,
i.e. enumerated duplicate, each list item is.
For example, if `lst` = [ 'A','B','C','C','A'] then the
returned list will be [ 0 , 0 , 0 , 1 , 1 ]. This is useful
when working with `DataSet` objects that have `collisionAction`
set to "keepseparate".
Parameters
----------
lst : list
The list to process.
Returns
-------
list
"""
lookup = {}; ret = []
for x in lst:
if x not in lookup:
lookup[x] = 0
else:
lookup[x] += 1
ret.append( lookup[x] )
return ret
def find_replace_tuple(t,aliasDict):
"""
Replace elements of t according to rules in `aliasDict`.
Parameters
----------
t : tuple or list
The object to perform replacements upon.
aliasDict : dictionary
Dictionary whose keys are potential elements of `t` and whose values
are tuples corresponding to a sub-sequence that the given element should
be replaced with. If None, no replacement is performed.
Returns
-------
tuple
"""
t = tuple(t)
if aliasDict is None: return t
for label,expandedStr in aliasDict.items():
while label in tuple(t):
i = t.index(label)
t = t[:i] + tuple(expandedStr) + t[i+1:]
return t
def find_replace_tuple_list(list_of_tuples,aliasDict):
"""
Applies :func:`find_replace_tuple` on each element of `list_of_tuples`.
Parameters
----------
list_of_tuples : list
A list of tuple objects to perform replacements upon.
aliasDict : dictionary
Dictionary whose keys are potential elements of `t` and whose values
are tuples corresponding to a sub-sequence that the given element should
be replaced with. If None, no replacement is performed.
Returns
-------
list
"""
return [ find_replace_tuple(t,aliasDict) for t in list_of_tuples ]
def sorted_partitions(n):
"""
Iterate over all sorted (decreasing) partitions of integer `n`.
A partition of `n` here is defined as a list of one or more non-zero
integers which sum to `n`. Sorted partitions (those iterated over here)
have their integers in decreasing order.
Parameters
----------
n : int
The number to partition.
Returns
-------
iterator
Iterates over arrays of descending integers (sorted partitions).
"""
if n == 0: #special case
yield _np.zeros(0,_np.int64); return
p = _np.zeros(n,_np.int64)
k = 0 # Index of last element in a partition
p[k] = n # Initialize first partition as number itself
# This loop first yields current partition, then generates next
# partition. The loop stops when the current partition has all 1s
while True:
yield p[0:k+1]
# Find the rightmost non-one value in p[]. Also, update the
# rem_val so that we know how much value can be accommodated
rem_val = 0;
while k >= 0 and p[k] == 1:
rem_val += p[k]
k -= 1
# if k < 0, all the values are 1 so there are no more partitions
if k < 0: return
# Decrease the p[k] found above and adjust the rem_val
p[k] -= 1
rem_val += 1
# If rem_val is more, then the sorted order is violated. Divide
# rem_val in different values of size p[k] and copy these values at
# different positions after p[k]
while rem_val > p[k]:
p[k+1] = p[k]
rem_val -= p[k]
k += 1
# Copy rem_val to next position and increment position
p[k+1] = rem_val
k += 1
def partitions(n):
"""
Iterate over all partitions of integer `n`.
A partition of `n` here is defined as a list of one or more non-zero
integers which sum to `n`. Every partition is iterated over exacty
once - there are no duplicates/repetitions.
Parameters
----------
n : int
The number to partition.
Returns
-------
iterator
Iterates over arrays of integers (partitions).
"""
for p in sorted_partitions(n):
previous = tuple()
for pp in _itertools.permutations(p[::-1]): # flip p so it's in *ascending* order
if pp > previous: # only *unique* permutations
previous = pp # (relies in itertools implementatin detail that
yield pp # any permutations of a sorted iterable are in
# sorted order unless they are duplicates of prior permutations
def partition_into(n, nbins):
"""
Iterate over all partitions of integer `n` into `nbins` bins.
Here, unlike in :function:`partition`, a "partition" is allowed to contain
zeros. For example, (4,1,0) is a valid partition of 5 using 3 bins. This
function fixes the number of bins and iterates over all possible length-
`nbins` partitions while allowing zeros. This is equivalent to iterating
over all usual partitions of length at most `nbins` and inserting zeros into
all possible places for partitions of length less than `nbins`.
Parameters
----------
n : int
The number to partition.
nbins : int
The fixed number of bins, equal to the length of all the
partitions that are iterated over.
Returns
-------
iterator
Iterates over arrays of integers (partitions).
"""
if n == 0:
a = _np.zeros(nbins,_np.int64)
yield tuple(a)
elif n == 1:
a = _np.zeros(nbins,_np.int64)
for i in range(nbins):
a[i] = 1
yield tuple(a)
a[i] = 0
elif n == 2:
a = _np.zeros(nbins,_np.int64)
for i in range(nbins):
a[i] = 2
yield tuple(a)
a[i] = 0
for i in range(nbins):
a[i] = 1
for j in range(i+1,nbins):
a[j] = 1
yield tuple(a)
a[j] = 0
a[i] = 0
else:
for p in _partition_into_slow(n, nbins):
yield p
def _partition_into_slow(n, nbins):
"""
Helper function for `partition_into` that performs the same task for
a general number `n`.
"""
for p in sorted_partitions(n):
if len(p) > nbins: continue # don't include partitions of length > nbins
previous = tuple()
p = _np.concatenate( (p, _np.zeros(nbins-len(p),_np.int64)) ) # pad with zeros
for pp in _itertools.permutations(p[::-1]):
if pp > previous: # only *unique* permutations
previous = pp # (relies in itertools implementatin detail that
yield pp # any permutations of a sorted iterable are in
# sorted order unless they are duplicates of prior permutations
def incd_product(*args):
"""
Like `itertools.product` but returns the first modified index (which was
incremented) along with the product tuple itself.
Parameters
----------
*args : iterables
Any number of iterable things that we're taking the product of.
Returns
-------
iterator over tuples
"""
lists = [list(a) for a in args] # so we can get new iterators to each argument
iters = [iter(l) for l in lists]
N = len(lists)
incr = 0 # the first index that was changed (incremented) since the last iteration
try:
t = [ next(i) for i in iters ]
except StopIteration: # at least one list is empty
yield incr, () #just yield one item w/empty tuple, like itertools.product
return
yield incr, tuple(t) # first yield is special b/c establishes baseline (incr==0)
incr = N-1
while incr >= 0:
try: # to increment index incr
t[incr] = next(iters[incr])
except StopIteration: # if exhaused, increment iterator to left
incr -= 1
else: # reset all iterators to right of incremented one and yield
for i in range(incr+1,N):
iters[i]= iter(lists[i])
t[i] = next(iters[i]) #won't raise error b/c all lists have len >= 1
yield incr, tuple(t)
incr = N-1 #next time try to increment the last index again
return
# ------------------------------------------------------------------------------
# Machinery initially designed for an in-place take operation, which computes
# how to do in-place permutations of arrays/lists efficiently. Kept here
# commented out in case this is needed some time in the future.
# ------------------------------------------------------------------------------
#
#def build_permute_copy_order(indices):
# #Construct a list of the operations needed to "take" indices
# # out of an array.
#
# nIndices = len(indices)
# flgs = _np.zeros(nIndices,'bool') #flags indicating an index has been processed
# shelved = {}
# copyList = []
#
# while True: #loop until we've processed everything
#
# #The cycle has ended. Now find an unprocessed
# # destination to begin a new cycle
# for i in range(nIndices):
# if flgs[i] == False:
# if indices[i] == i: # index i is already where it need to be!
# flgs[i] = True
# else:
# cycleFirstIndex = iDest = i
# if cycleFirstIndex in indices:
# copyList.append( (-1,i) ) # iDest == -1 means copy to offline storage
# break;
# else:
# break #everything has been processed -- we're done!
#
# while True: # loop over cycle
#
# # at this point, data for index iDest has been stored or copied
# iSrc = indices[iDest] # get source index for current destination
#
# # record appropriate copy command
# if iSrc == cycleFirstIndex:
# copyList.append( (iDest, -1) ) # copy from offline storage
# flgs[iDest] = True
#
# #end of this cycle since we've hit our starting point,
# # but no need to shelve first cycle element in this case.
# break #(end of cycle)
# else:
# if iSrc in shelved: #original iSrc is now at index shelved[iSrc]
# iSrc = shelved[iSrc]
#
# copyList.append( (iDest,iSrc) ) # => copy src -> dest
# flgs[iDest] = True
#
# if iSrc < nIndices:
# #Continue cycle (swapping within "active" (index < nIndices) region)
# iDest = iSrc # make src the new dest
# else:
# #end of this cycle, and first cycle index hasn't been
# # used, so shelve it (store it for later use) if it
# # will be needed in the future.
# if cycleFirstIndex in indices:
# copyList.append( (iSrc,-1) )
# shelved[cycleFirstIndex] = iSrc
#
# break #(end of cycle)
#
# return copyList
#
## X X X
## 0 1 2 3 (nIndices == 4)
## 3, 0, 7, 4
## store 0
## 3 -> 0
## 4 -> 3
## stored[0] -> 4, shelved[0] = 4
## store 1
## shelved[0]==4 -> 1, NO((stored[1] -> 4, shelved[1] = 4)) B/C don't need index 1
## store 2
## 7 -> 2
## NO((Stored[2] -> 7, istore[2] = 7))
#
#
#def inplace_take(a, indices, axis=None, copyList=None):
# check = a.take(indices, axis=axis) #DEBUGGING
# return check #FIX FOR NOW = COPY
#
# if axis is None:
# def mkindex(i):
# return i
# else:
# def mkindex(i):
# sl = [slice(None)] * a.ndim
# sl[axis] = i
# return sl
#
# if copyList is None:
# copyList = build_permute_copy_order(indices)
#
# store = None
# for iDest,iSrc in copyList:
# if iDest == -1: store = a[mkindex(iSrc)].copy() #otherwise just get a view!
# elif iSrc == -1: a[mkindex(iDest)] = store
# else: a[mkindex(iDest)] = a[mkindex(iSrc)]
#
# ret = a[mkindex(slice(0,len(indices)))]
# if _np.linalg.norm(ret-check) > 1e-8 :
# print("ERROR CHECK FAILED")
# print("ret = ",ret)
# print("check = ",check)
# print("diff = ",_np.linalg.norm(ret-check))
# assert(False)
# #check = None #free mem?
# #return ret
# return check