15

我有这样一个问题：

有一个类的元素列表CAnswer（无需描述类），我需要对其进行洗牌，但有一个限制 - 列表中的某些元素已CAnswer.freeze设置为True，并且这些元素不得洗牌，但仍保留在其原来的职位。因此，假设对于给定的列表：

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

如果所有元素都是CAnswer, but的实例c.freeze == True，并且对于 others freeze == False，可能的结果可能是：

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

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

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

先感谢您 ：）

4

5 回答 5

14

另一种解决方案：

# 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]
于 2012-09-02T17:18:48.163 回答
11

一种解决方案：

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)
于 2012-09-02T17:16:04.677 回答
9

在线性时间，常数空间使用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
于 2012-09-02T18:13:45.773 回答
1

过度设计的解决方案：创建一个包装类，其中包含未冻结元素的索引并模拟一个列表，并确保 setter 写入原始列表：

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))
于 2012-09-03T00:50:32.363 回答
1

使用列表具有快速删除和插入的事实：

  • 枚举固定元素并复制它们及其索引
  • 从列表中删除固定元素
  • 洗牌剩余的子集
  • 将固定元素放回

有关更通用的解决方案，请参阅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()
于 2014-08-10T13:34:40.260 回答