Python: перетасовка списка, но сохранение некоторых элементов замороженных

У меня такая проблема:

Существует список элементов класса 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 

Переработанное решение: создайте класс-оболочку, содержащий индексы незакрепленных элементов и эмулируя список, и убедитесь, что сеттер записывает в исходный список:

 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)) 

Используйте тот факт, что список быстро удаляется и вставляет:

  • перечислить фиксированные элементы и скопировать их и их индекс
  • удалить фиксированные элементы из списка
  • оставшийся субэлемент
  • вернуть неподвижные элементы в

См. https://stackoverflow.com/a/25233037/3449962 для более общего решения.

Это будет использовать операции на месте с издержками памяти, которые зависят от количества фиксированных элементов в списке. Линейный по времени. Возможная реализация 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()