Обход графа, может быть, другой тип математики?

Допустим, у вас есть набор/список/набор чисел: [1,3,7,13,21,19] (порядок не имеет значения). Допустим, по неважным причинам вы прогоняете их через функцию и получаете следующие пары: (1, 13), (1, 19), (1, 21), (3,19), (7, 3) , (7,13), (7,19), (21, 13), (21,19). Опять порядок не имеет значения. Мой вопрос касается следующей части: как мне узнать минимальное количество чисел, которые могут быть частью пары без повторения? Для этой конкретной последовательности это все шесть. Для [1,4,2] это пары (1,4), (1,2), (2,4). В этом случае любое из чисел может быть исключено, так как все они парные, но каждое из них повторяется, поэтому будет 2 (какие 2 не имеют значения). На первый взгляд это похоже на задачу обхода графа — числа — это узлы, пары — ребра. Есть ли какая-то часть математики, которая занимается этим? У меня нет проблем с написанием алгоритма обхода, мне просто интересно, есть ли решение с меньшей временной сложностью. Спасибо!


python set algorithm graph-traversal graph-algorithm
person msmedes    schedule 08.09.2018    source источник
comment
Что вы имеете в виду, говоря, что вы являетесь частью пары, не повторяясь?   -  person giusti    schedule 08.09.2018
comment
Ну разве минимум не всегда равен 0? Ты хотел сказать "максимальная сумма"?   -  person Maras    schedule 08.09.2018
comment
math: en.wikipedia.org/wiki/Combination python: комбинации импорта из itertools Также en.wikipedia.org/wiki/Combinatorics для общего поля. Просто найти количество — это простой расчет с использованием факториала.   -  person Kenny Ostrom    schedule 08.09.2018
comment
Да, я думаю, что я изменил то, что было задумано. Можно было бы написать «какая комбинация пар максимизирует количество элементов в парах» или, скорее, «какая комбинация приводит к наименьшему количеству возможных элементов, не включенных в пары». Вот что я получаю за то, что пишу вопрос за ужином.   -  person msmedes    schedule 08.09.2018
comment
вау, я совершенно неправильно понял вопрос   -  person Kenny Ostrom    schedule 08.09.2018
comment
один метод, который я думал сделать, заключался в создании всех возможных перестановок точек и поиске перестановки или перестановок с максимальным количеством представленных элементов, что в некотором роде является своего рода обходом графа.   -  person msmedes    schedule 08.09.2018

Ответы (2)


arrow_upward
0
arrow_downward

Если вы действительно намеревались найти минимальную сумму, ответ будет 0, потому что вам вообще не нужно использовать какое-либо число.

Я думаю, вы хотели написать «максимальное количество чисел».

Если я правильно понимаю вашу задачу, то похоже, что мы можем преобразовать ее в следующую задачу: дан набор из n чисел (1,..,n), на какое максимальное количество чисел я могу разделить разбиты на пары, где каждое число может встречаться только один раз.

Ответ на этот вопрос:

  • когда n = 2k f(n) = 2k для k>=0
  • когда n = 2k+1 f(n) = 2k для k>=0

Я объясню, используя индукцию.

  1. если n = 0, то мы можем использовать не более 0 чисел для создания пар.
  2. если n = 2 (множество может быть [1,2]), то мы можем использовать оба числа для создания одной пары (1,2)
  3. Предположение: если n=2k, предположим, что мы можем использовать все 2k чисел для создания 2k пар и доказать с помощью индукции, что мы можем использовать 2k+2 числа для n = 2k+2.
  4. Доказательство: если n = 2k+2, [1,2,..,k,..,2k,2k+1,2k+2], мы можем создать k пар, используя 2k чисел (из нашего предположения). без ограничения общности предположим, что наши пары равны (1,2),(3,4),..,(2k-1,2k). мы видим, что у нас остались два числа [2k+1, 2k+2], которые мы не использовали, и поэтому мы можем составить пару из двух из них, что означает, что мы использовали 2k+2 числа.

Вы можете самостоятельно доказать случай, когда n нечетно.

person Daniel Shterenberg    schedule 08.09.2018
comment
Да, как я прокомментировал выше, я испортил объяснение. Можно было бы написать «какая комбинация пар максимизирует количество элементов в парах» или, скорее, «какая комбинация приводит к наименьшему количеству возможных элементов, не включенных в пары», хотя в этом случае пары по существу неизменяемы, а «ребра» между «узлами». Я не уверен, что это все еще применимо в этом случае. - person msmedes; 08.09.2018
comment
ну если вы так сформулируете свой вопрос, то мое решение неверно. Например, допустим, у нас есть следующий набор: [1,2,3,4,5,6] со следующими ребрами: (1,2),(1,3),(1,4),(2, 4),(2,5),(2,6). В этом случае мы можем использовать не более 4 чисел (например, 1,2,3,4). - person Daniel Shterenberg; 09.09.2018
comment
Правильный. Насколько я могу судить, это по крайней мере np сложно, может быть, np завершено. У меня есть решение, которое перебирает каждую комбинацию пар (в этом конкретном примере требуется 3 пары, некоторые могут быть длиннее или короче в зависимости от длины набора входных целых чисел, которые генерируют пары), но оно медленное. Это считается комбинаторикой? Теория множества? Существует ли простая формула, относящаяся к количеству пар или элементов? Я действительно понятия не имею, где искать потенциальное решение. - person msmedes; 09.09.2018

arrow_upward
0
arrow_downward

На случай, если кому-то будет интересно в будущем, решение называется алгоритмом цветения.

person msmedes    schedule 10.09.2018