What algorithm should be used to determine the minimum number of card permutations in a deck?

Question

Programming

there is a deck of cards (cards are not repeated).
the initial positions of each card are known - which is in the first place, which is in the second, etc.
then the cards are shuffled and new positions of the cards are learned.
What algorithm can be used when writing a function that would return a table of card movements (the number of movements should be minimal)?
moving (permuting) cards in this case means "to move a card to a certain place (index)". Moreover, if we, for example, move the last card to the first place, all other cards increase their index by one (that is, the card that was first before this move becomes second, the second becomes third, etc.)
PS: it will be great to understand how this can be implemented at least in general terms. This is necessary for a script that I write in lua, but the language, it seems to me, is not fundamental here, the main thing would be to understand the idea of ​​​​the algorithm

Answer 1

The correct answer is 52-<length of the longest common subsequence>.
It is displayed as follows:
1) It makes no sense to move a single card 2 times. Those. answer 52-<number of fixed cards>
2) The fixed cards are in the same order in both decks, hence they form the largest common subsequence.
The largest common subsequence is actually their line processing theme, we will assume that we are given 2 52-character strings, one character-one card, all characters are different. NOP is the largest string that will remain if some characters are omitted from the first and second strings. It is searched for quadratic complexity (in this case - instantly, lines of a fixed length) by dynamic programming.
F(i, j) - length of the longest common substring for prefixes of length i for the first string and length j for the second.
Base F(0,*)=F(*,0)=0
Transition: F(i,j) = max(F(i-1,j), F(i,j-1), F(i-1 ,j-1)+1). The third option is considered only if the i-th character in the first line and the j-th character in the second are equal.
The answer is 52-F(52,52) for your task.
If you need to give out where to move something, then the task is a little more complicated. The dynamics is modified by saving which of the three options was chosen, in order to then restore the NOP. These cards are marked as immobile. Then, for all the cards in the second deck, find their places in the first deck. And then, stupidly, move the moving cards one at a time to the right places in ascending order of the resulting places. Then it will not be necessary to take into account cards that have not yet been moved at all.

Answer 2

My thoughts on the topic and the resulting algorithm:
- for simplicity, let's designate the cards by their serial numbers in the sorted deck, A _i ;
- to each card we compare the distance to its final desired position, equal to i - A _i ;
- permutation of the card from position i to position j changes its distance by j - i, and at the same time by sign(i - j) changes the distances of cards between i and j;
- permutation is beneficial if it reduces the total distance that the cards will need to go after it;
- for the current position, there is at least one most advantageous permutation - one that minimizes the remaining distance as much as possible; you can find it by blunt enumeration of the initial and final positions of the card being rearranged (but, perhaps, it can be faster);
- making the most profitable permutation at each step, we are likely to arrange the cards in the minimum number of permutations.
c code:

#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;
}

Answer 3

By what criteria do you optimize? By the number of permutations?
Because, if optimization is not required, then just in 52 permutations you can always put the cards in their places: either by placing the card in the first position (drawing in inverse), or by placing the card in the i-th position (drawing in direct).