Invertir la transformación Mover al frente

Requisito previo: Algoritmo de transformación de datos Mover al frente 

La idea principal detrás de la inversa de MTF Transform: 

1. Calcular el inverso de MTF Transform es deshacer MTF Transform y recuperar la string original. Tenemos con nosotros «input_arr» que es la transformación MTF y «n» que es el número de elementos en «input_arr» . 
2. Nuestra tarea es mantener una lista ordenada de caracteres (de la a a la z, en nuestro ejemplo) y leer el elemento «ith» de «input_arr» uno a la vez. 
3. Luego, tomando ese elemento como índice j , imprima el carácter «jth» en la lista.

Illustration for "[15 1 14 1 14 1]"
List initially contains English alphabets in order.
We move characters at indexes depicted by input 
to front of the list one by one.

input arr chars   output str  list
15                p           abcdefghijklmnopqrstuvwxyz
1                 pa          pabcdefghijklmnoqrstuvwxyz
14                pan         apbcdefghijklmnoqrstuvwxyz
1                 pana        napbcdefghijklmoqrstuvwxyz
14                panam       anpbcdefghijklmoqrstuvwxyz
1                 panama      manpbcdefghijkloqrstuvwxyz

Ejemplos:

Input : arr[] = {15, 1, 14, 1, 14, 1}
Output : panama

Input : arr[] = {6, 5, 0, 10, 18, 8, 15, 18, 
                6, 6, 0, 6, 6};
Output : geeksforgeeks

El siguiente es el código para la idea explicada anteriormente: 

// C program to find Inverse of Move to Front
// Transform of a given string
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
// Takes index of printed character as argument
// to bring that character to the front of the list
void moveToFront(int index, char *list)
{
    char record[27];
    strcpy(record, list);
 
    // Characters pushed one position right
    // in the list up until index
    strncpy(list+1, record, index);
 
    // Character at index stored at 0th position
    list[0] = record[index];
}
 
// Move to Front Decoding
void mtfDecode(int arr[], int n)
{
    // Maintains an ordered list of legal symbols
    char list[] = "abcdefghijklmnopqrstuvwxyz";
 
    int i;
    printf("\nInverse of Move to Front Transform: ");
    for (i = 0; i < n; i++)
    {
        // Printing characters of Inverse MTF as output
        printf("%c", list[arr[i]]);
 
        // Moves the printed character to the front
        // of the list
        moveToFront(arr[i], list);
    }
}
 
// Driver program to test functions above
int main()
{
    // MTF transform and number of elements in it.
    int arr[] = {15, 1, 14, 1, 14, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
 
    // Computes Inverse of Move to Front transform
    // of given text
    mtfDecode(arr, n);
 
    return 0;
}

Inverse of Move to Front Transform: panama

Complejidad de tiempo: O(n^2) 
Espacio auxiliar: O(n), tamaño de la array dada.

Ejercicio: implemente la codificación y decodificación MTF juntas en un programa y verifique si se recupera el mensaje original.