C# 列表排列迭代器

引言

在本文中，我将介绍一种紧凑、易于使用的迭代给定序列所有排列的方法。迭代会修改序列的内部顺序，访问所有排列，并最终恢复原始顺序（如果枚举过程完成）。

使用代码

迭代器的实现是递归的；递归终止条件是列表只有一个元素，在这种情况下，它直接返回。在递归情况下，我们迭代 (n) 次，对列表的前 (n-1) 个元素进行递归调用，并在每次迭代后执行右移操作。

由于每次完整的枚举最终会将序列恢复到其原始顺序，因此右移操作保证每次将不同的元素放置在序列的末尾。

public static void RotateRight(IList sequence, int count)
{
    object tmp = sequence[count-1];
    sequence.RemoveAt(count - 1);
    sequence.Insert(0, tmp);
}

public static IEnumerable<IList> Permutate(IList sequence, int count)
{
    if (count == 1) yield return sequence;
    else
    {
        for (int i = 0; i < count; i++)
        {
            foreach (var perm in Permutate(sequence, count - 1))
                yield return perm;
            RotateRight(sequence, count);
        }
    }
}

以下是如何使用此代码来排列整数列表

static void PermutateIntegersTest()
{
    List<int> seq = new List<int>() { 1, 2, 3, 4 };
    foreach (var permu in Permutate(seq, seq.Count))
    {
        foreach (var i in permu)
            Console.Write(i.ToString() + " ");
        Console.WriteLine();
    }
}

或者排列字符串

using System.Linq; // For the ToList() and ToArray() extension methods.

static void PermutateStringTest()
{
    string a = "word";
    foreach (List<char> perm in Permutate(a.ToCharArray().ToList(), a.Length))
    {
        string s = new string(perm.ToArray());
        Console.Write(s + "\t");
    }
    Console.WriteLine();
}

请记住，此实现实际上会修改序列中项目的顺序，如果不需要这样做，则必须在开始迭代之前复制序列。

就这样，尽情享受吧。