C# 列出字符串/整数的所有排列

Listing all permutations of a string/integer

提问by GurdeepS

A common task in programming interviews (not from my experience of interviews though) is to take a string or an integer and list every possible permutation.

编程面试中的一个常见任务（虽然不是根据我的面试经验）是获取一个字符串或一个整数并列出所有可能的排列。

Is there an example of how this is done and the logic behind solving such a problem?

有没有一个例子说明这是如何完成的以及解决这个问题背后的逻辑？

I've seen a few code snippets but they weren't well commented/explained and thus hard to follow.

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

采纳答案by Peter

First of all: it smells like recursionof course!

首先：它当然闻起来像递归！

Since you also wanted to know the principle, I did my best to explain it human language. I think recursion is very easy most of the times. You only have to grasp two steps:

既然你也想知道原理，我就尽量用人话解释了。我认为递归在大多数情况下非常容易。你只需要掌握两个步骤：

1. The first step
2. All the other steps (all with the same logic)

1. 第一步
2. 所有其他步骤（都具有相同的逻辑）

In human language:

用人类语言：

In short:
1. The permutation of 1 element is one element.
2. The permutation of a set of elements is a list each of the elements, concatenated with every permutation of the other elements.

Example:

If the set just has one element -->
return it.
perm(a) -> a

If the set has two characters: for each element in it: return the element, with the permutation of the rest of the elements added, like so:

perm(ab) ->

a + perm(b) -> ab

b + perm(a) -> ba

Further: for each character in the set: return a character, concatenated with a perumation of > the rest of the set

perm(abc) ->

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

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

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

perm(abc...z) -->

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

简而言之：
1. 1 个元素的排列是一个元素。
2. 一组元素的排列是每个元素的列表，与其他元素的每个排列连接。

例子：

如果集合只有一个元素 -->
返回它。
烫发（a）-> a

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

烫发（ab）->

a + 烫发(b) -> ab

b + 烫发(a) -> ba

进一步：对于集合中的每个字符：返回一个字符，与 > 其余部分的排列连接

烫发（ABC）->

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

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

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

烫发（abc...z）-->

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

I found the pseudocodeon http://www.programmersheaven.com/mb/Algorithms/369713/369713/permutation-algorithm-help/:

我在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#

C＃

OK, and something more elaborate (and since it is tagged c #), from http://radio.weblogs.com/0111551/stories/2002/10/14/permutations.html: Rather lengthy, but I decided to copy it anyway, so the post is not dependent on the original.

好的，还有更详细的内容（因为它被标记为 c#），来自http://radio.weblogs.com/0111551/stories/2002/10/14/permutations.html：相当冗长，但我决定复制它无论如何，所以帖子不依赖于原件。

The function takes a string of characters, and writes down every possible permutation of that exact string, so for example, if "ABC" has been supplied, should spill out:

该函数接受一串字符，并记下该确切字符串的所有可能排列，例如，如果提供了“ABC”，则应溢出：

ABC, ACB, BAC, BCA, CAB, CBA.

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

Code:

代码：

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);
    }
}

回答by Can Berk Güder

First of all, sets have permutations, not strings or integers, so I'll just assume you mean "the set of characters in a string."

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

Note that a set of size n has n! n-permutations.

请注意，一组大小为 n 的集合有 n！n-排列。

The following pseudocode (from Wikipedia), called with k = 1...n! will give all the permutations:

以下伪代码（来自维基百科），调用 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;
}

Here's the equivalent Python code (for 0-based array indexes):

这是等效的 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

回答by moinudin

Here's a good article covering three algorithms for finding all permutations, including one to find the next permutation.

这是一篇很好的文章，涵盖了用于查找所有排列的三种算法，包括用于查找下一个排列的算法。

http://www.cut-the-knot.org/do_you_know/AllPerm.shtml

http://www.cut-the-knot.org/do_you_know/AllPerm.shtml

C++ and Python have built-in next_permutationand itertools.permutationsfunctions respectively.

C++ 和 Python 分别内置了next_permutation和itertools.permutations函数。

回答by em70

Here's a purely functional F# implementation:

这是一个纯函数式 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 }

Performance can be greatly improved by changing swap to take advantage of the mutable nature of CLR arrays, but this implementation is thread safe with regards to the source array and that may be desirable in some contexts. Also, for arrays with more than 16 elements int must be replaced with types with greater/arbitrary precision as factorial 17 results in an int32 overflow.

通过更改交换以利用 CLR 数组的可变性质，可以极大地提高性能，但这种实现对于源数组是线程安全的，并且在某些上下文中可能是可取的。此外，对于超过 16 个元素的数组，int 必须替换为具有更高/任意精度的类型，因为阶乘 17 会导致 int32 溢出。

回答by em70

void permute (char *str, int ptr) {
  int i, len;
  len = strlen(str);
  if (ptr == len) {
    printf ("%s\n", str);
    return;
  }

  for (i = ptr ; i < len ; i++) {
    swap (&str[ptr], &str[i]);
    permute (str, ptr + 1);
    swap (&str[ptr], &str[i]);
  }
}

You can write your swap function to swap characters.
This is to be called as permute(string, 0);

您可以编写交换函数来交换字符。
这将被称为 permute(string, 0);

回答by Amit Patel

Here is the function which will print all permutaion. This function implements logic Explained by peter.

这是将打印所有排列的函数。这个函数实现了彼得解释的逻辑。

public class Permutation
{
    //http://www.java2s.com/Tutorial/Java/0100__Class-Definition/RecursivemethodtofindallpermutationsofaString.htm

    public static void permuteString(String beginningString, String endingString)
    {           

        if (endingString.Length <= 1)
            Console.WriteLine(beginningString + endingString);
        else
            for (int i = 0; i < endingString.Length; i++)
            {

                String newString = endingString.Substring(0, i) + endingString.Substring(i + 1);

                permuteString(beginningString + endingString.ElementAt(i), newString);

            }
    }
}

    static void Main(string[] args)
    {

        Permutation.permuteString(String.Empty, "abc");
        Console.ReadLine();

    }

回答by Pengyang

It's just two lines of code if LINQ is allowed to use. Please see my answer here.

如果允许使用 LINQ，只需两行代码。请在此处查看我的回答。

EDIT

编辑

Here is my generic function which can return all the permutations (not combinations) from a list of T:

这是我的通用函数，它可以从 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 }));
}

Example:

例子：

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

Output - a list of integer-lists:

输出 - 整数列表列表：

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

As this function uses LINQ so it requires .net 3.5 or higher.

由于此函数使用 LINQ，因此它需要 .net 3.5 或更高版本。

回答by priyank

The below is my implementation of permutation . Don't mind the variable names, as i was doing it for fun :)

下面是我对 permutation 的实现。不要介意变量名称，因为我这样做是为了好玩:)

class combinations
{
    static void Main()
    {

        string choice = "y";
        do
        {
            try
            {
                Console.WriteLine("Enter word :");
                string abc = Console.ReadLine().ToString();
                Console.WriteLine("Combinatins for word :");
                List<string> final = comb(abc);
                int count = 1;
                foreach (string s in final)
                {
                    Console.WriteLine("{0} --> {1}", count++, s);
                }
                Console.WriteLine("Do you wish to continue(y/n)?");
                choice = Console.ReadLine().ToString();
            }
            catch (Exception exc)
            {
                Console.WriteLine(exc);
            }
        } while (choice == "y" || choice == "Y");
    }

    static string swap(string test)
    {
        return swap(0, 1, test);
    }

    static List<string> comb(string test)
    {
        List<string> sec = new List<string>();
        List<string> first = new List<string>();
        if (test.Length == 1) first.Add(test);
        else if (test.Length == 2) { first.Add(test); first.Add(swap(test)); }
        else if (test.Length > 2)
        {
            sec = generateWords(test);
            foreach (string s in sec)
            {
                string init = s.Substring(0, 1);
                string restOfbody = s.Substring(1, s.Length - 1);

                List<string> third = comb(restOfbody);
                foreach (string s1 in third)
                {
                    if (!first.Contains(init + s1)) first.Add(init + s1);
                }


            }
        }

        return first;
    }

    static string ShiftBack(string abc)
    {
        char[] arr = abc.ToCharArray();
        char temp = arr[0];
        string wrd = string.Empty;
        for (int i = 1; i < arr.Length; i++)
        {
            wrd += arr[i];
        }

        wrd += temp;
        return wrd;
    }

    static List<string> generateWords(string test)
    {
        List<string> final = new List<string>();
        if (test.Length == 1)
            final.Add(test);
        else
        {
            final.Add(test);
            string holdString = test;
            while (final.Count < test.Length)
            {
                holdString = ShiftBack(holdString);
                final.Add(holdString);
            }
        }

        return final;
    }

    static string swap(int currentPosition, int targetPosition, string temp)
    {
        char[] arr = temp.ToCharArray();
        char t = arr[currentPosition];
        arr[currentPosition] = arr[targetPosition];
        arr[targetPosition] = t;
        string word = string.Empty;
        for (int i = 0; i < arr.Length; i++)
        {
            word += arr[i];

        }

        return word;

    }
}

回答by Yurik

Slightly modified version in C# that yields needed permutations in an array of ANY type.

在 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;
    }
}

回答by user2674028

Here is the function which will print all permutations recursively.

这是将递归打印所有排列的函数。

public void Permutations(string input, StringBuilder sb)
    {
        if (sb.Length == input.Length)
        {
            Console.WriteLine(sb.ToString());
            return;
        }

        char[] inChar = input.ToCharArray();

        for (int i = 0; i < input.Length; i++)
        {
            if (!sb.ToString().Contains(inChar[i]))
            {
                sb.Append(inChar[i]);
                Permutations(input, sb);    
                RemoveChar(sb, inChar[i]);
            }
        }
    }

private bool RemoveChar(StringBuilder input, char toRemove)
    {
        int index = input.ToString().IndexOf(toRemove);
        if (index >= 0)
        {
            input.Remove(index, 1);
            return true;
        }
        return false;
    }