Reordering task

Question

I'm trying to solve tiny task within a c++ algorithm but don't want to reinvent the wheel and looking for a math way.

Imagine a row of people when some of them are changing their positions by their own and as a result shifting their neighbors. Example is below(pretty random)

First matrix (Initial state)

0  | Daniel
1  | Alan
2  | Kate
3  | Tom
4  | Sandra
5  | Andrew
6  | Paul
7  | Laura
8  | Sophia
9  | Emma
10 | Carl

Second matrix (Final state)

7  | Daniel
3  | Alan
2  | Kate
4  | Tom
5  | Sandra
1  | Andrew
6  | Paul
8  | Laura
10 | Sophia
0  | Emma
9  | Carl

What I need is a list with minimal moving instructions to achieve the final state:

1. Emma, please go from 9 to 0 (current positions of all others are shifted)

2. X, please go from your current(shifted by Emma) position' to position2.

3. ...

I guess that this can be solved as matrix task, but at the same time it looks as a sorting task as well when just factors are changed. Anyway my turn to ask an all-knowing community for help ;)

Update 1 (Levenshtein distance/Wagner-Fischer algo)

Initial string 'order-1': 0123456789A

Final string 'order-2': 73245168A09

Where:

• 0 for Daniel
• 1 for Alan
• ...

To achieve the final state we need to apply these instructions to order-1:

1. replace '0' with '7';
2. replace '1' with '3';
3. delete '3';
4. insert '1';
5. delete '7';
6. replace '9' with 'A';
7. insert '0';
8. replace 'A' with '9';

Matrix:

[00,01,02,03,04,05,06,07,08,09,10,11]
[01,01,02,03,04,05,06,07,08,09,09,10]
[02,02,02,03,04,05,05,06,07,08,09,10]
[03,03,03,02,03,04,05,06,07,08,09,10]
[04,04,03,03,03,04,05,06,07,08,09,10]
[05,05,04,04,03,04,05,06,07,08,09,10]
[06,06,05,05,04,03,04,05,06,07,08,09]
[07,07,06,06,05,04,04,04,05,06,07,08]
[08,07,07,07,06,05,05,05,05,06,07,08]
[09,08,08,08,07,06,06,06,05,06,07,08]
[10,09,09,09,08,07,07,07,06,06,07,07]
[11,10,10,10,09,08,08,08,07,06,07,08]

This does not work in my case, because I'm just moving rows(removing&inserting) in a ListView, but not replacing.

What I actually need is a minimal moving list:

1. Take Emma and Put behind Daniel
2. Take Andrew and Put behind Daniel
3. Take Kate and Put behind Daniel
4. Take Alan and Put behind Daniel
5. Take Tom and Put behind Daniel
6. Take Sandra and Put behind Daniel
7. Take Paul and Put behind Daniel
8. Take Carl and Put behind Sophia

Where:

• Take = Remove
• Put = Insert
• Take&Put = Move

Update 2

Task is solved with permutation cycles.

Answer 1

One of the fundamental properties of permutations is that every permutation can be written as the product of disjoint cycles. So you can factor the final permutation into disjoint cycles and shift the elements in each cycle. Shifting the elements of a cycle is relatively simple.

Answer 2

You can do this using https://en.wikipedia.org/wiki/Bubble_sort, which uses only swapping operations to sort a list. It works by checking whether $2$ adjacent elements are in the right order, and swapping them if they are not. It goes through the list swapping items until the list is entirely sorted. Bubble sort is not the most efficient algorithm ($O(n^{2})$ average), but it'll work for your purposes.

Answer 3

There is a family of algorithms around minimal string edit distance. They generalize for all types of strings where alphabets come from a finite set. In your case, the alphabets are indices into an array (which contains strings).

You can use an algorithm for computing the minimum string edit distance (and some also list the edits that result in that distance) between two strings.

References:

Minimum Edit Distance: https://web.stanford.edu/class/cs124/lec/med.pdf

A Faster Algorithm Computing String Edit Distances: https://core.ac.uk/download/pdf/82758708.pdf

String Edit Distance: https://people.cs.umass.edu/~mccallum/courses/cl2006/lect4-stredit.pdf