Python:改组列表,但保留一些元素冻结

Question

我有这样一个问题:

有一个类的元素列表CAnswer(不需要描述类),我需要对它进行洗牌,但是有一个约束 - 列表中的一些元素已经CAnswer.freeze设置为True,并且这些元素不能被洗牌,而是保留在它们的上面原始职位.所以,让我们说,对于给定的列表:

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

如果所有元素都是CAnswer,但是c.freeze == True,对于其他元素freeze == False,可能的结果可能是:

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

所以索引为2的元素仍处于其位置.

实现它的最佳算法是什么？

先感谢您 :)

Answer 1

另一种方案:

# 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

一个解决方案

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)

Answer 3

在线性时间内,恒定空间使用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