我正在寻找以下问题的解决方案：
给定一个数组“a”和一个数组“b”，找到一组操作，当应用于“a”时，将“a”转换为“b”。
例如，鉴于我有：
a = [1,2,3]
b = [3,2,4]
c = transmute(a, b)
我现在希望 c 包含以下内容：
[["remove", 0], ["add", 2, 4], ["swap", 0, 1]]
按照给定的顺序在“a”上添加这些操作应该会产生“b”：
[1,2,3] => [2,3] => [2,3,4] => [3,2,4]
这是 Ruby 中一个非常幼稚的实现：https ://gist.github.com/4455256 。这个假设数组中没有重复项（这不是一个好的假设）。我认为它也是 O(n²)，如果有更高性能的东西会很好。
有没有已知的算法可以做到这一点？我可以做任何进一步的阅读吗？您对如何改进有什么建议吗？
您可以分阶段进行以解决此问题。根据我的想法，应该有3个阶段。O(N) 解决方案将是可能的。
将数组 A 复制到数组 C 中，将数组 B 复制到数组 D 中。
因为，步骤 1、2、4 相当简单。我将解释如何使用掉期的顺序。让我们举个例子。如果当前我们的数组 C 看起来像 1,3,2 而 D 看起来像 3,2,1。我们将 D 中每个索引处的值与 C 中的相应值进行比较。如果它们不同，则我们标记从 C 中的元素到 D 中的元素的有向边。因此，在索引 0 处，C 有 1，D 有 3。它们是不同，因此我们绘制从 1 到 3 的有向边。1->3。同样，我们为索引 1 绘制一条从 3 到 2 的边。为索引 2 绘制一条从 2 到 1 的边。
这将我们引向DAG。你可以试试 DFS 之类的各种东西，看看，我将在这里说明结果。没有。交换数将是（图中的节点数 - 1）。图的 DFS 遍历将告诉交换发生的顺序。
注意：如果数组中有重复的元素，则需要更多的簿记，但相同的解决方案将起作用。
如果您无法通过 DAG 交换算法的阶段。请看@handcraftsman 引用的问题，即字符串转置算法。它针对同一问题提出了类似的方法。
这是一个解决方案：
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
这是一个快速的 C# 实现：
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);
}
示例用法：
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);
}
}
样本输出：
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
以下是上面示例中明显的一些低效率：它交换将要删除的令牌它删除然后重新添加令牌
这个答案可能有用： 字符串转置算法
看看编辑距离算法