我们得到了两个小写拉丁字母序列。它们的长度相同，具有相同数量的给定类型字母数(第一个字母的t数与第二个字母的相同，因此on(。我们需要找到掉期的最小数量("掉期"指的是变化两个相邻字母的顺序(将第一序列转换为第二序列。我们可以安全地假设每两个序列can都被转换相互转化。我们可以用蛮力做到这一点，但序列太长了。
输入：
序列的长度(至少2，最多999999(和然后是两个序列。输出：
一个整数，表示序列变得相同。示例：
{5，aaaaa，aaaaa}应输出{0}，
｛4，abcd，acdb｝应该输出｛2｝。
我首先想到的是泡泡糖。我们可以简单地计算每个交换的顺序。问题是：a(这是O(n^2(最坏的情况b(我不相信它会给我每种情况下的最小数字。。。即使是经过优化的bubblesort似乎也没有起到作用。我们可以实现鸡尾酒类型，这将解决海龟的问题，但它会给我最好的性能吗？或者可能有更简单/更快的东西？
这个问题也可以表述为：当唯一允许的操作是换位时，我们如何确定两个字符串之间的编辑距离
关于将一个排列转换为另一个排列所需的最小交换次数(不一定是相邻的(，您应该使用的度量是Cayley距离，它本质上是排列的大小-循环数。
计算排列中的循环数是一个非常琐碎的问题。一个简单的例子。假设排列521634。
如果你检查第一个位置，你有5，在第五个位置你有3，在第三个位置你是1，结束第一个循环。2在第二个位置，所以它自己做一个循环，4和6做最后一个循环(4在第六个位置，6在第四个位置(。如果你想在单位置换中转换这个置换(交换次数最少(，你需要独立地对每个循环重新排序。交换的总数是置换的长度(6(减去循环的数量(3(。
给定任意两种排列，它们之间的距离等于第一种排列与第二种排列的倒数的组合与恒等式(如上所述计算(之间的距离。因此，你唯一需要做的就是组成第一个排列和第二个排列的倒数，并计算结果中的循环数。所有这些运算都是O(n(，所以你可以得到线性时间中交换的最小数量。
这里有一个简单高效的解决方案：
设CCD_ 1。设P[i] = on what position is the character corresponding to s1[i] in the second string。
构建Q和p:
for ( int i = 0; i < s1.size(); ++i )
Q[ s2[i] ].push_back(i); // basically, Q is a vector [0 .. 25] of lists
temp[0 .. 25] = {0}
for ( int i = 0; i < s1.size(); ++i )
P[i + 1] = 1 + Q[ s1[i] ][ temp[ s1[i] ]++ ];
示例：
1234
s1: abcd
s2: acdb
Q: Q[a = 0] = {0}, Q[b = 1] = {3}, Q[c = 2] = {1}, Q[d = 3] = {2}
P: P[1] = 1, P[2] = 4 (because the b in s1 is on position 4 in s2), P[3] = 2
P[4] = 3
P有2逆(4 2和4 3(，所以这就是答案。
这个解决方案是O(n log n)，因为构建P和Q可以在Q[ s2[i] ] = the positions character s2[i] is on in s20中完成，合并排序可以计算O(n log n)中的反转。
您所寻找的可能与">Kendall-tau距离"相同，后者是一致-不一致对的(归一化(差异。请参阅维基百科，它声称它相当于气泡排序距离。
在R中，函数不仅可用于计算τ，例如
cor( X, method="kendall", use="pairwise" ) ,
而且还用于测试差异的重要性，例如
cor.test( x1, x2, method="kendall" ) ,
他们甚至能够适当地考虑到关系。
请参阅此处了解更多信息。
">Kendall-tau距离"算法是这种情况下的精确解，其中必须找到相邻元素的交换次数。
示例。
eyssaasse(基字符串(
海洋生物
基本字符串为每个元素提供索引：e=0，y=1，s=2，1=3，2a=4，a=5，
s=6，
有些元素是重复的，因此：
1( 创建一个字典，其中元素是键，值是索引列表：
2( 使用idx字典中的元素索引创建第二个字符串的索引映射：
seasysaes->204316587(循环"seasysaes"并从列表中为idx中的每个键弹出下一个索引(
3( 创建此地图的所有配对组合的列表，204316587:20 24 23 21 26 25 28 27 04 03 01 06。。。65 68 67 58 57 87
循环这些对，计算第一个数字大于第二个数字的对
此计数是字符串之间相邻交换的数量。
Python脚本：
from itertools import combinations, cycle
word = 'eyssaasse' # base string
cmpr = 'seasysaes' # a string to find number of swaps from the base string
swaps = 0
# 1)
chars = {c: [] for c in word}
[chars[c].append(i) for i, c in enumerate(word)]
for k in chars.keys():
chars[k] = cycle(chars[k])
# 2)
idxs = [next(chars[c]) for c in cmpr]
# 3)
for cmb in combinations(idxs, 2):
if cmb[0] > cmb[1]:
swaps += 1
print(swaps)
"eyssaasse"one_answers"seasysaes"之间的交换数量为7。
"reviver"one_answers"vrerevi"是8。
我写了一个类Permutation，它可以返回将给定排列转换为恒等式所需的许多转座。这是通过创建轨道(循环(并计算其长度来完成的。术语取自Kostrikin A.，I.，"线性代数导论I">。
包括：
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <iterator>
类排列：
class Permutation {
public:
struct ei_element { /* element of the orbit*/
int e; /* identity index */
int i; /* actual permutation index */
};
typedef std::vector<ei_element> Orbit; /* a cycle */
Permutation( std::vector<int> const& i_vector);
/* permute i element, vector is 0 indexed */
int pi( int i) const { return iv[ i - 1]; }
int i( int k) const { return pi( k); } /* i_k = pi(k) */
int q() const { /* TODO: return rank = q such that pi^q = e */ return 0; }
int n() const { return n_; }
/* return the sequence 1, 2, ..., n */
std::vector<int> const& Omega() const { return ev; }
/* return vector of cycles */
std::vector<Orbit> const& orbits() const { return orbits_; }
int l( int k) const { return orbits_[ k].size(); } /* length of k-th cycle */
int transpositionsCount() const; /* return sum of all transpositions */
void make_orbits();
private:
struct Increment {
int current;
Increment(int start) : current(start) {}
int operator() () {
return current++;
}
};
int n_;
std::vector<int> iv; /* actual permutation */
std::vector<int> ev; /* identity permutation */
std::vector<Orbit> orbits_;
};
定义：
Permutation::Permutation( std::vector<int> const& i_vector) :
n_( i_vector.size()),
iv( i_vector), ev( n_) {
if ( n_) { /* fill identity vector 1, 2, ..., n */
Increment g ( 1);
std::generate( ev.begin(), ev.end(), g);
}
}
/* create orbits (cycles) */
void Permutation::make_orbits() {
std::set<int> to_visit( ev.begin(), ev.end()); // identity elements to visit
while ( !to_visit.empty()) {
/* new cycle */
Orbit orbit;
int first_to_visit_e = *to_visit.begin();
to_visit.erase( first_to_visit_e);
int k = first_to_visit_e; // element in identity vector
/* first orbit element */
ei_element element;
element.e = first_to_visit_e;
element.i = i( first_to_visit_e);
orbit.push_back( element);
/* traverse permutation until cycle is closed */
while ( pi( k) != first_to_visit_e && !to_visit.empty()) {
k = pi( k);
ei_element element;
element.e = k;
element.i = pi( k);
orbit.push_back( element);
to_visit.erase( k);
}
orbits_.push_back( orbit);
}
}
和：
/* return sum of all transpositions */
int Permutation::transpositionsCount() const {
int count = 0;
int k = 0;
while ( k < orbits_.size()) {
count += l( k++) - 1; /* sum += l_k - 1 */
}
return count;
}
用法：
/*
*
*/
int main(int argc, char** argv) {
//1, 2, 3, 4, 5, 6, 7, 8 identity (e)
int permutation[] = {2, 3, 4, 5, 1, 7, 6, 8}; // actual (i)
std::vector<int> vp( permutation, permutation + 8);
Permutation p( vp);
p.make_orbits();
int k = p.orbits().size();
std::cout << "Number of cycles:" << k << std::endl;
for ( int i = 0; i < k; ++i) {
std::vector<Permutation::ei_element> v = p.orbits()[ i];
for ( int j = 0; j < v.size(); ++j) {
std::cout << v[ j].e << "," << v[ j].i << " | ";
}
std::cout << std::endl;
}
std::cout << "Steps needed to create identity permutation: "
<< p.transpositionsCount();
return 0;
}
输出：
循环次数：3
1,2|2,3|3,4|4,5|5,1|
6,7|7,6|
8,8|
创建身份置换所需的步骤：5
运行成功(总时间：82ms(
coliru
通过反转O(n(中的目标排列，组合O(n中的排列，然后找到从那里到单位排列的交换数量，可以将排列从一个转换为另一个问题(排列中的交换数量(。给定：
int P1[] = {0, 1, 2, 3}; // abcd
int P2[] = {0, 2, 3, 1}; // acdb
// we can follow a simple algebraic modification
// (see http://en.wikipedia.org/wiki/Permutation#Product_and_inverse):
// P1 * P = P2 | premultiply P1^-1 *
// P1^-1 * P1 * P = P1^-1 * P2
// I * P = P1^-1 * P2
// P = P1^-1 * P2
// where P is a permutation that makes P1 into P2.
// also, the number of steps from P to identity equals
// the number of steps from P1 to P2.
int P1_inv[4];
for(int i = 0; i < 4; ++ i)
P1_inv[P1[i]] = i;
// invert the first permutation O(n)
int P[4];
for(int i = 0; i < 4; ++ i)
P[i] = P2[P1_inv[i]];
// chain the permutations
int num_steps = NumSteps(P, 4); // will return 2
// now we just need to count the steps
为了计算步骤，可以设计一个简单的算法，例如：
int NumSteps(int *P, int n)
{
int count = 0;
for(int i = 0; i < n; ++ i) {
for(; P[i] != i; ++ count) // could be permuted multiple times
swap(P[P[i]], P[i]); // look where the number at hand should be
}
// count number of permutations
return count;
}
这总是将一个项目交换到它应该在身份置换中的位置，因此在每一步中，它都会撤消并计数一次交换。现在，只要它返回的交换数量确实是最小的，算法的运行时就受其限制，并保证完成(而不是陷入无限循环(。它将在O(m)交换或O(m + n)循环迭代中运行，其中m是交换的数量(返回的count(，n是序列中的项目数量(4(。请注意，m < n始终为真。因此，这应该优于O(n log n)解，因为这里的上界是交换的O(n - 1)或循环迭代的O(n + n - 1)，这两者实际上都是O(n)(在后一种情况下省略了常数因子2(。
该算法只适用于有效的排列，它将对具有重复值的序列无限循环，并对具有[0, n)以外值的序列执行越界数组访问(和崩溃(。这里可以找到一个完整的测试用例(使用VisualStudio2008构建，算法本身应该是可移植的(。它生成长度为1到32的所有可能的排列，并对照广度优先搜索(BFS(生成的解决方案进行检查，似乎适用于长度为1至12的所有排列，然后它变得相当慢，但我认为它会继续工作。