Какой алгоритм использовать для определения минимального числа перестановок карт в колоде?
Мои мысли на тему и получившийся алгоритм:
- обозначим для простоты карты их порядковыми номерами в отсортированной колоде, Ai;
- каждой карте сопоставим расстояние до её конечной желаемой позиции, равное i - Ai;
- перестановка карты с позиции i на позицию j меняет её расстояние на j - i, и одновременно на sign(i - j) меняет расстояния карт между i и j;
- перестановка выгодна если она уменьшает суммарное расстояние, которое потребуется пройти картам после неё;
- для текущей позиции существует по меньшей мере одна наиболее выгодная перестановка -- такая, которая максимально уменьшает оставшееся расстояние; найти её можно тупым перебором исходной и конечной позиции переставляемой карты (но, может быть, можно и быстрее);
- совершая на каждом шаге наиболее выгодную перестановку мы, скорее всего, упорядочим карты за минимальное число перестановок.
Код на c:#include <limits.h>
#include <stdio.h>
#include <string.h>

#define N (sizeof(a) / sizeof(a[0]))

inline int sign(int d)
{
        if (d == 0)
                return 0;
        return d < 0 ? -1 : 1;
}

inline int abs(int v)
{
        return v < 0 ? -v : v;
}

int main()
{
        int a[] = {2, 1, 3, 4, 0};
        int q[N];

        for (;;) {
                int best_profit = INT_MIN;
                int best_src = -1;
                int best_dst = -1;
                int i, src, dst, tmp;

                for (i = 0; i < N; ++i)
                        q[i] = i - a[i];

                for (src = 0; src < N; ++src)
                        for (dst = 0; dst < N; ++dst) {
                                int d = sign(dst - src);
                                int profit = abs(q[src]) - abs(q[src] + dst - src);

                                //printf("...%d -> %d: profit = %d", src, dst, profit);

                                for (i = src + d; i != dst + d; i += d) {
                                        if (sign(q[i]) == d) {
                                                ++profit;
                                                //printf(" + 1");
                                        } else {
                                                --profit;
                                                //printf(" - 1");
                                        }
                                }
                                //printf(" = %d\n", profit);
                                if (profit > best_profit) {
                                        best_src = src;
                                        best_dst = dst;
                                        best_profit = profit;
                                        //printf("... -- new best!\n");
                                }
                        }
                printf("%d -> %d (profit = %d)\n", best_src, best_dst, best_profit);
                if (best_profit == 0)
                        break;
                tmp = a[best_src];
                if (best_dst < best_src)
                        memmove(a + best_dst + 1, a + best_dst, (best_src - best_dst) * sizeof(int));
                else
                        memmove(a + best_src, a + best_src + 1, (best_dst - best_src) * sizeof(int));
                a[best_dst] = tmp;

                for (i = 0; i < N; ++i)
                        printf("%d ", a[i]);
                printf("\n");
        }
        return 0;
}
По какому критерию Вы оптимизируете ? По количеству перестановок ?
Потому как, если оптимизация не требуется, то просто за 52 перестановки Вы можете расставить карты на свои места всегда : либо устанавливая карту в первую позицию (доставая в инверсном), либо устанавливая карту в i-ую позицию (доставая в прямом).