Нахождение вершин в упорядоченном множестве полного графа

Для решения задачи в закрытой форме нам понадобится формула суммы первых k чисел: 1 + 2 + ... + k = (k + 1) * k / 2. Это дает нам сопоставление ребра (i, j) с индексом ребра:

from math import ceil, sqrt

def edge_to_index((i, j)):
    return n * (i - 1) + j - i * (i + 1) / 2

Мы можем вывести обратное отображение:

def index_to_edge(k, n):
    b = 1.0 - 2 * n
    i = int(ceil((-b - sqrt(b**2 - 8 * k)) / 2))
    j = k - n * (i - 1) + i * (i + 1) / 2
    return (i, j)

Тест:

n = 5

print "Edge to index and index to edge:"
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        k = edge_to_index((i, j))
        print (i, j), "->", k, "->", index_to_edge(k, n)

Выход:

Edge to index and index to edge:
(1, 2) -> 1 -> (1, 2)
(1, 3) -> 2 -> (1, 3)
(1, 4) -> 3 -> (1, 4)
(1, 5) -> 4 -> (1, 5)
(2, 3) -> 5 -> (2, 3)
(2, 4) -> 6 -> (2, 4)
(2, 5) -> 7 -> (2, 5)
(3, 4) -> 8 -> (3, 4)
(3, 5) -> 9 -> (3, 5)
(4, 5) -> 10 -> (4, 5)

Позвольте мне переформулировать вопрос, который, я думаю, вы задаете, чтобы, если он совсем не по теме, вы могли сообщить мне:

Для целого числа k и ряда (1, 2), (1, 3), ..., (1, k), (2, 3), (2, 4), ..., (2, k) , (3, 4), ..., (k - 1, k) и индекс n возвращают значение n-го члена этого ряда.

Вот простой алгоритм решения этой проблемы, который, вероятно, не является асимптотически оптимальным. Обратите внимание, что первая (k - 1) пара начинается с 1, следующая (k - 2) начинается с 2, следующая (k - 3) с 3 и т. д. Чтобы определить значение первого элемента в пары, вы можете продолжать складывать эти числа (k - 1) + (k - 2) + ..., пока не получите значение, которое больше или равно вашему индексу. Количество раз, которое вы могли бы сделать это, плюс один, дает вам ваше первое число:

E1 = (1, 2)
E2 = (1, 3)
E3 = (1, 4)
E4 = (1, 5)
E5 = (2, 3)
E6 = (2, 4)
E7 = (2, 5)
E8 = (3, 4)
E9 = (3, 5)
E10 = (4, 5)

Здесь k = 5. Чтобы найти первое число члена 8, мы сначала добавляем k - 1 = 4, что меньше восьми. Затем мы добавляем k - 2 = 3, чтобы получить 7, что все еще меньше восьми. Однако добавление k - 3 = 2 даст нам девять, что больше восьми, и поэтому мы останавливаемся. Мы сложили два числа вместе, поэтому первое число должно быть 3.

Как только мы узнаем, что такое первое число, вы можете довольно легко получить второе число. Выполняя шаг для получения первого числа, мы, по сути, перечисляем индексы пар, в которых изменяется первое число. Например, в приведенном выше случае у нас были ряды 0, 4, 7. Добавление одного к каждому из них дает 1, 5, 8, которые действительно являются первыми парами, начинающимися с чисел 1, 2 и 3 соответственно. . Как только вы узнаете, что такое первое число, вы также узнаете, где начинаются пары с этим числом, и поэтому вы можете вычесть индекс вашего числа из этой позиции. Это говорит вам с нулевым индексом, сколько шагов вы сделали вперед от этого элемента. Более того, вы знаете, каково второе значение этого первого элемента, потому что это единица плюс первый элемент, и поэтому вы можете сказать, что второе значение задается первым числом, плюс единица, плюс количество шагов, за пределами вашего индекса первая пара, начинающаяся с заданного числа. В нашем случае, поскольку мы смотрим на индекс 8 и знаем, что первая пара, начинающаяся с тройки, находится на позиции 8, мы получаем, что второе число равно 3 + 1 + 0 = 4, а наша пара — (3, 4) .

Этот алгоритм на самом деле довольно быстрый. Для любого k этот алгоритм выполняет не более k шагов, поэтому выполняется за O(k). Сравните это с наивным подходом сканирования всего, что занимает O(k²).

Чтобы облегчить себе жизнь, я буду вычислять на основе 0, а не 1, как в вашем вопросе.

Сначала мы выводим формулу для индекса терма (v,v+1) (первого, начинающегося с v). Это просто арифметическая сумма n-1 + n-2 + ... + n-v, которая равна v(2n-v-1)/2.

Итак, чтобы найти v по индексу i, просто решите уравнение v(2n-v-1)/2 <= i для наибольшего интеграла v. Двоичный поиск будет работать хорошо, или вы можете решить квадратное число, используя квадратичную формулу, и округлить в меньшую сторону (возможно, придется подумать, сработает ли это).

Найти W легко, учитывая V:

findW(i):
  v = findV(i)
  i_v = v(2n-v-1)/2
  return i - i_v + 1

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

def unpackindex(i,n):
  for v in range(1,n):
    if v+i<=n: return (v,v+i)
    i-= n-v
  raise IndexError("bad index")

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