列出一个字符串/整数的所有排列

Question

在编程面试中（虽然我没有面试经验），一个常见的任务就是将字符串或整数列出所有可能的排列。

有没有一个实现示例和解决此类问题的逻辑呢？

我看过一些代码片段，但它们没有很好的注释/解释，因此很难跟踪。

- GurdeepS

---

这里有一个关于排列组合的问题包括一个图表和一些很好的解释性答案，但不是关于C#的。 - user unknown

Answer 1

首先：当然会有 递归 的味道！

既然你想知道原理，我尽力用人类语言解释了它。我认为大多数情况下递归非常简单，你只需要掌握两个步骤：

1. 第一步
2. 所有其他步骤（均使用相同的逻辑）

用人类语言说：

简而言之：

1. 1个元素的排列是1个元素。
   
2. 元素集合的排列是每个元素与其余元素的每个排列连接在一起组成的列表。
   

例如：

如果集合只有一个元素 ->
返回它本身。
perm(a) -> a

如果集合有两个字符：对于其中的每个元素：返回该元素，并连接其余元素的排列，如下所示：

perm(ab) ->

a + perm(b) -> ab

b + perm(a) -> ba

继续：对于集合中的每个字符：返回与其余集合的排列连接在一起的字符。

perm(abc) ->

a + perm(bc) --> abc, acb

b + perm(ac) --> bac, bca

c + perm(ab) --> cab, cba

perm(abc...z) -->

a + perm(...), b + perm(....)
....

我在http://www.programmersheaven.com/mb/Algorithms/369713/369713/permutation-algorithm-help/上找到了伪代码：

makePermutations(permutation) {
  if (length permutation < required length) {
    for (i = min digit to max digit) {
      if (i not in permutation) {
        makePermutations(permutation+i)
      }
    }
  }
  else {
    add permutation to list
  }
}

C#

以下内容来自 http://radio.weblogs.com/0111551/stories/2002/10/14/permutations.html，这是一个比较详细的例子（由于标记为C#），函数接受一串字符并输出该字符串所有可能的排列组合。例如，如果提供了“ABC”，则应该输出：

ABC、ACB、BAC、BCA、CAB和CBA。

代码：

class Program
{
    private static void Swap(ref char a, ref char b)
    {
        if (a == b) return;

        var temp = a;
        a = b;
        b = temp;
    }

    public static void GetPer(char[] list)
    {
        int x = list.Length - 1;
        GetPer(list, 0, x);
    }

    private static void GetPer(char[] list, int k, int m)
    {
        if (k == m)
        {
            Console.Write(list);
        }
        else
            for (int i = k; i <= m; i++)
            {
                   Swap(ref list[k], ref list[i]);
                   GetPer(list, k + 1, m);
                   Swap(ref list[k], ref list[i]);
            }
    }

    static void Main()
    {
        string str = "sagiv";
        char[] arr = str.ToCharArray();
        GetPer(arr);
    }
}

- Peter

---

为了让意思更加清晰，我会将k称为“递归深度”，将m称为“最大深度”。 - Nerf Herder

第二次交换（Swap(ref list[k], ref list[i]);）是不必要的。 - dance2die

谢谢您提供的解决方案。我已经根据它创建了这个fiddle（https://dotnetfiddle.net/oTzihw），并进行了适当的命名，而不是使用k和m。 就我所理解的算法而言，由于您在原地编辑原始数组，因此需要第二次交换（以进行回溯）。 - Andrew

一个小细节：看起来使用临时缓冲变量实现 Swap 方法比使用 XOR 更好（https://www.dotnetperls.com/swap）。 - Sergioet

当字符串中有重复字符时，这段代码无法正常工作。如何避免在字符串中出现重复字符。 - chindirala sampath kumar

通过使用 C# 7 元组，您可以使交换变得更加优雅：(a[x], a[y]) = (a[y], a[x]); - Darren

Answer 2

如果允许使用LINQ，那么这只需要两行代码。请查看我在这里的回答。 编辑 下面是一个通用函数，可以从T类型的列表中返回所有排列（而非组合）：

static IEnumerable<IEnumerable<T>>
    GetPermutations<T>(IEnumerable<T> list, int length)
{
    if (length == 1) return list.Select(t => new T[] { t });

    return GetPermutations(list, length - 1)
        .SelectMany(t => list.Where(e => !t.Contains(e)),
            (t1, t2) => t1.Concat(new T[] { t2 }));
}

例子：

IEnumerable<IEnumerable<int>> result =
    GetPermutations(Enumerable.Range(1, 3), 3);

输出 - 一个整数列表的列表：

{1,2,3} {1,3,2} {2,1,3} {2,3,1} {3,1,2} {3,2,1}

由于该功能使用了LINQ，因此需要.NET 3.5或更高版本。

- Pengyang

---

排列组合是两个不同的概念。虽然相似，但您在那里给出的答案似乎回答了一个与一组元素的所有排列不同的问题。 - Shawn Kovac

@ShawnKovac，谢谢你指出这一点！我已经将代码从组合更新为排列。 - Pengyang

@Pengyang，我看了你的另一个答案，它对我帮助很大，但我有另一种情况，不知道你是否指出了正确的解决方法。我想找到单词“HALLOWEEN”的所有排列组合，但发现我还想在结果集中包括两个'L'和两个'E'。在我的迭代中，我使用你的方法循环迭代并逐渐增加长度（length++），并期望在给定单词HALLOWEEN（9个字符）的完整长度时得到9个字符长的结果...但事实并非如此：我只得到7个字符（1个L和1个E被省略）。 - MegaMark

这个函数要求元素是唯一的。请尝试使用以下代码：const string s = "HALLOWEEN"; var result = GetPermutations(Enumerable.Range(0, s.Length), s.Length).Select(t => t.Select(i => s[i])); - Pengyang

虽然我自己是LINQ的粉丝，但我担心这个解决方案的性能非常糟糕。这可能是由于惰性评估或所有迭代器开销引起的，我不知道，但我进行了一些时间测量，将此解决方案与Yurik的实现进行比较，他的实现速度大约快了40倍。 - KnorxThieus

Answer 3

我找到了解决方案。它是用Java编写的，但我已将其转换为C＃。希望它能帮助你。

以下是C#代码：

static void Main(string[] args)
{
    string str = "ABC";
    char[] charArry = str.ToCharArray();
    Permute(charArry, 0, 2);
    Console.ReadKey();
}

static void Permute(char[] arry, int i, int n)
{
    int j;
    if (i==n)
        Console.WriteLine(arry);
    else
    {
        for(j = i; j <=n; j++)
        {
            Swap(ref arry[i],ref arry[j]);
            Permute(arry,i+1,n);
            Swap(ref arry[i], ref arry[j]); //backtrack
        }
    }
}

static void Swap(ref char a, ref char b)
{
    char tmp;
    tmp = a;
    a=b;
    b = tmp;
}

- user3277651

---

它是从其他语言移植过来的吗？图片绝对值得加一分，因为它确实增加了价值。然而，代码本身似乎有一定的改进潜力。有些小部分是不需要的，但最重要的是，当我们发送某些东西并对其进行处理而不是提供输入参数并获取返回值时，我会感到这种C++的感觉。事实上，我使用了你的图片来实现一个类似于C#风格的C#代码（当然是我的个人感觉），它帮助了我很多，所以当我发布它时，我肯定会从你这里偷取它（并为此给你信用）。 - Konrad Viltersten

自从C#引入元组以来，它也像Python一样支持交换。 - GNUSupporter 8964民主女神 地下教會

Answer 4

递归并不是必需的，这里提供了关于该解决方案的良好信息。

var values1 = new[] { 1, 2, 3, 4, 5 };

foreach (var permutation in values1.GetPermutations())
{
    Console.WriteLine(string.Join(", ", permutation));
}

var values2 = new[] { 'a', 'b', 'c', 'd', 'e' };

foreach (var permutation in values2.GetPermutations())
{
    Console.WriteLine(string.Join(", ", permutation));
}

Console.ReadLine();

我已经使用这个算法多年了，它的时间和空间复杂度都是O(N)，用于计算每个排列。

public static class SomeExtensions
{
    public static IEnumerable<IEnumerable<T>> GetPermutations<T>(this IEnumerable<T> enumerable)
    {
        var array = enumerable as T[] ?? enumerable.ToArray();

        var factorials = Enumerable.Range(0, array.Length + 1)
            .Select(Factorial)
            .ToArray();

        for (var i = 0L; i < factorials[array.Length]; i++)
        {
            var sequence = GenerateSequence(i, array.Length - 1, factorials);

            yield return GeneratePermutation(array, sequence);
        }
    }

    private static IEnumerable<T> GeneratePermutation<T>(T[] array, IReadOnlyList<int> sequence)
    {
        var clone = (T[]) array.Clone();

        for (int i = 0; i < clone.Length - 1; i++)
        {
            Swap(ref clone[i], ref clone[i + sequence[i]]);
        }

        return clone;
    }

    private static int[] GenerateSequence(long number, int size, IReadOnlyList<long> factorials)
    {
        var sequence = new int[size];

        for (var j = 0; j < sequence.Length; j++)
        {
            var facto = factorials[sequence.Length - j];

            sequence[j] = (int)(number / facto);
            number = (int)(number % facto);
        }

        return sequence;
    }

    static void Swap<T>(ref T a, ref T b)
    {
        T temp = a;
        a = b;
        b = temp;
    }

    private static long Factorial(int n)
    {
        long result = n;

        for (int i = 1; i < n; i++)
        {
            result = result * i;
        }

        return result;
    }
}

- Najera

---

开箱即用！ - revobtz

也许我不理解O(n)符号。N是否指的是需要多少个“内部循环”才能使您的算法正常工作？在我看来，如果您有N个数字，似乎它是O(N * N！)（因为它必须执行N次交换）。此外，它还必须执行大量的数组复制。这段代码“整洁”，但我不会使用它。 - eric frazer

每个排列只使用一个数组副本，序列的时间复杂度为O(N-1)，交换的时间复杂度为O(N)，总时间复杂度为O(N)。我仍在生产环境中使用这个算法，但进行了重构，只生成一个排列，如：GetPermutation(i)，其中0 <= i <= N!-1。如果有更好性能的算法，我会很高兴使用它，所以请随意提供更好的参考，大多数替代方案在内存中使用O(N!)，所以您也可以检查一下。 - Najera

Answer 5

class Program
{
    public static void Main(string[] args)
    {
        Permutation("abc");
    }

    static void Permutation(string rest, string prefix = "")
    {
        if (string.IsNullOrEmpty(rest)) Console.WriteLine(prefix);

        // Each letter has a chance to be permutated
        for (int i = 0; i < rest.Length; i++)
        {                
            Permutation(rest.Remove(i, 1), prefix + rest[i]);
        }
    }
}

- Meng Xue

Answer 6

这是一个略有修改的 C# 版本，可以在任何类型的数组中生成所需的排列。

    // USAGE: create an array of any type, and call Permutations()
    var vals = new[] {"a", "bb", "ccc"};
    foreach (var v in Permutations(vals))
        Console.WriteLine(string.Join(",", v)); // Print values separated by comma


public static IEnumerable<T[]> Permutations<T>(T[] values, int fromInd = 0)
{
    if (fromInd + 1 == values.Length)
        yield return values;
    else
    {
        foreach (var v in Permutations(values, fromInd + 1))
            yield return v;

        for (var i = fromInd + 1; i < values.Length; i++)
        {
            SwapValues(values, fromInd, i);
            foreach (var v in Permutations(values, fromInd + 1))
                yield return v;
            SwapValues(values, fromInd, i);
        }
    }
}

private static void SwapValues<T>(T[] values, int pos1, int pos2)
{
    if (pos1 != pos2)
    {
        T tmp = values[pos1];
        values[pos1] = values[pos2];
        values[pos2] = tmp;
    }
}

- Yuri Astrakhan

---

这个实现有一个小问题：只有在你不尝试存储枚举值时它才能正常工作。如果你尝试做类似于 Permutations(vals).ToArray() 的事情，那么你最终会得到 N 个对同一数组的引用。如果你想要能够存储结果，你必须手动创建一个副本。例如：Permutations(values).Select(v => (T[])v.Clone())。 - Pharap

我已经在非常大的排列（数千万）上测试了这种方法。它需要非常谨慎的使用。它在速度和内存使用方面完全超越了其他解决方案。 - undefined

Answer 7

首先，集合有排列，而不是字符串或整数，因此我假设您的意思是“字符串中的字符集合”。

请注意，大小为n的集合具有n！个n排列。

以下伪代码（来自维基百科），使用k = 1…n!将给出所有排列：

function permutation(k, s) {
    for j = 2 to length(s) {
        swap s[(k mod j) + 1] with s[j]; // note that our array is indexed starting at 1
        k := k / j; // integer division cuts off the remainder
    }
    return s;
}

以下是相应的Python代码（针对从0开始的数组索引）：

def permutation(k, s):
    r = s[:]
    for j in range(2, len(s)+1):
        r[j-1], r[k%j] = r[k%j], r[j-1]
        k = k/j+1
    return r

- Can Berk Güder

---

这是什么语言？问题标记为C#。我不知道 k := k / j; 是什么意思。 - Shawn Kovac

Answer 8

我认为FBryant87的方法很简单易懂。然而，像其他“解决方案”一样，它无法提供包含相同数字的整数的所有排列方式，例如656123。请看下面这行代码：

var tail = chars.Except(new List<char>(){c});

使用Except将导致所有出现的内容都被删除，例如当c = 6时，两个数字被删除，我们留下了5123。由于我尝试的解决方案都没有解决这个问题，所以我决定基于FBryant87的代码来尝试解决它。以下是我的解决方案：

private static List<string> FindPermutations(string set)
    {
        var output = new List<string>();
        if (set.Length == 1)
        {
            output.Add(set);
        }
        else
        {
            foreach (var c in set)
            {
                // Remove one occurrence of the char (not all)
                var tail = set.Remove(set.IndexOf(c), 1);
                foreach (var tailPerms in FindPermutations(tail))
                {
                    output.Add(c + tailPerms);
                }
            }
        }
        return output;
    }

我只是使用.Remove和.IndexOf删除了第一个找到的出现。对于我的用法来说，似乎达到了预期的效果。我相信它可以更加巧妙。

需要注意的一点是：结果列表可能包含重复项，因此请确保您要么使该方法返回例如 HashSet，或在返回后使用任何方法删除重复项。

- hug

---

运行起来非常完美，这是我发现的第一个能够处理重复字符+1的程序。 - Jack Casey

Answer 9

以下是一个使用递归的C#简单解决方案：

void Main()
{
    string word = "abc";
    WordPermuatation("",word);
}

void WordPermuatation(string prefix, string word)
{
    int n = word.Length;
    if (n == 0) { Console.WriteLine(prefix); }
    else
    {
        for (int i = 0; i < n; i++)
        {
            WordPermuatation(prefix + word[i],word.Substring(0, i) + word.Substring(i + 1, n - (i+1)));
        }
    }
}

- raghavankl

Answer 10

这里是一个纯函数式的F#实现：

let factorial i =
    let rec fact n x =
        match n with
        | 0 -> 1
        | 1 -> x
        | _ -> fact (n-1) (x*n)
    fact i 1

let swap (arr:'a array) i j = [| for k in 0..(arr.Length-1) -> if k = i then arr.[j] elif k = j then arr.[i] else arr.[k] |]

let rec permutation (k:int,j:int) (r:'a array) =
    if j = (r.Length + 1) then r
    else permutation (k/j+1, j+1) (swap r (j-1) (k%j))

let permutations (source:'a array) = seq { for k = 0 to (source |> Array.length |> factorial) - 1 do yield permutation (k,2) source }

通过改变交换（swap）以利用CLR数组的可变性，可以大大提高性能，但是在某些情况下，与源数组相关的实现在线程安全方面可能是值得考虑的。 此外，对于具有超过16个元素的数组，int必须被替换为具有更高/任意精度的类型，因为17的阶乘会导致int32溢出。

- em70