假設我有兩組項目和一個函數來檢查兩個項目的等價性（不嚴格相等，以便一個項目可能等同於多個項目另一組），我想確定是否存在一對一的對應關係，以便對每個對都成立。確定與等價函數一一對應的算法
這個問題是否有任何確定的/最佳的解決方案？
這個問題從確定兩個C聯合類型是否兼容，對於該標準需要這樣的對應關係，但是事情變得棘手，因爲工會成員可以是匿名的，所以對於一個項目的等價項目可以有多種可能性原本來自。目前我正在採用一種天真的方法，但我想知道是否有任何建立的討論/解決方案。
一種解決方案是實現一個具有兩個屬性的哈希函數：
請注意，完美的散列函數絕不會爲不等價的項目生成相同的散列值。
一旦你有一個散列函數，你可以通過散列值對列表進行排序。如果你的散列是完美的，檢查一對一的對應關係是微不足道的。如果散列函數不是完美的，當你找到n對n的對應關係時，代碼將需要回退到這些n項目的蠻力O（n^2）等價檢查。
運行時間是以下任務
所以，總體運行時間與一個完美的散列函數是O相比的O爲蠻力比較的運行時間（N^2）（NlogN）。
這種散列函數只有在OP的「等價」概念是真正的等價關係時纔有可能;但從他/她的後續評論看，這顯然不是。此外，即使它*是一個等價關係，也可能難以計算出一個有意義的散列碼;請參閱https://cstheory.stackexchange.com/questions/10702。 – ruakh
我們可以假設等價（由「≡」定義）是可傳遞的，即如果'a≡b'且'b≡c'則'a≡c'？ – Dukeling
@Dukeling在這種情況下，可悲的是，沒有。因爲類型A，B，C可以用相同的標籤聲明，並且如果A和C是完整類型但B不是，則transtive屬性被破壞。但我仍然懷疑它是否真的存在，是否有任何確定的討論呢？ –
如果它是可傳遞的，到目前爲止發佈的答案應該解決問題就好（我不知道任何「已建立的討論」）。如果它不是傳遞的，我很確定它會是NP完全的（即，假設真的，對於一般情況來說確實很慢解決），儘管我目前沒有這方面的證據。 – Dukeling