Мои мысли на тему и получившийся алгоритм:
- обозначим для простоты карты их порядковыми номерами в отсортированной колоде, A
i;
- каждой карте сопоставим расстояние до её конечной желаемой позиции, равное i - A
i;
- перестановка карты с позиции 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;
}
