利用列表具有快速删除和插入的事实,并扩展先前的解决方案(https://dev59.com/-Gct5IYBdhLWcg3wPbEm#25229111):
列表项
- 枚举固定元素并复制它们及其索引
- 从列表中删除固定元素
- 混洗剩余子集
- 将固定元素放回去
这将使用内存开销的原地操作,该开销取决于列表中固定元素的数量。时间复杂度为线性。 shuffle_subset 的一个可能更一般的实现:
#!/usr/bin/env python
"""Shuffle elements in a list, except for a sub-set of the elments.
The sub-set are those elements that should retain their position in
the list. Some example usage:
>>> from collections import namedtuple
>>> class CAnswer(namedtuple("CAnswer","x fixed")):
... def __bool__(self):
... return self.fixed is True
... __nonzero__ = __bool__ # For Python 2. Called by bool in Py2.
... def __repr__(self):
... return "<CA: >".format(self.x)
...
>>> val = [3, 2, 0, 1, 5, 9, 4]
>>> fix = [2, 5]
>>> lst = [CAnswer(v, i in fix) for i, v in enumerate(val)]
>>> print("Start ", 0, ": ", lst)
Start 0 : [<CA: 3>, <CA: 2>, <CA: 0>, <CA: 1>, <CA: 5>, <CA: 9>, <CA: 4>]
Using a predicate to filter.
>>> for i in range(4): # doctest: +NORMALIZE_WHITESPACE
... shuffle_subset(lst, lambda x : x.fixed)
... print([lst[i] for i in fix], end=" ")
...
[<CA: 0>, <CA: 9>] [<CA: 0>, <CA: 9>] [<CA: 0>, <CA: 9>] [<CA: 0>, <CA: 9>]
>>> for i in range(4): # doctest: +NORMALIZE_WHITESPACE
... shuffle_subset(lst) # predicate = bool()
... print([lst[i] for i in fix], end=" ")
...
[<CA: 0>, <CA: 9>] [<CA: 0>, <CA: 9>] [<CA: 0>, <CA: 9>] [<CA: 0>, <CA: 9>]
Exclude certain postions from the shuffle. For example, exclude the
first two elements:
>>> fix = [0, 1]
>>> lst = [CAnswer(v, i in fix) for i, v in enumerate(val)]
>>> print("Start ", 0, ": ", lst)
Start 0 : [<CA: 3>, <CA: 2>, <CA: 0>, <CA: 1>, <CA: 5>, <CA: 9>, <CA: 4>]
>>> for i in range(4): # doctest: +NORMALIZE_WHITESPACE
... shuffle_subset(lst, fix)
... print([lst[i] for i in fix], end=" ")
...
[<CA: 3>, <CA: 2>] [<CA: 3>, <CA: 2>] [<CA: 3>, <CA: 2>] [<CA: 3>, <CA: 2>]
Using a selector with the same number of elements as lst:
>>> fix = [0, 1]
>>> lst = [CAnswer(v, i in fix) for i, v in enumerate(val)]
>>> sel = [(i in fix) for i, _ in enumerate(val)]
>>> print("Start ", 0, ": ", lst)
Start 0 : [<CA: 3>, <CA: 2>, <CA: 0>, <CA: 1>, <CA: 5>, <CA: 9>, <CA: 4>]
>>> for i in range(4): # doctest: +NORMALIZE_WHITESPACE
... shuffle_subset(lst, sel)
... print([lst[i] for i in fix], end=" ")
...
[<CA: 3>, <CA: 2>] [<CA: 3>, <CA: 2>] [<CA: 3>, <CA: 2>] [<CA: 3>, <CA: 2>]
A generator as selector works fine too:
>>> fix = [0, 1]
>>> lst = [CAnswer(v, i in fix) for i, v in enumerate(val)]
>>> print("Start ", 0, ": ", lst)
Start 0 : [<CA: 3>, <CA: 2>, <CA: 0>, <CA: 1>, <CA: 5>, <CA: 9>, <CA: 4>]
>>> for i in range(4): # doctest: +NORMALIZE_WHITESPACE
... sel = ((i in fix) for i, _ in enumerate(val))
... shuffle_subset(lst, sel)
... print([lst[i] for i in fix], end=" ")
...
[<CA: 3>, <CA: 2>] [<CA: 3>, <CA: 2>] [<CA: 3>, <CA: 2>] [<CA: 3>, <CA: 2>]
"""
from __future__ import print_function
import random
def shuffle_subset(lst, predicate=None):
"""All elements in lst, except a sub-set, are shuffled.
The predicate defines the sub-set of elements in lst that should
not be shuffled:
+ The predicate is a callable that returns True for fixed
elements, predicate(element) --> True or False.
+ If the predicate is None extract those elements where
bool(element) == True.
+ The predicate is an iterable that is True for fixed elements
or len(predicate) == len(lst).
+ The predicate is a list of indices of fixed elements in lst
with len(predicate) < len(lst).
"""
def extract_fixed_elements(pred, lst):
try:
if callable(pred) or pred is None:
pred = bool if pred is None else pred
fixed_subset = [(i, e) for i, e in enumerate(lst) if pred(e)]
elif (hasattr(pred, '__next__') or len(pred) == len(lst)):
fixed_subset = [(i, lst[i]) for i, p in enumerate(pred) if p]
elif len(pred) < len(lst):
fixed_subset = [(i, lst[i]) for i in pred]
else:
raise TypeError("Predicate not supported.".format(pred))
except TypeError as err:
raise TypeError("Predicate not supported. ".format(pred, err))
return fixed_subset
#
fixed_subset = extract_fixed_elements(predicate, lst)
fixed_subset.reverse() # Delete fixed elements from high index to low.
for i, _ in fixed_subset:
del lst[i]
random.shuffle(lst)
fixed_subset.reverse() # Insert fixed elements from low index to high.
for i, e in fixed_subset:
lst.insert(i, e)
if __name__ == "__main__":
import doctest
doctest.testmod()
list[2:]
创建了一个全新的列表,没有被其他地方引用,因此结果就丢失了。 - Felix Kling