整數序列的C++有效比較（相對順序）

我將非常感謝在C++中有效實現比較算法的幫助。我的程序獲取由整數序列行組成的輸入，我需要找出哪些序列是重複的。但是一些序列可能會轉移到一邊，它應該仍然是平等的。我的意思是例如序列{0,1,22,5,9}和{22,5,9,0,1}應該是相等的。這些序列或重複序列的數量可能是一個大小。整數序列的C++有效比較（相對順序）

我似乎無法想象任何有效的事情（比較每一個新行與所有其他行都需要太多時間），所以我希望有人能提供幫助。提前致謝！

來源

2016-11-26 Sia

看看[std :: is_permutation]（http://en.cppreference.com/w/cpp/algorithm/is_permutation） –

這個排列並不是我的意思（也許我解釋自己錯了）我需要這些數字需要精確的排列，並有可能發生轉變。 – Sia

所有重複的序列是否具有相同的長度/元素，只有順序不同？或者你是否需要找到在兩個較長序列中常見的值的子串？ –

我能想到的解決方案是計算不依賴於旋轉的散列。例如：

unsigned long long hash(const std::vector<int>& seq) { 
    unsigned long long result; 
    for (int i=0,n=seq.size(),j=n-1; i<n; j=i++) { 
     result ^= seq[i] * 69069ULL + seq[j]; 
    } 
    return result; 
}

然後你就可以創建一個std::map映射的散列碼列出序列中的索引，所以你需要做一個全面的檢查只如果哈希是相同的。

來源

2016-11-26 14:19:55 6502

整數序列的C++有效比較（相對順序）

回答

相關問題