anagram算法

Question

这是为文本生成字谜的最佳方法(最多80个字符长度).示例:输入:狗输出狗dgo odg ogd gdo god

我只想到一个回溯解决方案,但如果文本更长,那将需要一段时间.

另一个想法是为字典中的所有单词构建,但问题并不是要求真正的单词.

有人能指出最小时间复杂度解决方案吗？

谢谢!

Answer 1

这是一个直接的实现,以防万一你需要一个:

IEnumerable<List<T>> Permutations<T>(List<T> items)
{
    if (items.Count == 0) yield return new List<T>();

    var copy = new List<T>(items);
    foreach (var i in items)
    {
        copy.Remove(i);
        foreach (var rest in Permutations(copy))
        {
            rest.Insert(0, i);
            yield return rest;
        }
        copy.Insert(0, i);
    }

}

IEnumerable<string> Anagrams(string word)
{
    return Permutations(word.ToCharArray().ToList()).Select(x => new String(x.ToArray()));
}

关于时间复杂性的答案给了Adithya.要了解他们的答案你必须知道有n!n项的= 1*2*...*n排列.我的算法证明了这一点(或基于直接证明)

Answer 2

问题看起来像生成排列列表; (字谜是排列的一个子集,形成一个有意义的词).N!可以使用STL的next_permutation方法按时间顺序生成排列(每个排列的线性时间复杂度); 你可以在这里找到这个算法的讨论:http://marknelson.us/2002/03/01/next-permutation/ ; STL的算法甚至可以处理重复,在这种情况下,天真交换算法失败.

有关生成排列的深入讨论,您可以通过Donald Knuth的TAOCP的Generating all Perumutations部分.