15

私はそのような問題を抱えています：

クラスの要素のリストがあり(クラスCAnswerを説明する必要はありません)、それをシャッフルする必要がありますが、1 つの制約があります。元の位置。したがって、特定のリストについて、次のようにしましょう。CAnswer.freezeTrue

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

すべての要素がCAnswer、 but c.freeze == True、およびother のインスタンスである場合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

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

注:が通常のリストではなくnumpy 配列lstである場合、これは少し単純になります。

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

過度に設計されたソリューション: 凍結されていない要素のインデックスを含み、リストをエミュレートするラッパー クラスを作成し、セッターが元のリストに書き込むことを確認します。

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 に答える