algorithm - 使用 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。

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

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

Answer 1

生成排列的算法是Heap's algorithm .此代码是一种计算 n 对象排列的蛮力方法。对于每个配置，传递次数是任何元素从其排序位置开始的最大长度，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) ，但是带有冒泡排序遍的代码不匹配任何文档。