修复正整数n和k。
让A是一个长度n数组，A[i]一个长度数组k其中每个条目都n-i 。例如，对于n=5和k=1，这只是
[ [5] , [4] , [3] , [2] , [1] ]
对于n=5和k=2来说，这是
[ [5,5] , [4,4] , [3,3] , [2,2] , [1,1] ]
目标是通过交换相邻数组中的数字(例如，用 A[i+1][j2] 交换A[i][j1](来对数组数组进行气泡排序，直到每个i i+1 A[i]的每个条目。
问题是：需要多少次掉期，什么是最佳算法？
注意：有很多很多更好的排序算法可以使用。但是，对于这个问题，我只对应用上述气泡排序感兴趣。我只能交换来自相邻数组的条目，并且我只对所需的最小数量此类交换感兴趣。我确实感谢对其他排序算法的所有建议，但这是我试图理解的问题。
例子：
对于k=1来说，这是众所周知的。交换的数量是被视为排列的A的反转数，因此交换的最小数量是二项式系数(n choose 2) = n(n-1)/2，这可以通过交换任何无序对来实现：A[i] > A[j]。对于第一个示例，下面是一个最佳气泡排序：
[ [5] , [4] , [3] , [2] , [1] ]
[ [4] , [5] , [3] , [2] , [1] ]
[ [4] , [5] , [2] , [3] , [1] ]
[ [4] , [2] , [5] , [3] , [1] ]
[ [4] , [2] , [5] , [1] , [3] ]
[ [4] , [2] , [1] , [5] , [3] ]
[ [4] , [1] , [2] , [5] , [3] ]
[ [1] , [4] , [2] , [5] , [3] ]
[ [1] , [4] , [2] , [3] , [5] ]
[ [1] , [2] , [4] , [3] , [5] ]
[ [1] , [2] , [3] , [4] , [5] ]
对于k=2，使用相同的策略将给出所需的2 (n choose 2)掉期的界限。对于上面的例子，这意味着20掉期。但是有一个解决方案只使用15掉期：
[ [5,5] , [4,4] , [3,3] , [2,2] , [1,1] ]
[ [5,4] , [5,4] , [3,3] , [2,2] , [1,1] ]
[ [5,4] , [3,4] , [5,3] , [2,2] , [1,1] ]
[ [5,4] , [3,4] , [2,3] , [5,2] , [1,1] ]
[ [5,4] , [3,4] , [2,3] , [1,2] , [5,1] ]
[ [5,4] , [3,4] , [2,1] , [3,2] , [5,1] ]
[ [5,4] , [3,1] , [2,4] , [3,2] , [5,1] ]
[ [1,4] , [3,5] , [2,4] , [3,2] , [5,1] ]
[ [1,4] , [3,2] , [5,4] , [3,2] , [5,1] ]
[ [1,4] , [3,2] , [2,4] , [3,5] , [5,1] ]
[ [1,4] , [3,2] , [2,4] , [3,1] , [5,5] ]
[ [1,4] , [3,2] , [2,1] , [3,4] , [5,5] ]
[ [1,4] , [1,2] , [2,3] , [3,4] , [5,5] ]
[ [1,1] , [4,2] , [2,3] , [3,4] , [5,5] ]
[ [1,1] , [2,2] , [4,3] , [3,4] , [5,5] ]
[ [1,1] , [2,2] , [3,3] , [4,4] , [5,5] ]
此解决方案最适合n=5和k=2(通过蛮力证明找到所有解决方案(。对于n=6，最好的解决方案需要22掉期，但解决方案看起来不如n=5的解决方案好(按照右边的 5 个，然后是左边的 1，然后是右边的 5 个，等等(，所以我仍然不知道一个最佳策略，更不用说公式或更好的掉期次数了。
我已经考虑了几天了，还没有想出任何启发性的东西。如果有人对这个问题有任何想法，那么请分享。如果能更多地了解k=2案，我会很高兴。对于一般情况的任何想法来说，甚至更好。
编辑：如果我不能按照你的喜好激发这个问题，我深表歉意，但这里有一个尝试：对排列进行排序所需的气泡排序数是组合数学和数论中非常重要的统计量，称为排列的反转数。您可以使用更好的算法对无序排列进行排序，但这是赋予您代数含义的算法。如果这没有帮助，也许这个相关的SO帖子可能：泡沫排序有什么用？
更新：下面最古老的答案给出了掉期次数的下限(和上限(。第二个最古老的答案给出了一个非常接近这个下限(通常达到它(的算法。如果有人可以改进边界，或者更好的是，证明下面给出的算法是最佳的，那就太好了。
这不是一个最佳答案，但我想分享我的尝试，因为有人可能会改进它。 我没有想过找到一个公式来计算最小掉期次数，而是想过最佳算法。 该算法基于 k = 2。
基本思想是基于信息增益。假设 A = {[i，j] ： 1<=i<=n， 1<=j<=n} 表示一个配置。在每个步骤中，我们有 4 个 * (n-1( 可能的交换，以从一个配置移动到另一个配置。例如，如果 n = 2(即 A = [ {2,2}， {1,1} ] (，那么我们有 4 个可能的交换 A[0][0] <-> A[1][0]、A[0][0] <-> A[1][1]、A[0][1] <-> A[1][0] 和 A[0][1] <-> A[1][1]。 因此，我们的目标是在需要从一个配置移动到另一个配置时选择具有高信息增益的交换。
棘手的部分将是"如何计算信息增益"。 在我的解决方案(如下(中，信息增益基于值与其正确位置的距离。让我向您展示我的代码(用C++编写(来理解我想说的内容：
const int n = 5;
const int k = 2;
int gain(int item, int from, int to)
{
if (to > from)
return item - to;
else
return to - item ;
}
void swap(int &x, int &y)
{
int temp = x;
x = y;
y = temp;
}
void print_config (int A[][k])
{
cout << "[";
for (int i=0; i<n; i++) {
cout << " [";
for (int j=0; j<k; j++) {
cout << A[i][j] << ", ";
}
cout << "bb], ";
}
cout << "bb ]" << endl;
}
void compute (int A[][k], int G[][4])
{
for (int i=0; i<n-1; i++)
{
G[i][0] = gain(A[i][0], i+1, i+2) + gain(A[i+1][0], i+2, i+1);
G[i][1] = gain(A[i][0], i+1, i+2) + gain(A[i+1][1], i+2, i+1);
G[i][2] = gain(A[i][1], i+1, i+2) + gain(A[i+1][0], i+2, i+1);
G[i][3] = gain(A[i][1], i+1, i+2) + gain(A[i+1][1], i+2, i+1);
}
}
int main()
{
int A[n][k];
int G[n-1][k*k];
// construct initial configuration
for (int i=0; i<n; i++)
for (int j=0; j<k; j++)
A[i][j] = n-i;
print_config(A);
int num_swaps = 0;
int r, c;
int max_gain;
do {
compute (A, G);
// which swap has high info gain
max_gain = -1;
for (int i=0; i<n-1; i++)
for (int j=0; j<k*k; j++)
if (G[i][j] > max_gain) {
r = i;
c = j;
max_gain = G[i][j];
}
// Did we gain more information. If not terminate
if (max_gain < 0) break;
switch (c)
{
case 0: swap(A[r][0], A[r+1][0]); break;
case 1: swap(A[r][0], A[r+1][1]); break;
case 2: swap(A[r][1], A[r+1][0]); break;
case 3: swap(A[r][1], A[r+1][1]); break;
}
print_config(A);
num_swaps++;
} while (1);
cout << "Number of swaps is " << num_swaps << endl;
}
我针对 n=1,2 的情况运行了上面的代码,...和 7. 以下是答案(掉期次数(：0、2、5、10、15、23(非常接近(和 31。 我认为函数 gain(( 在 n 为偶数时不能很好地工作。 您能否通过验证 n = 7 时的交换次数来确认这一点。等式的下限是 31，所以这是 n = 7 时的最佳掉期次数。
当 n = 5 时，我在这里打印输出(因为您正在寻找一种模式(：
[ [5, 5], [4, 4], [3, 3], [2, 2], [1, 1] ]
[ [4, 5], [5, 4], [3, 3], [2, 2], [1, 1] ]
[ [4, 5], [3, 4], [5, 3], [2, 2], [1, 1] ]
[ [4, 5], [3, 4], [2, 3], [5, 2], [1, 1] ]
[ [4, 5], [3, 4], [2, 3], [1, 2], [5, 1] ]
[ [4, 3], [5, 4], [2, 3], [1, 2], [5, 1] ]
[ [4, 3], [2, 4], [5, 3], [1, 2], [5, 1] ]
[ [4, 3], [2, 4], [1, 3], [5, 2], [5, 1] ]
[ [4, 3], [2, 4], [1, 3], [1, 2], [5, 5] ]
[ [4, 3], [2, 1], [4, 3], [1, 2], [5, 5] ]
[ [1, 3], [2, 4], [4, 3], [1, 2], [5, 5] ]
[ [1, 3], [2, 4], [1, 3], [4, 2], [5, 5] ]
[ [1, 3], [2, 1], [4, 3], [4, 2], [5, 5] ]
[ [1, 1], [2, 3], [4, 3], [4, 2], [5, 5] ]
[ [1, 1], [2, 3], [2, 3], [4, 4], [5, 5] ]
[ [1, 1], [2, 2], [3, 3], [4, 4], [5, 5] ]
回答自己的问题相当俗气，但我刚刚想通了这一点，它更接近答案而不是问题的一部分。但是，这不是一个完整的答案，不会被接受，所以如果有人可以改进这一点，请发表想法。
k=2的最小隔夜利息数(例如m(受以下限制：
2 * (n choose 2) >= m >= (2n choose 2) / 3
为什么会这样？
上限是对数组的第一个元素进行气泡排序，然后在数组的第二个元素上进行气泡排序。这部分并不那么棘手。
下限有点棘手，但这是我是如何得出的。让我们计算传递次数，当较大的数字从较小数字的左侧移动到该数字的右侧时，就会发生传递。这可能发生在 1 次交换 a 和 b 中，a更大，在数组的左侧b。如果将a移动到阵列中，并在一次交换中b，然后在以后的交换中继续移动，则也可能需要 2 次交换。为了正确跟踪事物，在这种情况下，将传递数成两半。为了使计数更容易，当两个相同数字的拆分然后重新组合时，它也算作一个通过。
数组在 (2n choose 2) 次传递后完全排序，因此唯一的问题是一次交换可以发生多少次传递。下面是交换a和c的简单示例：
... [a,b] , [c,d] ...
... [c,b] , [a,d] ...
现在让我们计算可能发生的最大传递次数：
- 自
a > c年以来，我们肯定会获得 1 次完整通过。 - 如果
a > b，那么我们会得到 1/2 通过，因为a一定在某个时候留下了b。 - 如果
a > d，那么我们会得到 1/2 的通过，因为a在某些时候会正确d。 - 如果
c < d，那么我们得到 1/2 通过，因为d一定在某个时候留下了c。 - 如果
c < b，那么我们得到 1/2 通过，因为b在某些时候会正确c。
因此，您在交换中能做的最好的事情就是获得 3 次传球(1 次全传和 4 次半场(。
为什么这不是一个完整的答案？
我不知道下限是否总是可以实现的！我认为不是，而且，尽管有几次失败的尝试，但我无法编写实现它的算法。
这是我想到的一个直观的算法。我认为它为最佳解决方案提供了建设性的证明。
这是算法：
我尝试了 n= 4 5 6 7 9，它给出了与 badawi 相同的结果：
思路如下：
1：选择一个不在最终位置的极值(1或n开始(
2：找到最接近他最终位置的极值(在下面的例子中用箭头标记(
3：如果它是最大的精灵之一，
然后将其移动到另一侧，并将对中的所有最小元素向左移动
否则
将其移动到另一侧，然后将每对的所有最大元素向右移动。
注意：移位等同于用每对的小(resp 最大(元素"冒泡"这个值。
4：返回步骤2，但是如果您选择了其中一个大，请选择一个小的，反之亦然。
它非常直观，似乎有效：
示例 n=5：
11 22 33 44 55
^
|
12 23 34 45 51 (4 moves) // shifted all larger numbers to the left
^
|
52 13 24 43 51 (3 moves) // shifted all smaller numbers to the right
^
|
52 34 24 35 11 (3 moves) // shifted all larger numbers to the left
^
|
55 24 34 32 11 (3 moves) // smaller to the right
^
|
55 44 33 22 11 (2 moves) // larger to left
总共15个动作。
第二个示例 n=7：
11 22 33 44 55 66 77 // 6 moves
^
12 23 34 45 56 67 71 //5 moves
^
72 13 24 35 46 56 71 //5 moves
^
72 34 25 36 46 57 11 // 4 moves
^
77 24 35 26 36 45 11 //4 moves
^
77 45 36 26 35 42 11 //1 move
^
77 65 34 26 35 42 11 //2 moves
^
77 65 34 56 34 22 11 //2 moves
^
77 66 54 53 34 22 11 //1 move
^
77 66 54 45 33 22 11 //1 move
^
77 66 55 44 33 22 11
共：31
条如果我不清楚，请随时问我问题。
手工完成很容易。您可以自己尝试使用 6 或 7 或编写算法。
我用 6 试过了，它给了 23。，用 7 它给出 31，用 9 它给出 53，手动计算它需要一分钟而无需计算任何东西
为什么这个解决方案是最佳的：
每次将一个大元素移动到另一侧时，都会将一对中最小的元素移动到左侧。
因此，移动所有大元素不会使您失去移动所有最小元素的任何移动。
你总是把你的元素推向"正确的方向"
此外，对于移动极端元素，您可以进行最少的移动次数。(这是因为算法取最接近他最后位置的极值，没有移动丢失(
小元素的推理是一样的。
该算法为您提供最佳动作，因为它不会进行任何动作 不必要的移动。
希望我没有犯任何错误.
它证明badawi结果如您所料是最佳的。