Python：无序排列列表，但保持某些元素冻结

Question

我有这样一个问题：

有一个类CAnswer的元素列表（无需描述该类），我需要对其进行无序处理，但有一个约束条件-列表中的某些元素将CAnswer.freeze设置为True，这些元素不能被无序排列，而是保留在其原始位置。比如说，对于给定的列表：

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

其中所有元素都是CAnswer的实例，但是c.freeze == True，对于其他元素{}，可能的结果是：

^{pr2}$

所以索引为2的元素仍然在它的位置上。在

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

提前感谢：）

Answer 1

一种解决方案：

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 array而不是一个常规列表，则这可能会更简单一些：

^{pr2}$

其用法示例：

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

Answer 3

在线性时间中，常数空间使用^{}：

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