Фильтровать сгенерированные перестановки в python - PullRequest
Новая
       39

Фильтровать сгенерированные перестановки в python

1 голос
/ 04 февраля 2020

Я хочу генерировать перестановки элементов в списке, но сохраняю набор, в котором каждый элемент находится на каждой позиции только один раз.

Например, [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

, но я не знаю, как завершить sh вторую функцию.

Короче говоря, я хочу дать моей функции несколько перестановок, которые нужно сгенерировать, и функция должна дать мне то количество перестановок, при котором ни один элемент не окажется в той же позиции больше, чем другие (один раз, если все появляются там один раз, дважды, если все появляются там дважды, et c).

Ответы [ 2 ]

2 голосов
/ 05 февраля 2020

Давайте начнем с решения случая генерации n или меньше строк в первую очередь. В этом случае ваш вывод должен быть латинским прямоугольником или латинским квадратом . Их легко создать: начните с построения латинского квадрата, перемешайте строки, перемешайте столбцы, а затем сохраните только первые 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)]

Обратите внимание, что этот алгоритм не может генерировать все возможные латинские квадраты; по построению строки представляют собой циклические c перестановки друг друга, поэтому вы не получите латинские квадраты в других классах эквивалентности . Я предполагаю, что это нормально, поскольку генерация равномерного распределения вероятностей по всем возможным выходным данным не является одним из требований вопроса.

Преимущество состоит в том, что это гарантированно сработает, и последовательно в O(n^2) времени, потому что он не использует выборку отклонения или 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).

0 голосов
/ 04 февраля 2020

Если время выполнения не так важно, я бы go выбрал ленивый способ и сгенерировал бы все возможные перестановки (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)
...