Python: lista mischiare, ma mantenendo alcuni elementi congelati

Question

Sono un problema:

C'è un elenco di elementi di classe CAnswer (non c'è bisogno di descrivere la classe), e ho bisogno di mischiare, ma con un vincolo: alcuni elementi dell'elenco hanno CAnswer.freeze impostato su True e tali elementi non devono essere mescolati, ma rimangono nelle loro posizioni originali. Quindi, diciamo, per una data lista:

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

dove tutti gli elementi sono istanze di CAnswer, ma c.freeze == True, e per gli altri freeze == False, il possibile risultato potrebbe essere:

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

Così elemento con indice 2 è ancora sulla sua posizione.

Qual è il miglior algoritmo per raggiungerlo?

Grazie in anticipo :)

Answer 1

Un'altra soluzione:

# 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 soluzione:

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: Se lst è un numpy array invece di una lista regolare, questo può essere un po 'più semplice:

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 esempio del suo utilizzo:

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

Nel tempo lineare, spazio costante utilizzando 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

soluzione overengineered: creare una classe involucro che contiene gli indici degli elementi unfreezed e emula un elenco e fanno che il setter scrive alla lista originale:

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 

E non chiamate:

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

Answer 5

Utilizzare il fatto che l'elenco è rapidamente rimuovere e inserire:

• enumerare fisso elementi e copiare loro e il loro indice di
• di eliminazione elementi fissi da elenco
• riordino rimanente sottoinsieme
• put fisso elementi indietro nel

Vedi https://stackoverflow.com/a/25233037/3449962 per una soluzione più generale.

Questo utilizzerà le operazioni sul posto con sovraccarico della memoria che dipende dal numero di elementi fissi nell'elenco. Lineare nel tempo.Una possibile implementazione di 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()