修正的正整数 N 和 K 。

让 A 是长度 N 与数组A [1] 长度的数组 K ，每一个条目是 NI 。例如， N = 5 和 K = 1 ，这只是

Let A be an array of length n with A[i] an array of length k where every entry is n-i. For example, with n=5 and k=1, this is just

[ [5] , [4] , [3] , [2] , [1] ]

和 N = 5 和 K = 2 ，这是

[ [5,5] , [4,4] , [3,3] , [2,2] , [1,1] ]

我们的目标是冒泡排序此数组的数组由相邻阵列交换数字（例如交换 A [1] [J1] 与 A [我+ 1] [J2] ），直到 A [1] 的每一个条目 I + 1 ，每我。

The goal is to bubble sort this array of arrays by swapping numbers in adjacent arrays (e.g. swap A[i][j1] with A[i+1][j2]) until every entry of A[i] is i+1 for every i.

现在的问题是：？有多少掉期是必要的和什么是优化算法

注意： 还有很多很多更好的排序算法使用。然而，对于这个问题，我只关心应用排序上面描述的泡沫。我只能从邻近的阵列交换项目，我只关心有必要这样交汇处的最低数量。我做AP preciate为其它排序算法的建议，但是这是我想了解的问题。的

例子：

有关 K = 1 ，这是众所周知的。掉期的数量是 A 的反转数量视为排列，因此交换的最小数量是二项式系数（正选2） = N（N-1）/ 2 ，这可以通过交换任何乱序对来实现： A [1]＆GT; A [J] 。对于第一个例子，这里是一个最佳的冒泡排序：

For k=1, this is well known. The number of swaps is the inversion number of A regarded as a permutation, and so the minimum number of swaps is the binomial coefficient (n choose 2) = n(n-1)/2 and this can be attained by swapping any out of order pair: A[i] > A[j]. For the first example, here's an optimal bubble sort:

[ [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选择2）互换必要的。对于上面的例子，这意味着 20 互换。但是，仅使用 15 交换的解决方案：

For k=2, using the same strategy would give a bound of 2 (n choose 2) swaps needed. For the example above, that means 20 swaps. But there is a solution that uses only 15 swaps:

[ [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右等），所以我还是不知道的最佳策略，更不用说公式或用于交换的数量较好结合。

This solution is optimal for n=5 and k=2 (proof by brute force to find all solutions). For n=6, the best solution takes 22 swaps, but the solution doesn't look as nice as the one for n=5 (follow the 5 right, then the 1 left, then the 5 right, etc), so I still don't know an optimal strategy, much less a formula or better bound for the number of swaps.

我一直在想这几天的现在，还没有想出什么启发。如果任何人对这个问题有什么想法的话，请分享。我很高兴与了解更多关于 K = 2 情况。即使是在一般的情况下，任何的想法更好。

I've been thinking about this for a couple of days now and haven't come up with anything enlightening. If anyone has any thoughts on this problem, then please share them. I'd be thrilled with knowing more about the k=2 case. Even better for any thoughts on the general case.

编辑：我很抱歉，如果我不能激励这个问题，根据自己的喜好，但这里的尝试：对需要置换排序气泡排序数在组合数学与数论一个非常重要的统计，叫作置换的反转数量。你可以梳理出一个使用更好的算法秩序排列的，但是这是一个，让你的代数意义。如果这样做没有帮助，这也许SO相关的职位可能：什么是泡沫什么？排序好的

I apologize if I cannot motivate this problem to your liking, but here's an attempt: the number of bubble sorts needed to sort a permutation is a very important statistic in combinatorics and number theory, called the inversion number of the permutation. You can sort an out of order permutation using much better algorithms, but this is the one that gives you the algebraic meaning. If that doesn't help, perhaps this related SO post may: What is a bubble sort good for?

更新的：在oldest下面的答案给出较低（与上部）开往互换的次数。该second最古老的答案给出了一个算法，来真正接近这个下限（通常达到它）。这将是非常美妙的，如果有人可以提高装订成册，或者甚至更好，证明下面给出的算法是最优的。

UPDATE: The oldest answer below gives a lower (and upper) bound for the number of swaps. The second oldest answer gives an algorithm that comes really close to this lower bound (often attaining it). It would be fantastic if someone could improve the bound, or, even better, prove that the algorithm given below is optimal.

推荐答案

这是不是一个最佳答案，但我想和大家分享我的企图有人可能会改善它。我没有想过要找一个公式来计算的掉期交易，而是在优化算法的最小数量。该算法基于k = 2

This is not an optimal answer, but i would like to share my attempt as someone may improve it. I did not thought about finding a formula to calculate the minimum number of swaps but rather on the optimal algorithm. The algorithm is based on k = 2.

的基本思想是基于信息增益。让我们假定A = {[I，J]：1所述; = I＆其中; = n时，1所述; = J＆其中; = n}的重新presents一个的构造的。在每一个步骤中，我们有4 *（N-1）可以交换移动至从一种配置到另一种配置。例如如果n = 2（即A = [{2,2}，{1,1}]），则有4个可能的交换A [0] [0]＆LT; - > A [1] [0] A [0] [0]＆LT; - > A [1] [1]，A [0] [1]; - > A [1] [0]，和A [0] [1]; - > A [1] [1]。因此，我们的目标是选择具有高信息增益，当我们需要移动从一个配置到另一个配置的交换。

The basic idea is based on information gain. Let us assume that A = {[i,j] : 1<=i<=n, 1<=j<=n} represents a configuration. In each step, we have 4 * (n-1) possible swapping to move from one configuration to another configuration. For example if n = 2 (i.e. A = [ {2,2}, {1,1} ] ), then we have 4 possible swapping A[0][0] <-> A[1][0], A[0][0] <-> A[1][1], A[0][1] <-> A[1][0], and A[0][1] <-> A[1][1]. Thus, our objective is to select the swap that has high information gain when we need to move from one configuration to another configuration.

最棘手的部分将是如何计算的信息增益。在我的溶液（下），信息增益是根据从正确的位置的值的距离。让我告诉你我的code（C语言编写），以明白我想说的：

The tricky part will be "how to calculate the information gain". In my solution (below), the information gain is based on the distance of a value from its correct position. Let me show you my code (written in C++) to understand what i am trying to say:

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 << "\b\b], ";
    }
    cout << "\b\b ]" << 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;
}

我跑了超过$ C $下的情况下，N = 1,2，...和7下面分别答案（掉期的号码）：0，2，5，10，15，23（非常接近），和31。我认为功能增益（）无法正常工作，当n为偶数。你能否证实通过验证交换的数量当n = 7，下界你的公式是31，所以这是交换的最佳数量，当n = 7。

I ran the above code for cases n=1,2,... and 7. Here are the answers (number of swaps) respectively: 0, 2, 5, 10, 15, 23 (very close), and 31. I think that the function gain() does not work well when n is even. Can you confirm that by validating the number of swaps when n = 7. The lower bound of your equation is 31 so this is the optimal number of swaps when n = 7.

我在这里打印输出，当n = 5（因为你正在寻找一个模式）：

I am printing here the output when n = 5 (since you are looking for a pattern):

[ [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] ]