Python重排,使位置永远不会重复

yws3nbqq  于 2022-10-30  发布在  Python
关注(0)|答案(6)|浏览(182)

我想对一个列表进行随机洗牌,但有一个条件:在混洗之后,元素永远不会处于相同的原始位置。
在python for a list中,有没有一行的方法来实现这一点?
示例:

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]是不允许的,因为它们都重复元素位置中的一个。
注意:list_ex中的每个元素都是唯一的ID。不允许重复使用相同的元素。

lskq00tm

lskq00tm1#

在循环中进行随机化,并不断拒绝结果,直到满足您的条件:

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
enxuqcxy

enxuqcxy2#

我将这种洗牌描述为“没有固定点的排列”,它们也被称为derangements
一个随机排列是错乱的概率约为1/e(证明起来很有趣)。无论列表有多长,这都是正确的。因此,给予随机错乱的一个明显算法是正常地洗牌,并且一直洗牌,直到你出现错乱。预期的必要洗牌次数约为3次,很少你需要洗牌超过10次。

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

假设有n个人参加聚会,每个人都带了一把伞。聚会结束时,每个人都从篮子里随机拿了一把伞。没有人带自己的伞的概率是多少?

vs91vp4v

vs91vp4v3#

您可以生成所有可能的有效洗牌:

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

如果只需要一个结果,还可以通过短路迭代器来提高效率:

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

但是,这并不是一个“随机”的选择,你必须生成所有的选项,然后从中选择一个,这样才是一个真正的随机结果:

>>> 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)
1qczuiv0

1qczuiv04#

这是另一个解决方案。你可以根据自己的需要选择一个或另一个解决方案。这不是一个单行程序,而是打乱元素的索引,而不是元素本身。因此,原始列表可能有重复的值,或者无法比较的类型值,或者比较起来可能很昂贵。


# ! /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]。其他的解决方案会给予你空的列表。我不确定在这种情况下你想要什么。

lp0sw83n

lp0sw83n5#

使用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

kcugc4gi

kcugc4gi6#

这是另一个算法,随机取牌,如果你的第i张牌是第i张,把它放回去再试一次,唯一的问题是,如果你拿到最后一张牌时,它是你不想要的,那就把它和其他牌交换一下。
我认为这是公平的(均匀随机)。

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

相关问题