使用 BubbleSort 完全排序所需的遍数？

Question

我正在研究对 array[n].

中每个可能的整数组合 [1,n] 进行排序所需的遍数背后的数学原理

例如，对于 n = 3，数字有 3! = 6 种可能的排列：

1,2,3 - 1,3,2 - 2,1,3 - 2,3,1 - 3,1,2 - 3,2,1.

其中一个初始排列需要 k = 0 遍 (1,2,3) 来对数组进行升序排序；
其中三个需要 k = 1 通过 (1,3,2 - 2,1,3 - 3,1,2) 和
两次需要 k = 2 遍 (2,3,1 - 3,2,1)。

基本上，我希望能够从数学上推导出给定 n 的传球次数集 {k}。

对于 n = 4，需要 k 遍的初始排列 P 的数量是 P(n,k) = 1,7,10,6 for k = 0,1,2,3。

当然只有1个k = 0的初始排列（已经按升序排列），即P(n,0) = 1，以及k的最高值（即n-1）的初始排列数) 是 k!，即 P(n,n-1) = (n-1)! 。或者，至少我是这么认为的...

我觉得这比我做的要简单，而且涉及阶乘公式。

Answer 1

取决于实施：如果你只朝一个方向前进，那么当它的目的地与迭代方向相反时，任何元素最多会靠近它的目的地一步。因此，所需的迭代次数取决于任何单个元素在该方向上需要移动的最大距离。

如果你来回迭代，它就不那么明显了。我怀疑通过转换为有向图（其中每条边指向需要与之交换的其他元素），属性个边将给出答案。

Answer 2

生成排列的算法是Heap's algorithm。此代码是计算 n 对象排列的 brute-force 方法。对于每个配置，通过次数是任何元素从其排序位置开始的最大长度，O(n)。给定 n，这会通过直方图给出所有 P(n, k)；运行时间在 n 中呈指数增长（在 C 中）

#include <stdlib.h> /* EXIT */
#include <stdio.h>  /* printf */
#include <assert.h> /* assert */
#include <errno.h>  /* errno, ERANGE */

typedef void (*PermuteFunc)(const size_t a_size);

unsigned a[12];
const size_t a_max = sizeof a / sizeof *a;

/* https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3 */
static void heaps_r(const size_t a_size, const unsigned k,
    const PermuteFunc func) {
    size_t i, j;
    assert(k && a_size);
    if(k == 1) { func(a_size); return; }
    for(i = 0; i < k; i++) {
        heaps_r(a_size, k - 1, func);
        if(i >= k - 1) continue;
        j = (k & 1) ? 0 : i; /* Odd/even. */
        a[j] ^= a[k-1], a[k-1] ^= a[j], a[j] ^= a[k-1]; /* Swap. */
    }
}

/* Generates all permutations of size `a_size` and passes them to `func`.
 @return Success. */
static int heaps(const size_t a_size, const PermuteFunc func) {
    size_t i;
    assert(func);
    if(!a_size || a_size > a_max) return errno = ERANGE, 0;
    for(i = 0; i < a_size; i++) a[i] = i + 1; /* Distinct numbers. */
    heaps_r(a_size, a_size, func);
    return 1;
}

static unsigned histogram[256]; /* This is good enough, right? */
static size_t histogram_size = sizeof histogram / sizeof *histogram;

/* @implements PermuteFunc */
static void print(const size_t a_size) {
    size_t i, bin = 0;
    assert(a && a_size);
    for(i = 0; i < a_size; i++) printf("%d ", a[i]);
#if 0 /* I misread the question. */
    /* O(n^2) way to calculate the Kendall tau distance. */
    for(i = 0; i < a_size; i++) {
        size_t j;
        for(j = i + 1; j < a_size; j++) if(a[i] > a[j]) bin++;
    }
#else
    /* Calculate the number of passes bubble-sort needs to make. */
    for(i = 0; i < a_size; i++) {
        size_t passes = abs(a[i] - i);
        if(passes > bin) bin = passes;
    }
#endif
    if(bin >= histogram_size) {
        fprintf(stderr, "Histogram too small for %d.\n", (unsigned long)bin);
        return;
    }
    histogram[bin]++;
    printf("-> %d\n", bin);
}

int main(int argc, char **argv) {
    int n;
    size_t k;
    const char *err = 0;
    do {
        if(argc != 2 || (n = atoi(argv[1]), n <= 0))
            { errno = EDOM; err = "Argument needed"; break; }
        if(!heaps(n, &print)) { err = "Heap's"; break; }
        printf("\n");
        for(k = 0; k < histogram_size; k++) if(histogram[k])
            printf("P(%d, %lu) = %u\n", n, (unsigned long)k, histogram[k]);
    } while(0);
    return err ? (perror(err), EXIT_FAILURE) : EXIT_SUCCESS;
}

通过 4，我得到，

P(4, 1) = 1
P(4, 2) = 7
P(4, 3) = 10
P(4, 4) = 6

我用谷歌搜索了 Kendall tau 距离代码并注意到它是 coefficients in expansion of Product_{i=0..n-1} (1 + x + ... + x^i)，但是带有 bubble-sort 的代码与任何文档都不匹配。

使用 BubbleSort 完全排序所需的遍数？

Number of required passes to fully sort using BubbleSort?

sorting

algorithm

bubble-sort