Пользовательская перестановка, Равное распределение пар

Question

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

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

список (A, B, C, D) может привести к следующему:

(A,B)
(C,D)
(B,A)
(D,C)
(A,C)
(B,D)
(C,A)
(D,B)
(A,D)
(B,C)
(D,A)
(C,B)

Обратите внимание, каждая буква используется каждые 2 пары, ибуквы часто меняются местами.

Чтобы получить перестановку, я использовал скрипт python:

perm = list(itertools.permutations(list,2))

, который дал мне 12 пар букв.

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

С 4 буквами это может бытьсделано проще, потому что (4 буквы / 2 пары) = 2. Я также хотел бы, чтобы это работало и с нечетными парами перестановок.

Например:

A, BC

A, B, C, D, E

и т. Д.

У меня естьпопробовал это несколькими способами и попытался распознать закономерности, и хотя их много, есть только много способов решить эту проблему, особенно.Также не может быть идеального ответа.

Я также пытался взять нормальную перестановку букв P (4,4) или в случае 5 букв P (5,5), и япопытался выбрать определенные перестановки, объединить их, а затем разбить их на пары.Это похоже на другой маршрут, но я не могу понять, какие пары выбрать, если я не проработаю его вручную.

Любая помощь приветствуется!Может быть, попытаться указать мне правильное направление:)

В конечном счете, я попытаюсь внедрить это в python, но мне не обязательно нужна помощь при написании кода.это больше вопрос о том, что процесс может быть.

Answer 1

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

С n объектами у нас есть n * (n-1) пар.В этих (a, b) парах:

• n имеют такие индексы, как b = (a + 1), по модулю n

• n имеют такие индексы, как b = (a + 2) по модулю n

  и т. д.

Мы можем сгенерировать первые n пар с разностью 1, затем n пар с разницей 2 ...

Для каждого различия мы генерируем индексы, добавляя разницу к индексу (по модулю n).Когда мы получаем a, который уже использовался для этой разницы, мы добавляем 1 (снова по модулю n).Таким образом, мы можем сгенерировать n пар с этой разницей.Поскольку мы «катимся» по индексам, мы уверены, что каждое значение будет появляться регулярно.

def pairs(n):
    for diff in range(1, n):
        starts_seen = set()
        index = 0
        for i in range(n):
            pair = [index]
            starts_seen.add(index)
            index = (index+diff) % n
            pair.append(index)
            yield pair
            index = (index+diff) % n
            if index in starts_seen:
                index = (index+1) % n

pairs2 = list(pair for pair in pairs(2))
print(pairs2)
# [[0, 1], [1, 0]]          

pairs3 = list(pair for pair in pairs(3))
print(pairs3)         
# [[0, 1], [2, 0], [1, 2], 
#  [0, 2], [1, 0], [2, 1]]

pairs4 = list(pair for pair in pairs(4))
print(pairs4)        
# [[0, 1], [2, 3], [1, 2], [3, 0],   <- diff = 1
#  [0, 2], [1, 3], [2, 0], [3, 1],   <- diff = 2
#  [0, 3], [2, 1], [1, 0], [3, 2]]   <- diff = 3

pairs5 = list(pair for pair in pairs(5))
print(pairs5)    
# [[0, 1], [2, 3], [4, 0], [1, 2], [3, 4],
#  [0, 2], [4, 1], [3, 0], [2, 4], [1, 3],
#  [0, 3], [1, 4], [2, 0], [3, 1], [4, 2],
#  [0, 4], [3, 2], [1, 0], [4, 3], [2, 1]]

# A check to verify that we get the right number of different pairs:
for n in range(100):
    pairs_n = set([tuple(pair) for pair in pairs(n)])
    assert len(pairs_n) == n*(n-1)
print('ok')
# ok