16

リストをランダムにシャッフルしたいのですが、1つの条件があります。シャッフル後、要素が同じ元の位置になることはありません。

リストのためにPythonでそのようなことをする1行の方法はありますか？

例：

list_ex = [1,2,3]

次のシャッフルされたリストのそれぞれは、シャッフル後にサンプリングされる確率が同じである必要があります。

list_ex_shuffled = [2,3,1]
list_ex_shuffled = [3,1,2]

ただし、順列[1,2,3]、[1,3,2]、[2,1,3]、および[3,2,1]は、すべて要素の位置の1つを繰り返すため、許可されていません。

注：list_exの各要素は一意のIDです。同じ要素の繰り返しは許可されていません。

何か案は？ありがとう！

4

6 に答える 6

8

ループでランダム化し、条件が満たされるまで結果を拒否し続けます。

import random

def shuffle_list(some_list):
    randomized_list = some_list[:]
    while True:
        random.shuffle(randomized_list)
        for a, b in zip(some_list, randomized_list):
            if a == b:
                break
        else:
            return randomized_list
于 2013-03-19T23:17:55.570 に答える
7

私はそのようなシャッフルを「不動点のない順列」と表現します。それらは混乱としても知られています。

ランダム順列が混乱である確率は約1/e（証明するのが楽しい）です。これは、リストが長くても当てはまります。したがって、ランダムな混乱を与えるための明白なアルゴリズムは、カードを通常どおりシャッフルし、混乱が生じるまでシャッフルを続けることです。必要なシャッフルの予想回数は約3回で、10回以上シャッフルしなければならないことはめったにありません。

(1-1/e)**11 < 1%

パーティーにn人がいて、それぞれが傘を持ってきたとします。パーティーの最後に、一人一人がバスケットからランダムに傘を取り出します。誰も自分の傘を持っていない確率はどれくらいですか？

于 2013-03-20T00:20:07.843 に答える
4

可能なすべての有効なシャッフルを生成できます。

>>> list_ex = [1,2,3]
>>> import itertools

>>> list(itertools.ifilter(lambda p: not any(i1==i2 for i1,i2 in zip(list_ex, p)),
...                        itertools.permutations(list_ex, len(list_ex))))
[(2, 3, 1), (3, 1, 2)]

他のシーケンスの場合：

>>> list_ex = [7,8,9,0]
>>> list(itertools.ifilter(lambda p: not any(i1==i2 for i1,i2 in zip(list_ex, p)),
...                        itertools.permutations(list_ex, len(list_ex))))
[(8, 7, 0, 9), (8, 9, 0, 7), (8, 0, 7, 9), (9, 7, 0, 8), (9, 0, 7, 8), (9, 0, 8, 7), (0, 7, 8, 9), (0, 9, 7, 8), (0, 9, 8, 7)]

1つの結果だけが必要な場合は、イテレータを短絡することで、これをもう少し効率的にすることもできます。

>>> list_ex = [1,2,3]
>>> i = itertools.ifilter(lambda p: not any(i1==i2 for i1,i2 in zip(list_ex, p)),
...                       itertools.permutations(list_ex, len(list_ex)))
>>> next(i)
(2, 3, 1)

しかし、それはランダムな選択ではありません。それらすべてを生成し、実際のランダムな結果になるように1つを選択する必要があります。

>>> list_ex = [1,2,3]
>>> i = itertools.ifilter(lambda p: not any(i1==i2 for i1,i2 in zip(list_ex, p)),
...                       itertools.permutations(list_ex, len(list_ex)))
>>> import random
>>> random.choice(list(i))
(2, 3, 1)
于 2013-03-19T23:01:08.120 に答える
1

これについての別の見方があります。ニーズに応じて、いずれかのソリューションを選択できます。これはワンライナーではありませんが、要素自体ではなく要素のインデックスをシャッフルします。したがって、元のリストには、重複する値または比較できないタイプの値が含まれている可能性があり、比較するのに費用がかかる可能性があります。

#! /usr/bin/env python
import random

def shuffled_values(data):
    list_length = len(data)
    candidate = range(list_length)
    while True:
        random.shuffle(candidate)
        if not any(i==j for i,j in zip(candidate, range(list_length))):
            yield [data[i] for i in candidate]

list_ex = [1, 2, 3]
list_gen = shuffled_values(list_ex)
for i in range(0, 10):
    print list_gen.next()

これは与える：

[2, 3, 1]
[3, 1, 2]
[3, 1, 2]
[2, 3, 1]
[3, 1, 2]
[3, 1, 2]
[2, 3, 1]
[2, 3, 1]
[3, 1, 2]
[2, 3, 1]

の場合、このメソッドlist_exは何度[2, 2, 2]も降伏[2, 2, 2]し続けます。他の解決策はあなたに空のリストを与えるでしょう。この場合、何が欲しいのかわかりません。

于 2013-03-19T23:39:01.510 に答える
1

Knuth-Durstenfeldを使用してリストをシャッフルします。シャッフルプロセス中に元の位置にあることが判明した場合、新しいシャッフルプロセスが最初から開始され、適切な配置に戻ります。このアルゴリズムの時間計算量は、最小の定数項です。

def _random_derangement(x: list, randint: Callable[[int, int], int]) -> None:
    '''
        Random derangement list x in place, and return None.
        An element can never be in the same original position after the shuffle. provides uniform distribution over permutations.
        The formal parameter randint requires a callable object such as rand_int(b, a) that generates a random integer within the specified closed interval.
    '''

    from collections import namedtuple

    sequence_type = namedtuple('sequence_type', ('sequence_number', 'elem'))

    x_length = len(x)
    if x_length > 1:
        for i in range(x_length):
            x[i] = sequence_type(sequence_number = i, elem = x[i])
    
        end_label = x_length - 1
        while True:
            for i in range(end_label, 0, -1):
                random_location = randint(i, 0)
                if x[random_location].sequence_number != i:
                    x[i], x[random_location] = x[random_location], x[i]
                else:
                    break
            else:
                if x[0].sequence_number != 0: break
    
        for i in range(x_length):
            x[i] = x[i].elem

complete_shuffle

于 2020-11-06T22:41:58.367 に答える
0

これが別のアルゴリズムです。カードをランダムに取ります。i番目のカードがカードiの場合は、元に戻して再試行してください。唯一の問題は、最後のカードに到達したときに、それが不要なカードである場合はどうなるかということです。他の1つと交換してください。

これは公平だと思います（均一にランダム）。

import random

def permutation_without_fixed_points(n):
    if n == 1:
        raise ArgumentError, "n must be greater than 1"

    result = []
    remaining = range(n)

    i = 0
    while remaining:
        if remaining == [n-1]:
            break

        x = i
        while x == i:
            j = random.randrange(len(remaining))
            x = remaining[j]

        remaining.pop(j)
        result.append(x)

        i += 1

    if remaining == [n-1]:
        j = random.randrange(n-1)
        result.append(result[j])
        result[j] = n

    return result
于 2013-03-20T00:43:17.030 に答える