算法思想是归并排序么~3次~

我也不知道用什么算法，但我知道结果。

目前没想到啥好算法，状态压缩+DFS寻找最短路径。

将数组的每种形态使用五位数或康托展开存储，然后DFS寻找最短路径。

麻烦的是状态转换的可能，尤其数组移动感觉很恶心。

#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define  M  5

int ws[120] = {1};

void print(int s[], int n)
{
    for (int i = 0; i < n; ++i)
    {
        printf("%d%c", s[i], "\n "[i < n - 1]);
    }
}

static int fac[] = {1, 1, 2, 6, 24, 120};

/*

 * 康托展开

 */
int cantor(int sa[M])
{
    int result = 0;
    for (int i = 0; i < M; i++)
    {
        int count = 0;
        for (int j = i + 1; j < M; j++)
        {
            count += sa[i] > sa[j];
        }
        result += count * fac[M - i - 1];
    }
    return result;
}

/*

 * 逆康托展开

 */
void unCantor(int sa[M], int x)
{
    int i, j, l, t, h[10] = {0};

    for (i = 1; i <= M; i++)
    {
        t = x / fac[M - i];
        x -= t * fac[M - i];

        for (j = 1, l = 0; l <= t; j++) if (!h[j]) l++;

        h[--j] = 1, sa[i - 1] = j;
    }
}

void swap(int sa[M], int beg, int end, int to)
{
    int lren = end - beg + 1, sren[lren];
    for (int i = beg; i <= end; ++i) sren[i - beg] = sa[i];

    int stil[M - end + beg - 1], ltil = 0;
    for (int i = 0; i < M; ++i)
    {
        if (i >= beg && i <= end) continue;
        stil[ltil++] = sa[i];
    }

    int pos = 0;
    for (int i = 0; i < to; ++i) sa[pos++] = stil[i];
    for (int i = 0; i < lren; ++i) sa[pos++] = sren[i];
    for (int i = to; i < ltil; ++i) sa[pos++] = stil[i];
}

void dfs()
{
    int sa[M], queue[120] = {0}, f = 0, r = 1;

    while (f < r)
    {
        int now = queue[f++];

        for (int beg = 0; beg < M; ++beg)
        {
            for (int end = beg; end < M; ++end)
            {
                for (int to = 0; to < M - end + beg; ++to)
                {
                    unCantor(sa, now);
                    swap(sa, beg, end, to);
                    int next = cantor(sa);

                    if (ws[next]) continue;

                    queue[r++] = next;
                    ws[next] = ws[now] + 1;
                }
            }
        }
    }
}

int main()
{
    int sa[M];

    dfs();

    for (int i = 0; i < 120; ++i)
    {
        unCantor(sa, i);
        printf("step: %d   ", ws[i]);
        print(sa, M);
    }

    return 0;
}

我想这种算法可以适用于任意排列的情况~如果安照楼主顺序变逆序的排列感觉应该很简洁才对~还是看看楼主是怎么认为的~

用了四步，不对哦，用四步的话我完全可以把1后面的数往前插。
结果小于四步，不然也不会拿出来考大家。曾经高中时，有人拿扑克牌来考我，结果我一下午都没搞出来。
我想计算机可能能实现，就是算法不太好想。
我想了一个算法，不知可不可行。12345逆序数为0，54321逆序数为10，我们直接在3次以下凑这个逆序数的加减就可以了。

[此贴子已经被作者于2017-3-25 01:03编辑过]

百度到的（方括号中的数据要移到*号位置）：
第一步：*1 2[3 4]5
第二步：3*4 1[2 5]
第三步：*3 2[5 4]1
  结果：5 4 3 2 1

按数据块移动，3次可完成，可是块移不还是要一个个元素移动吗？代码实际操作还要移动6次还不如一个个元素移动呢。

你拿扑克牌12345，三次就能排序。
我只是想用计算机算出这个过程。

想了很久也想不到什么好的算法~用BFS记录每次移动变化后数据的集合~

S(1) = 0            1    
S(2) = 1            12            21
S(3) = 2            123            321
S(4) = 3            1234        4321
S(5) = S(1)    + 3        12345        1 2345     54321
S(6) = S(2) + 3        123456        12 3456        654321
S(7) = S(3) + 3        1234567        123 4567     7654321

S(n) = S(n-4) + 3

变换一下，用数值交换形式可否：

#include <stdio.h>
void swap(short *p1, short *p2)
{
    *p1 ^= *p2;
    *p2 ^= *p1;
    *p1 ^= *p2;
}

main()     
{     
    char a[]="12345";
    swap((short*)a, (short*)(a+2));
    printf("%s\n", a);
    swap((short*)(a+1), (short*)(a+3));
    printf("%s\n", a);
    swap((short*)a, (short*)(a+2));
    printf("%s\n", a);
}

[此贴子已经被作者于2017-3-24 23:46编辑过]