时间戳

首页 > 解决方案 > 使用 BubbleSort 完全排序所需的通过次数？

algorithm - 使用 BubbleSort 完全排序所需的通过次数？

问题描述

我正在研究[1,n]对array[n].

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

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

基本上，我希望能够从数学上推导出{k}给定n.

对于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)!。或者，至少我是这么认为的……

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

标签： algorithmsortingbubble-sort

解决方案

用于生成排列的算法是 Heap 算法。此代码是计算对象排列的蛮力方法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 距离代码，注意到它是 Product_{i=0..n-1} (1 + x + ... + x^i) 扩展中的系数，但是带有气泡传递的代码- sort 不匹配任何文档。

推荐阅读