在 python 中过滤生成的排列

Question

我想生成列表中元素的排列，但只保留一个集合，其中每个元素只在每个位置出现一次。

例如 [1, 2, 3, 4, 5, 6] 可以是一个用户列表，我想要 3 个排列。一个好的集合是：

[1,2,3,5,4,6]
[2,1,4,6,5,3]
[3,4,5,1,6,2]

但是，不能在上面添加，例如，[1,3,2,6,5,4]，因为有两个排列，其中 1 两次出现在第一个位置，5 也会两次出现在第 5 个位置，但是其他元素只出现在这些位置一次。

到目前为止我的代码是：

# this simply generates a number of permutations specified by number_of_samples

def generate_perms(player_list, number_of_samples):
    myset = set()
    while len(myset) < number_of_samples:
         random.shuffle(player_list)
         myset.add(tuple(player_list))
    return [list(x) for x in myset]

# And this is my function that takes the stratified samples for permutations.
def generate_stratified_perms(player_list, number_of_samples):
    user_idx_dict = {}
    i = 0

    while(i < number_of_samples):
        perm = generate_perms(player_list, 1)
        for elem in perm:
            if not user_idx_dict[elem]:
                user_idx_dict[elem] = [perm.index(elem)]
            else:
                user_idx_dict[elem] += [perm.index(elem)]
        [...]
    return total_perms

但我不知道如何完成第二个功能。

所以简而言之，我想为我的函数提供一些要生成的排列，并且该函数应该为我提供这些排列的数量，其中没有元素比其他元素更多地出现在相同的位置（一次，如果全部出现一次，两次，如果全部出现两次，等等）。

Answer 1

如果运行时不是那么重要，我会采用懒惰的方式并生成所有可能的排列（itertools 可以为您完成），然后过滤掉所有不符合您要求的排列。

这是一种方法。

import itertools

def permuts (l, n):
    all_permuts = list(itertools.permutations(l))
    picked = []

    for a in all_permuts:
        valid = True
        for p in picked:
            for i in range(len(a)):
                if a[i] == p[i]:
                    valid = False
                    break

        if valid:
            picked.append (a)

        if len(picked) >= n:
            break

    print (picked)


permuts ([1,2,3,4,5,6], 3)

Answer 2

让我们首先解决生成 n 或更少行的情况。在这种情况下，您的输出必须是 Latin rectangle or a Latin square。这些很容易生成：首先构造一个拉丁方，打乱行，打乱列，然后只保留前 r 行。以下始终适用于构建拉丁方开始：

1 2 3 ... n
2 3 4 ... 1
3 4 5 ... 2
... ... ...
n 1 2 3 ...

打乱行比打乱列容易得多，所以我们先打乱行，然后取 transpose，然后再次打乱行。这是 Python 中的一个实现：

from random import shuffle

def latin_rectangle(n, r):
    square = [
        [1 + (i + j) % n for i in range(n)]
        for j in range(n)
    ]
    shuffle(square)
    square = list(zip(*square)) # transpose
    shuffle(square)
    return square[:r]

示例：

>>> latin_rectangle(5, 4)
[(2, 4, 3, 5, 1),
 (5, 2, 1, 3, 4),
 (1, 3, 2, 4, 5),
 (3, 5, 4, 1, 2)]

请注意，此算法无法生成所有可能的 拉丁方；通过构造，这些行是彼此的循环排列，因此您不会在其他 equivalence classes 中得到拉丁方。我假设这没问题，因为在所有可能的输出上生成统一的概率分布不是问题要求之一。

好处是这保证有效，并且在 O(n^2) 时间内始终如一，因为它不使用 rejection sampling or backtracking。

现在让我们解决 r > n 的情况，即我们需要更多行。除非r % n == 0，否则每列的每个数字的频率都不能相等，但它足够简单，可以保证每列中的频率最多相差1。生成足够的拉丁方，将它们放在一起，然后从中切出 r 行。对于额外的随机性，可以安全地打乱那些 r 行，但只能在获取切片之后。

def generate_permutations(n, r):
    rows = []
    while len(rows) < r:
        rows.extend(latin_rectangle(n, n))
    rows = rows[:r]
    shuffle(rows)
    return rows

示例：

>>> generate_permutations(5, 12)
[(4, 3, 5, 2, 1),
 (3, 4, 1, 5, 2),
 (3, 1, 2, 4, 5),
 (5, 3, 4, 1, 2),
 (5, 1, 3, 2, 4),
 (2, 5, 1, 3, 4),
 (1, 5, 2, 4, 3),
 (5, 4, 1, 3, 2),
 (3, 2, 4, 1, 5),
 (2, 1, 3, 5, 4),
 (4, 2, 3, 5, 1),
 (1, 4, 5, 2, 3)]

这使用数字 1 到 n 因为第一个列表理解中的公式 1 + (i + j) % n。如果你想使用数字 1 到 n 以外的东西，你可以把它当作一个列表（例如 players）并将列表理解的这一部分更改为 players[(i + j) % n], 其中 n = len(players).

在 python 中过滤生成的排列

Filter generated permutations in python

python

permutation

permute