Получить уникальные группы из списка - PullRequest
Новая
       43

Получить уникальные группы из списка

0 голосов
/ 20 апреля 2020

Я пытаюсь создать алгоритм для создания уникальных групп длины = N из списка L со значениями len (L).

РЕДАКТИРОВАТЬ: уникальная группа - это та, где любая из значения никогда не были с какими-либо значениями в группе ранее.

РЕДАКТИРОВАТЬ: Поэтому, если бы вместо значений у нас были люди, любой в группе всегда должен встречать только новых людей в новая группа.

Скажем, у нас есть список L и попробуйте найти уникальные группы из 4: 

L = [1,2,3,4,5,6,7,8]
N = 4

unique_groups = [[1,2,3,4], [5,6,7,8]]
len(unique_groups) = 2

Итак, у нас есть 8 значений и 2 уникальные группы, любая новая группа будет содержать по крайней мере одно значение, которое содержится в предыдущем, например, [1,2,3,5] или [1,3,5,7] содержат по крайней мере два значения ранее, поэтому эти группы не являются уникальными.

Где len (L) = 12, у нас есть 3 разные группы, в то время как len (L)> = 16 дает нам больше возможностей: 

L = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
N = 4

unique_groups = [[1,2,3,4], [5,6,7,8], [9,10,11,12], [13,14,15,16], [1,5,9,13], [2,3,7,12] ...]
len(unique_groups) = ?

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

def findsubsets(s, n):
    return list(itertools.combinations(s, n))


s = [1,2,3,4,5,6,7,8]


sets = findsubsets(s,4)

sets_unique = []


def compare_sets(set1, set2):
    init_eq = 0
    for s1 in set1:
        if s1 in set2 and init_eq > 0:
            return False
        elif s1 in set2 and init_eq < 1:
            init_eq += 1
        else:
            continue
    return True


for s in sets:
    start_point = sets.index(s)
    print(start_point)
    for i in range(start_point + 1, len(sets) + 1):
        set2 = sets[i]
        if compare_sets(s, set2):
            print(s, set2)
            sets_unique.append(set2)

print(sets_unique)

РЕДАКТИРОВАНИЕ 2: Реальная проблема заключается в том, чтобы сопоставить сотрудников в группе из N, поэтому в этих группах никогда не бывает двух одинаковых людей. Каждый человек должен встречаться только с новыми людьми.

1 Ответ

1 голос
/ 20 апреля 2020

Ваш вопрос об обновлении теперь вполне понятен; спасибо.

Эта проблема изоморфна c множествам точек и линий в проективной плоскости . Вы пытаетесь построить как можно больше линий, используя N точек на каждой линии. Посмотрите подраздел «Конечный пример» для визуализации процесса и «Построение векторного пространства» для формального алгоритма.

Чтобы дать вам представление, вы начнете с произвольно выбранной точки 1 , Составляйте множества (коллинеарные точки), добавляя (удобно) последовательные непересекающиеся тройки: 

1  2  3  4
1  5  6  7
1  8  9 10
1 11 12 13
...

Это дает вам все группы, содержащие точку 1. Теперь перейдем к математически интересной части: как сшить точки 2 и выше будет определять projective plane; решение здесь не является уникальным. Один стандартный алгоритм ищет решение homeomorphi c, жадный алгоритм: в каждой точке выбора выберите точку с наименьшим номером, которая является допустимой для текущего открытого слота. Это даст нам 

2  5  8 11
2  6  9 12
2  7 10 13
...
3  5  9 13
3  6 10 11

и так далее

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

Имея дело с этим с точки зрения проективных плоскостей, вы начинаете с аффинно и выводите плоскости оттуда. Специально проверьте три свойства аффинной плоскости

Дополнительные ссылки: http://www.mathpuzzle.com/MAA/47-Fano/mathgames_05_30_06.html

Достаточно ли этого для игры на данный момент?

...