Array mutation algorithm

Question

I am looking for a solution to the following problem:

Given the array "a" and the array "b", find the set of operations that, when applied to "a", converts "a" to "b".

So, for example, if I have:

a = [1,2,3] b = [3,2,4] c = transmute(a, b) 

Now I expected c to contain something like:

 [["remove", 0], ["add", 2, 4], ["swap", 0, 1]] 

Adding these operations to "a" in the given order should produce "b":

 [1,2,3] => [2,3] => [2,3,4] => [3,2,4] 

Here's a very naive implementation in Ruby: https://gist.github.com/4455256 . This assumes there are no duplicates in the array (which is not a good guess). It is also O (n²), I think, and it would be nice if there was something more perfect.

Is there any known algorithm? Any further reading I can do? Do you have any suggestions on how this can be improved?

Answer 1

You can follow the steps to resolve this issue. According to what I thought, there should be 3 steps. Perhaps the solution is O (N).

Copy array A to array C and array B to array D.

• Now compare the 2 arrays of C and D. Remove the elements in C that are not in D. These are the elements that need to be removed from array A. If we use the HashMap for this step, then this can be done in O (N)
• Compare C and D again, remove the elements from D that are not in C. These elements will essentially be the elements that we will add to array A.
• So, now we have 2 arrays - C and D, which essentially have the same elements . We only need to see how we can change these elements so that they look the same .
• Once they look the same, we can add the missing elements from A to D. Add the elements you removed in step 2 back to array D. They can be added in the correct order compared to the original array A.

Since steps 1,2,4 are quite simple. I will explain how to come with the order of swaps . Let's take an example. If at present our array C looks like 1,3,2, and D looks like 3,2,1. We compare the value at each index in D with the corresponding value in C. If they are different, then we mark the directed edge from the element in C to the element in D. So, at index 0, C has 1 and D has 3. They are different, so we draw a directed edge from 1 to 3. 1-> 3. Similarly, we draw an edge from 3 to 2 for index 1. And the edge from 2 to 1 for index 2.

This brings us to the DAG . You can try various things, such as DFS and see, I just indicate the result here. Not. there will be swaps (the number of nodes on the chart is 1) . Bypassing the DFS chart will indicate the order in which swaps will be executed .

Note. If the arrays have duplicate elements, then a little more accounting is required, but the same solution will work.

If you can not replace the scene of the algorithm using DAG. Take a look at the question quoted by @handcraftsman, which is a string transposition algorithm . It represents a similar approach to the same problem.

Answer 2

here is one solution:

 get the token-index pairs of all tokens in the source string get the token-index pairs of all tokens in the target string from both sets remove the values that are in the other set. foreach token-index in the source set if the target set has the token at the same location remove it from both sets, this is a match created by a previous swap get the target token at the source index if the source set has the target token (at any index) create a swap command to swap the source token at source index with the target token at its index in the source remove the token-index from the source set remove the target token-index from the target set add a token-index for the target token at the new index to the source set loop without moving to the next token-index create remove commands for any remaining token-indexes in the source set create add commands for any remaining token-indexes in the target set 

here's a quick C # implementation:

 private static IEnumerable<ICommand> GetChangeCommands(string source, string target) { var unmatchedSourceTokens = GetUnmatchedTokenIndexes(source, target); var unmatchedTargetTokens = GetUnmatchedTokenIndexes(target, source); var commands = new List<ICommand>(); foreach (var tokenIndexList in unmatchedSourceTokens) { var sourceToken = tokenIndexList.Key; var sourceStringSourceTokenIndexes = unmatchedSourceTokens[sourceToken]; foreach (var sourceLoopIndex in tokenIndexList.Value.ToList()) { var sourceIndex = sourceLoopIndex; bool swapped; do { swapped = false; if (sourceIndex >= target.Length) { continue; } var targetToken = target[sourceIndex]; if (targetToken == sourceToken) { sourceStringSourceTokenIndexes.Remove(sourceIndex); unmatchedTargetTokens[targetToken].Remove(sourceIndex); continue; } List<int> sourceStringTargetTokenIndexes; if (!unmatchedSourceTokens.TryGetValue(targetToken, out sourceStringTargetTokenIndexes) || !sourceStringTargetTokenIndexes.Any()) { continue; } var targetIndex = sourceStringTargetTokenIndexes.First(); commands.Add(new SwapCommand(sourceIndex, targetIndex)); sourceStringTargetTokenIndexes.RemoveAt(0); sourceStringSourceTokenIndexes.Remove(sourceIndex); sourceStringSourceTokenIndexes.Add(targetIndex); unmatchedTargetTokens[targetToken].Remove(sourceIndex); swapped = true; sourceIndex = targetIndex; } while (swapped); } } var removalCommands = unmatchedSourceTokens .SelectMany(x => x.Value) .Select(x => new RemoveCommand(x)) .Cast<ICommand>() .OrderByDescending(x => x.Index) .ToList(); commands.AddRange(removalCommands); var insertCommands = unmatchedTargetTokens .SelectMany(x => x.Value.Select(y => new InsertCommand(y, x.Key))) .Cast<ICommand>() .OrderBy(x => x.Index) .ToList(); commands.AddRange(insertCommands); return commands; } private static IDictionary<char, List<int>> GetUnmatchedTokenIndexes(string source, string target) { var targetTokenIndexes = target.Select((x, i) => new { Token = x, Index = i }) .ToLookup(x => x.Token, x => x.Index) .ToDictionary(x => x.Key, x => x.ToList()); var distinctSourceTokenIndexes = new Dictionary<char, List<int>>(); foreach (var tokenInfo in source.Select((x, i) => new { Token = x, Index = i })) { List<int> indexes; if (!targetTokenIndexes.TryGetValue(tokenInfo.Token, out indexes) || !indexes.Contains(tokenInfo.Index)) { if (!distinctSourceTokenIndexes.TryGetValue(tokenInfo.Token, out indexes)) { indexes = new List<int>(); distinctSourceTokenIndexes.Add(tokenInfo.Token, indexes); } indexes.Add(tokenInfo.Index); } } return distinctSourceTokenIndexes; } internal class InsertCommand : ICommand { private readonly char _token; public InsertCommand(int index, char token) { Index = index; _token = token; } public int Index { get; private set; } public string Change(string input) { var chars = input.ToList(); chars.Insert(Index, _token); return new string(chars.ToArray()); } public override string ToString() { return string.Format("[\"add\", {0}, '{1}']", Index, _token); } } internal class RemoveCommand : ICommand { public RemoveCommand(int index) { Index = index; } public int Index { get; private set; } public string Change(string input) { var chars = input.ToList(); chars.RemoveAt(Index); return new string(chars.ToArray()); } public override string ToString() { return string.Format("[\"remove\", {0}]", Index); } } internal class SwapCommand : ICommand { private readonly int _targetIndex; public SwapCommand(int sourceIndex, int targetIndex) { Index = sourceIndex; _targetIndex = targetIndex; } public int Index { get; private set; } public string Change(string input) { var chars = input.ToArray(); var temp = chars[Index]; chars[Index] = chars[_targetIndex]; chars[_targetIndex] = temp; return new string(chars); } public override string ToString() { return string.Format("[\"swap\", {0}, {1}]", Index, _targetIndex); } } internal interface ICommand { int Index { get; } string Change(string input); } 

Sample Usage:

 const string source = "123"; const string target = "324"; var commands = GetChangeCommands(source, target); Execute(source, target, commands); private static void Execute(string current, string target, IEnumerable<ICommand> commands) { Console.WriteLine("converting".PadRight(19) + current + " to " + target); foreach (var command in commands) { Console.Write(command.ToString().PadRight(15)); Console.Write(" => "); current = command.Change(current); Console.WriteLine(current); } } 

sample output:

 converting 123 to 324 ["swap", 0, 2] => 321 ["remove", 2] => 32 ["add", 2, '4'] => 324 converting hello to world ["swap", 1, 4] => holle ["remove", 4] => holl ["remove", 2] => hol ["remove", 0] => ol ["add", 0, 'w'] => wol ["add", 2, 'r'] => worl ["add", 4, 'd'] => world converting something to smith ["swap", 1, 2] => smoething ["swap", 2, 6] => smiethong ["swap", 3, 4] => smitehong ["swap", 4, 5] => smitheong ["remove", 8] => smitheon ["remove", 7] => smitheo ["remove", 6] => smithe ["remove", 5] => smith converting something to sightseeing ["swap", 1, 6] => simethong ["swap", 6, 3] => simotheng ["swap", 3, 5] => simhtoeng ["swap", 2, 8] => sightoenm ["remove", 8] => sightoen ["remove", 7] => sightoe ["remove", 5] => sighte ["add", 5, 's'] => sightse ["add", 7, 'e'] => sightsee ["add", 8, 'i'] => sightseei ["add", 9, 'n'] => sightseein ["add", 10, 'g'] => sightseeing 

here are some of the drawbacks obvious in the above samples: it changes the tokens that will be deleted it deletes and then re-adds the tokens

Answer 3

This answer may be useful: a string transposition algorithm

Take a look at distance editing algorithms