Алгоритм получения комбинаций за меньшее количество итераций - PullRequest
0 голосов
/ 13 мая 2019

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

A, B, C, D, E, F, G - набор узлов в приведенном ниже примере

enter image description here

Критерии:

Чтобы получить список элементов.
1. Не должно быть никаких повторяющихся узлов вЭто.например, там может быть AB, там не должно быть BA 2. Там не должно быть там диагонального элемента, например .. AA, BB ...

Однажды после выполнения логики мы получим все цветные (не черные)./ серого цвета) AB, AC, AD, AE, AF, AG, BC, BD, BE, BF, BG, CD, CE, CF, CG, DE, DF, DG, EF, EG, FG

Чтобы получить группу элементов в итерации Элементы должны быть сгруппированы для итерации в соответствии с приведенными ниже правилами

1-я итерация 1. Выберите элемент,Скажем, AB 2. Элемент, который будет выбран, не должен иметь A или B.Следовательно, CD можно выбрать.3. После выполнения указанных выше 2 шагов мы получим элементы для 1-й итерации

. В конце 1-й итерации мы бы собрали AB, CD, EF

Теперь повторите шаги с 1 по 3, чтобы получить элементы для 2-й итерации

В конце 2-й итерации мы бы собрали AC, BD, EG

Как и числоитерации, чтобы получить элементы для каждой итерации.

Вопрос: Поскольку ожидаемых элементов будет около 100, мне интересно, есть ли лучший способ уменьшить количествоитераций.Я надеюсь, что не будет пути.Но поскольку у нас есть эксперты по алгоритмам, мне нужен совет.

1 Ответ

2 голосов
/ 13 мая 2019

Вы можете использовать алгоритм кругового турнира

Поместите элементы в два ряда (с пустым местом, если число нечетное), здесь я сделал пары для вашего примера AB / CD / EF

A  C  E  G     
B  D  F  .
pairs  AB CD EF

Исправьте первый элемент (A) и на каждом шаге вращайте другие предметы циклически (порядок отличается от вашего). Наконец, вы получите N-1 наборов N/2 пар

A  B  C  E
D  F  G  .  
pairs  AD BF CG
and so on
A  D  B  C 
F  G  E  .  

A  F  D  B 
G  E  C  .  

A  G  F  D  
E  C  B  .  

A  E  G  F  
C  B  D  .  
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...