有序集合了完整的圖形

Question

問題尋找頂點：對於有序集中完全圖的邊緣電子商務，給定邊EI，找到邊緣的頂點（V，W）_Ei。

注意：這很可能不是一個問題，具體到圖論，雖然它被選爲僅表達熟悉的，因爲這個問題。對引入的任何不正確的符號抱歉。

假設從由頂點1，2，3，4，5的一個完全圖K5構造，我們有圖形的邊緣的一組有序的E，共計10層的邊緣。集合E是衆所周知的總是命令如下：

榮=（0 < v < N時，V<瓦特= < N）

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) 

對於任何給定EI，我們現在必須找到頂點（v，w）_Ei單獨使用我。例如，給定6，我們應該獲得（2,4）。

更新： 另外，表示這個問題也許簡單的方法是：

n = 5 
i = 0 

for v = 1 to n - 1 
    for w = v + 1 to n 
     i++ 
     print "E" + i + " = " + v + ", " w 


print "E6 = " + findV(6) + ", " + findW(6) 

這是如何完成的？

Answer 1

爲了解決封閉形式的問題，我們需要的公式第一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) 

Answer 2

好了，簡單的方法是遍歷和減去對應的第一個頂點值，（在python）如下：

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的中等值，如果性能很重要，則可能需要考慮預先計算的查找表。

Answer 3

讓我重申，我認爲你的要求，這樣，如果這完全是題外話，你可以讓我知道了一個問題：

給定一個整數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，但仍然小於8。然而，加k - 3 = 2會給我們九個，這個數字大於八，所以我們停下來。我們增加了兩個數字加在一起，所以第一個數字必須是3

一旦我們知道了第一個數字是什麼，你可以很輕鬆地獲得第二個數字。當進行獲取第一個數字的步驟時，我們基本上列出了第一個數字變化對的索引。例如，在我們上面的例子中，我們有0,4,7系列。給它們中的每一個增加一個給出1，5，8，這實際上是分別以數字1,2和3開始的第一對。一旦你知道第一個數字是什麼，你也知道與那個數字的配對是從哪裏開始的，所以你可以從那個位置中減去你的數字的索引。這會告訴你一個零索引，你從這個元素中取得了多少個步驟。此外，你知道這是什麼第一個元素的第二值，因爲它是一加的第一個元素，所以你可以說，第二個值由第一個數字定，加一加的步數的指數超出第一對以給定的數字開始。在我們的例子中，因爲我們看索引8，並且我們知道以3開始的第一對在位置8，所以我們得到第二個數字是3 + 1 + 0 = 4，並且我們的對是（3,4） 。

這種算法實際上是非常快的。給定任意k，該算法最多需要k個步驟才能完成，因此以O（k）運行。將其與掃描所有內容的幼稚方法相比較，這需要O（k ）。

Answer 4

爲了讓我的生活更輕鬆，我將以你的問題爲基礎進行基於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被容易給出五：

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