数组数组的最优气泡排序算法

Question

修复正整数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][j1],A[i+1][j2]直到每个数据A[i]都i+1为每个数组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帖子可能:什么是泡沫排序好？

---

更新:下面最老的答案给出了掉期数量的下限(和上限).在第二古老的答案给出谈到真正接近这个下限(通常达到它)的算法.如果某人能够改善界限,或者甚至更好地证明下面给出的算法是最佳的,那将是很棒的.

Answer 1

这不是一个最佳答案,但我想分享我的尝试,因为有人可能会改进它.我没有考虑找到一个公式来计算最小交换次数,而是考虑最优算法.该算法基于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 << "\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;
}

我为上述代码n = 1,2,...和7运行了上面的代码.以下是答案(交换次数):0,2,5,10,15,23(非常接近)和31.我当n是偶数时,认为函数gain()不能很好地工作.你可以通过验证当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] ]