高效地確定電子表格中行之間的關係

Question

這是我剛剛遇到的一個問題，或者更確切地說，它是捕獲核心問題的簡化。

想象一下，我有一個電子表格，其中包含許多列，每個列都標有標籤，還有一些行。

我想確定一列中的值何時可以從另一列中的值推斷出來。例如，我們可能會發現每次在列a中出現'1'時，總是在列d中出現'5'，但是隻要在列a中出現'2'，3總會出現在列d。我們觀察到列a中的值可靠地預測了列c中的值。

目標是確定列之間的所有這些關係。 （a，b），（a，c），（a，d）...（b，c），（b，d）的列對開始列表， ... 等等。我們稱這些爲「合格」列表。

對於這些配對中的每一對，我們都會跟蹤配對中第一對的值和第二對中的對應值。如果我們注意到我們看到第一對貨幣的價值相同，而第二個貨幣對的價值不同，那麼這對貨物不再符合條件。

無論在這個過程結束時剩下的是一組有效的關係。

不幸的是，隨着列數的增加，這很快就變得不切實際，因爲我們必須存儲的數據量是按列的平方數量的順序排列的。

任何人都可以想到一個有效的方法來做到這一點？

Answer 1

我不認爲你可以改進n列的O（n^2）：考慮任何一對之間不存在關係的情況。發現這一點的唯一方法是測試所有對，即O（n^2）。

Answer 2

我懷疑你最好是建立關係，而不是縮小關係。

您可能必須存儲n^2條信息，其中有n列。例如，如果一個列從不重複（即它的值在每一行上不同），那麼該列預測所有其他列。如果每一列都是這樣的，那麼每一列都可以預測其他列。你可以使用一個二維表，pred表示，按列數索引，pred（a，b）如果是預測b，則爲true。 pred（a，b）可以具有3個值中的任何一個：真，假和未知。

預測關係是傳遞性的，即如果預測b和b預測c然後a預測c。如果行數很大，以便檢查一行是否預測另一行很昂貴，那麼可能需要使用可傳遞性來填寫可能的內容：如果您剛剛計算pred（a，b）爲真，並且您有已經爲每個x計算了pred（b，x），那麼可以爲pred（b，y）爲真的每個y設置pred（a，y）true。要填充pred（a ,.），您可以從a構建一對臨時數組（值，行索引），然後按值排序;這使您可以輕鬆訪問a不變的索引集。如果這些集合中的每一個都是單例，那麼pred（a，b）對於每個b都是真的;否則檢查是否預測b（如果它不是已知的），你需要檢查b在每個索引集上（不止一個成員）是恆定的，其中a是常數。如果pred（a，b）爲真，且pred（b，a）爲真，那麼對於每個c，pred（a，c）當且僅當pred（b，c） ;因此在這種情況下，如果您已經填寫pred（b ,.），您可以通過複製填寫所有pred（a ,.）。