1

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

例如[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

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

所以简而言之，我想给我的函数一些要生成的排列，并且该函数应该给我那个排列数量，其中没有一个元素比其他元素出现在同一个位置上（一次，如果所有元素都出现一次，两次，如果都出现两次，等等）。

4

2 回答 2

2

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

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

打乱行比打乱列容易得多，所以我们将打乱行，然后进行转置，然后再次打乱行。这是 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)]

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

好处是这可以保证工作，并且始终如一O(n^2)，因为它不使用拒绝采样或回溯。

现在让我们解决其中的情况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], where n = len(players)。

于 2020-02-05T01:16:17.137 回答
0

如果运行时不是那么重要，我会采用惰性方式并生成所有可能的排列（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)
于 2020-02-04T19:28:52.753 回答