次の問題の解決策を探しています。
配列 "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 によって引用された質問を見てください。これは、同じ問題に対する同様のアプローチを示しています。
ここに1つの解決策があります：
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
上記のサンプルで明らかな非効率性を次に示します。削除されるトークンを交換します。トークンを削除してから再度追加します。
この答えは役に立つかもしれません： 文字列転置アルゴリズム
編集距離アルゴリズムを見てみましょう