Prerequisite:Move To Front Data Transform Algorithm
The main idea behind inverse of MTF Transform:
- To compute inverse of MTF Transform is to undo the MTF Transform and recover the original string. We have with us “input_arr” which is the MTF transform and “n” which is the number of elements in “input_arr”.
- Our task is to maintain an ordered list of characters (a to z, in our example) and read in “ith”element from “input_arr” one at a time.
- Then, taking that element as index j, print “jth” character in the list.
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
Examples:
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 : neveropen
Following is the code for idea explained above:
C++
// C++ program to find Inverse of Move to Front // Transform of a given string #include<bits/stdc++.h>using namespace std;// Takes index of printed character as argument // to bring that character to the front of the list void moveToFront(int index, string &list) { char record[27]; int i = 0; for(; i < list.size(); i++) record[i] = list[i]; // Characters pushed one position right // in the list up until index i = 1; for(; i <= index; i++) list[i] = record[i-1]; // Character at index stored at 0th position list[0] = record[index]; } // Move to Front Decoding void mtfDecode(vector<int> arr, int n) { // Maintains an ordered list of legal symbols string list = "abcdefghijklmnopqrstuvwxyz"; int i; cout << "\nInverse of Move to Front Transform: "; for (i = 0; i < n; i++) { // Printing characters of Inverse MTF as output cout << 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. vector<int> arr = {15, 1, 14, 1, 14, 1}; int n = arr.size(); // Computes Inverse of Move to Front transform // of given text mtfDecode(arr, n); return 0; } // The code is contributed by Nidhi goel. |
C
// 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; } |
Java
import java.util.*;class Main { // Takes index of printed character as argument // to bring that character to the front of the list static void moveToFront(int index, StringBuilder list) { char[] record = new char[list.length()]; list.getChars(0, list.length(), record, 0); // Characters pushed one position right // in the list up until index for (int i = index; i > 0; i--) { list.setCharAt(i, record[i - 1]); } // Character at index stored at 0th position list.setCharAt(0, record[index]); } // Move to Front Decoding static void mtfDecode(List<Integer> arr, int n) { // Maintains an ordered list of legal symbols StringBuilder list = new StringBuilder("abcdefghijklmnopqrstuvwxyz"); System.out.print("\nInverse of Move to Front Transform: "); for (int i = 0; i < n; i++) { // Printing characters of Inverse MTF as output System.out.print(list.charAt(arr.get(i))); // Moves the printed character to the front // of the list moveToFront(arr.get(i), list); } } // Driver program to test functions above public static void main(String[] args) { // MTF transform and number of elements in it. List<Integer> arr = Arrays.asList(15, 1, 14, 1, 14, 1); int n = arr.size(); // Computes Inverse of Move to Front transform // of given text mtfDecode(arr, n); }} |
Python3
# Python3 program to find Inverse of Move to Front # Transform of a given string # Takes index of printed character as argument # to bring that character to the front of the list def move_to_front(index, lst): # Characters pushed one position right # in the list up until index record = lst.copy() lst[1:index+1] = record[:index] # Character at index stored at 0th position lst[0] = record[index]# Move to Front Decoding def mtf_decode(arr): lst = list("abcdefghijklmnopqrstuvwxyz") result = [] for i in arr: result.append(lst[i]) # Moves the printed character to the front # of the list move_to_front(i, lst) return ''.join(result)# Driver program to test functions abovearr = [15, 1, 14, 1, 14, 1]print("Inverse of Move to Front Transform:", mtf_decode(arr))# This code is contributed by Prince |
C#
using System;using System.Collections.Generic;using System.Text;class MainClass { // Takes index of printed character as argument // to bring that character to the front of the list static void moveToFront(int index, StringBuilder list) { char[] record = list.ToString().ToCharArray(); // Characters pushed one position right // in the list up until index for (int i = index; i > 0; i--) { list[i] = record[i - 1]; } // Character at index stored at 0th position list[0] = record[index]; } // Move to Front Decoding static void mtfDecode(List<int> arr, int n) { // Maintains an ordered list of legal symbols StringBuilder list = new StringBuilder("abcdefghijklmnopqrstuvwxyz"); Console.Write("\nInverse of Move to Front Transform: "); for (int i = 0; i < n; i++) { // Printing characters of Inverse MTF as output Console.Write(list[arr[i]]); // Moves the printed character to the front // of the list moveToFront(arr[i], list); } } // Driver program to test functions above public static void Main(string[] args) { // MTF transform and number of elements in it. List<int> arr = new List<int> {15, 1, 14, 1, 14, 1}; int n = arr.Count; // Computes Inverse of Move to Front transform // of given text mtfDecode(arr, n); }} |
Javascript
// JavaScript program for the above approach function move_to_front(index, lst) { // Characters pushed one position right // in the list up until index const record = lst.slice(); lst.splice(1, index, ...record.slice(0, index)); // Character at index stored at 0th position lst[0] = record[index];}function mtf_decode(arr) { const lst = "abcdefghijklmnopqrstuvwxyz".split(""); const result = []; for (let i = 0; i < arr.length; i++) { const charIndex = arr[i]; result.push(lst[charIndex]); // Moves the printed character to the front // of the list move_to_front(charIndex, lst); } return result.join("");}const arr = [15, 1, 14, 1, 14, 1];console.log("Inverse of Move to Front Transform:", mtf_decode(arr));// This code is contributed by adityashatmfh |
Output
Inverse of Move to Front Transform: panama
Time Complexity: O(n^2)
Auxiliary Space: O(n), size of the given array.
Exercise: Implement MTF encoding and decoding together in one program and check if the original message is recovered.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
