Python: lista arrastrando los pies, pero manteniendo algunos elementos congelados

Question

Tengo un problema:

Hay una lista de elementos de la clase CAnswer (sin necesidad de describir la clase), y necesito a barajar, pero con una restricción: algunos elementos de la lista tienen CAnswer.freeze establecido en True, y esos elementos no se deben barajar, sino que deben permanecer en sus posiciones originales. Así que, digamos, de una lista dada:

[a, b, c, d, e, f] 

donde todos los elementos son instancias de CAnswer, pero c.freeze == True, y para otros freeze == False, el posible resultado podría ser:

[e, a, c, f, b, d] 

Así elemento con el índice 2 todavía está en su posición.

¿Cuál es el mejor algoritmo para lograrlo?

gracias de antemano :)

Answer 1

Otra solución:

# 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] 

Answer 2

Una solución:

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 

NOTA: Si lst es una numpy array lugar de una lista regular, esto puede ser un poco más simple:

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 

Un ejemplo de su uso:

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) 

Answer 3

en el tiempo lineal, el espacio constante utilizando 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 

Answer 4

solución overengineered: crear una clase contenedora que contiene los índices de los elementos unfreezed y emula una lista, y crea Asegúrese de que el colocador escribe a la lista original:

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 

Y llama:

random.shuffle(IndexedFilterList(mylist, lambda c: not c.freeze)) 

Answer 5

uso del hecho de que una lista se retire rápido e insertar:

• elementos Enumerar fija y copiarlos y su índice
• elementos fijos de borrado de la lista
• aleatoria restante subconjunto
• put elementos fijos de vuelta en

Ver https://stackoverflow.com/a/25233037/3449962 para una solución más general.

Esto utilizará operaciones in situ con sobrecarga de memoria que depende de la cantidad de elementos fijos en la lista. Lineal en el tiempoUna posible implementación de 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()