整数序列的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++有效比较（相对顺序）

回答

相关问题