У меня такая проблема:
Существует список элементов класса CAnswer (нет необходимости описывать класс), и мне нужно перетасовать его, но с одним ограничением - некоторые элементы списка имеют CAnswer.freeze, установленный в True, и эти элементы нельзя перетасовывать, но оставаться на их исходных позициях. Итак, скажем, для данного списка:
[a, b, c, d, e, f]
Где все элементы являются экземплярами CAnswer, но c.freeze == True, а для других freeze == False возможный результат может быть:
[e, a, c, f, b, d]
Таким образом, элемент с индексом 2 все еще находится на своем месте.
Каков наилучший алгоритм для его достижения?
Заранее спасибо:)
Другое решение:
# memorize position of fixed elements
fixed = [(pos, item) for (pos,item) in enumerate(items) if item.freeze]
# shuffle list
random.shuffle(items)
# swap fixed elements back to their original position
for pos, item in fixed:
index = items.index(item)
items[pos], items[index] = items[index], items[pos]
Одно решение:
def fixed_shuffle(lst):
unfrozen_indices, unfrozen_subset = zip(*[(i, e) for i, e in enumerate(lst)
if not e.freeze])
unfrozen_indices = list(unfrozen_indices)
random.shuffle(unfrozen_indices)
for i, e in zip(unfrozen_indices, unfrozen_subset):
lst[i] = e
ПРИМЕЧАНИЕ. Если lst является массив numpy вместо обычного списка, это может быть немного проще:
def fixed_shuffle_numpy(lst):
unfrozen_indices = [i for i, e in enumerate(lst) if not e.freeze]
unfrozen_set = lst[unfrozen_indices]
random.shuffle(unfrozen_set)
lst[unfrozen_indices] = unfrozen_set
Пример его использования:
class CAnswer:
def __init__(self, x, freeze=False):
self.x = x
self.freeze = freeze
def __cmp__(self, other):
return self.x.__cmp__(other.x)
def __repr__(self):
return "<CAnswer: %s>" % self.x
lst = [CAnswer(3), CAnswer(2), CAnswer(0, True), CAnswer(1), CAnswer(5),
CAnswer(9, True), CAnswer(4)]
fixed_shuffle(lst)
В линейном времени постоянное пространство с использованием random.shuffle() source:
from random import random
def shuffle_with_freeze(x):
for i in reversed(xrange(1, len(x))):
if x[i].freeze: continue # fixed
# pick an element in x[:i+1] with which to exchange x[i]
j = int(random() * (i+1))
if x[j].freeze: continue #NOTE: it might make it less random
x[i], x[j] = x[j], x[i] # swap
Overengineered solution: создайте класс-оболочку, содержащий индексы незавернутых элементов и эмулируя список, и убедитесь, что сеттер записывает в исходный список:
class IndexedFilterList:
def __init__(self, originalList, filterFunc):
self.originalList = originalList
self.indexes = [i for i, x in enumerate(originalList) if filterFunc(x)]
def __len__(self):
return len(self.indexes)
def __getitem__(self, i):
return self.originalList[self.indexes[i]]
def __setitem__(self, i, value):
self.originalList[self.indexes[i]] = value
И вызов:
random.shuffle(IndexedFilterList(mylist, lambda c: not c.freeze))
Используйте тот факт, что список быстро удаляется и вставляет:
См. fooobar.com/info/348548/... для более общего решения.
Это будет использовать операции на месте с издержками памяти, которые зависят от количества фиксированных элементов в списке. Линейный по времени. Возможная реализация 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>]
"""
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.
"""
predicate = bool if predicate is None else predicate
fixed_subset = [(i, e) for i, e in enumerate(lst) if predicate(e)]
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()