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

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

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

1. 第一步
2. 所有其他步骤(逻辑相同)

在 人类语言:

简而言之: < br/>

1. 1元素的排列是一个元素。 < br/>
2. 一组元素的排列是每个元素的列表，与其他元素的每个排列连接在一起。< br/>

< strong > 示例:

如果集合只有一个元素—— > < br/> 返回。 < br/> 烫(a)-> a

< p > 如果集合有两个字符: for 中的每个元素: 返回 元素的置换 添加的其他元素如下: < br/>

烫发(ab)-> < br/>

A + perm (b)-> AB < br/>

B + perm (a)-> 爸 < br/>

进一步: 对于集合中的每个字符: 返回一个字符，并与集合其余部分的置换连接

Perm (abc)-> < br/>

A + perm (bc)—— > Abc，Acb < br/>

B + perm (ac)—— > 回来，BCA < br/>

C + perm (ab)—— > 出租车，CBA < br/>

Perm (abc... z)—— > < br/>

A + perm (...) ，b + perm (... .) < br/> ... ..

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

该函数接受一个字符串，并写下该字符串的每一种可能的排列，例如，如果提供了“ 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);
}
}

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

注意，一个大小为 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

下面是一个纯功能性的 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 }

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


}

如果允许使用 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或更高版本。

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

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;


}
}

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

下面是递归打印所有排列的函数。

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

我在这里找到了解决办法。它是用 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;
}

class Permutation
{
public static List<string> Permutate(string seed, List<string> lstsList)
{
loopCounter = 0;
// string s="\w{0,2}";
var lstStrs = PermuateRecursive(seed);


Trace.WriteLine("Loop counter :" + loopCounter);
return lstStrs;
}


// Recursive function to find permutation
private static List<string> PermuateRecursive(string seed)
{
List<string> lstStrs = new List<string>();


if (seed.Length > 2)
{
for (int i = 0; i < seed.Length; i++)
{
str = Swap(seed, 0, i);


PermuateRecursive(str.Substring(1, str.Length - 1)).ForEach(
s =>
{
lstStrs.Add(str[0] + s);
loopCounter++;
});
;
}
}
else
{
lstStrs.Add(seed);
lstStrs.Add(Swap(seed, 0, 1));
}
return lstStrs;
}
//Loop counter variable to count total number of loop execution in various functions
private static int loopCounter = 0;


//Non recursive  version of permuation function
public static List<string> Permutate(string seed)
{
loopCounter = 0;
List<string> strList = new List<string>();
strList.Add(seed);
for (int i = 0; i < seed.Length; i++)
{
int count = strList.Count;
for (int j = i + 1; j < seed.Length; j++)
{
for (int k = 0; k < count; k++)
{
strList.Add(Swap(strList[k], i, j));
loopCounter++;
}
}
}
Trace.WriteLine("Loop counter :" + loopCounter);
return strList;
}


private static string Swap(string seed, int p, int p2)
{
Char[] chars = seed.ToCharArray();
char temp = chars[p2];
chars[p2] = chars[p];
chars[p] = temp;
return new string(chars);
}
}

下面是一个稍微简化的 C # 答案。

public static void StringPermutationsDemo()
{
strBldr = new StringBuilder();


string result = Permute("ABCD".ToCharArray(), 0);
MessageBox.Show(result);
}


static string Permute(char[] elementsList, int startIndex)
{
if (startIndex == elementsList.Length)
{
foreach (char element in elementsList)
{
strBldr.Append(" " + element);
}
strBldr.AppendLine("");
}
else
{
for (int tempIndex = startIndex; tempIndex <= elementsList.Length - 1; tempIndex++)
{
Swap(ref elementsList[startIndex], ref elementsList[tempIndex]);


Permute(elementsList, (startIndex + 1));


Swap(ref elementsList[startIndex], ref elementsList[tempIndex]);
}
}


return strBldr.ToString();
}


static void Swap(ref char Char1, ref char Char2)
{
char tempElement = Char1;
Char1 = Char2;
Char2 = tempElement;
}

产出:

1 2 3
1 3 2


2 1 3
2 3 1


3 2 1
3 1 2

下面是我写的一个高水平的例子，说明了彼得给出的 人类语言解释:

    public List<string> FindPermutations(string input)
{
if (input.Length == 1)
return new List<string> { input };
var perms = new List<string>();
foreach (var c in input)
{
var others = input.Remove(input.IndexOf(c), 1);
perms.AddRange(FindPermutations(others).Select(perm => c + perm));
}
return perms;
}

我喜欢 FBryant 87的方法，因为它很简单。不幸的是，它确实像许多其他的“解决方案”一样，没有提供所有的排列或者一个整数，如果它包含相同的数字超过一次。以656123为例。台词是:

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

例如，当 c = 6时，两个数字被删除，我们只剩下5123。由于没有一个解决方案可以解决这个问题，所以我决定尝试用 FBryant 87的代码作为基础来解决这个问题。这是我想到的:

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

我只是使用。拿开。IndexOf.看起来至少对我有用。我相信它可以变得更聪明。

但是需要注意的一点是: 结果列表可能包含重复的内容，所以请确保您要么使用方法返回，例如使用 HashSet，要么使用您喜欢的任何方法在返回后删除重复的内容。

这是我的解决方案，对我来说很容易理解

class ClassicPermutationProblem
{
ClassicPermutationProblem() { }


private static void PopulatePosition<T>(List<List<T>> finalList, List<T> list, List<T> temp, int position)
{
foreach (T element in list)
{
List<T> currentTemp = temp.ToList();
if (!currentTemp.Contains(element))
currentTemp.Add(element);
else
continue;


if (position == list.Count)
finalList.Add(currentTemp);
else
PopulatePosition(finalList, list, currentTemp, position + 1);
}
}


public static List<List<int>> GetPermutations(List<int> list)
{
List<List<int>> results = new List<List<int>>();
PopulatePosition(results, list, new List<int>(), 1);
return results;
}
}


static void Main(string[] args)
{
List<List<int>> results = ClassicPermutationProblem.GetPermutations(new List<int>() { 1, 2, 3 });
}

递归是不必要的，给你是关于这个解决方案的好信息。

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

如果性能和内存是一个问题，我建议使用这种非常有效的实现。根据 维基百科中的堆算法，它应该是最快的。希望它能满足你的需要: —— ！

正如把它与 Linq 实现的10! (包含代码)进行比较:

• 这个: 36288000个项目在235毫克
• < p > Linq: 36288000(以50051毫克为单位)

  using System;
  using System.Collections.Generic;
  using System.Diagnostics;
  using System.Linq;
  using System.Runtime.CompilerServices;
  using System.Text;
  
  
  namespace WpfPermutations
  {
  /// <summary>
  /// EO: 2016-04-14
  /// Generator of all permutations of an array of anything.
  /// Base on Heap's Algorithm. See: https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3
  /// </summary>
  public static class Permutations
  {
  /// <summary>
  /// Heap's algorithm to find all pmermutations. Non recursive, more efficient.
  /// </summary>
  /// <param name="items">Items to permute in each possible ways</param>
  /// <param name="funcExecuteAndTellIfShouldStop"></param>
  /// <returns>Return true if cancelled</returns>
  public static bool ForAllPermutation<T>(T[] items, Func<T[], bool> funcExecuteAndTellIfShouldStop)
  {
  int countOfItem = items.Length;
  
  
  if (countOfItem <= 1)
  {
  return funcExecuteAndTellIfShouldStop(items);
  }
  
  
  var indexes = new int[countOfItem];
  for (int i = 0; i < countOfItem; i++)
  {
  indexes[i] = 0;
  }
  
  
  if (funcExecuteAndTellIfShouldStop(items))
  {
  return true;
  }
  
  
  for (int i = 1; i < countOfItem;)
  {
  if (indexes[i] < i)
  { // On the web there is an implementation with a multiplication which should be less efficient.
  if ((i & 1) == 1) // if (i % 2 == 1)  ... more efficient ??? At least the same.
  {
  Swap(ref items[i], ref items[indexes[i]]);
  }
  else
  {
  Swap(ref items[i], ref items[0]);
  }
  
  
  if (funcExecuteAndTellIfShouldStop(items))
  {
  return true;
  }
  
  
  indexes[i]++;
  i = 1;
  }
  else
  {
  indexes[i++] = 0;
  }
  }
  
  
  return false;
  }
  
  
  /// <summary>
  /// This function is to show a linq way but is far less efficient
  /// </summary>
  /// <typeparam name="T"></typeparam>
  /// <param name="list"></param>
  /// <param name="length"></param>
  /// <returns></returns>
  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 }));
  }
  
  
  /// <summary>
  /// Swap 2 elements of same type
  /// </summary>
  /// <typeparam name="T"></typeparam>
  /// <param name="a"></param>
  /// <param name="b"></param>
  [MethodImpl(MethodImplOptions.AggressiveInlining)]
  static void Swap<T>(ref T a, ref T b)
  {
  T temp = a;
  a = b;
  b = temp;
  }
  
  
  /// <summary>
  /// Func to show how to call. It does a little test for an array of 4 items.
  /// </summary>
  public static void Test()
  {
  ForAllPermutation("123".ToCharArray(), (vals) =>
  {
  Debug.Print(String.Join("", vals));
  return false;
  });
  
  
  int[] values = new int[] { 0, 1, 2, 4 };
  
  
  Debug.Print("Non Linq");
  ForAllPermutation(values, (vals) =>
  {
  Debug.Print(String.Join("", vals));
  return false;
  });
  
  
  Debug.Print("Linq");
  foreach(var v in GetPermutations(values, values.Length))
  {
  Debug.Print(String.Join("", v));
  }
  
  
  // Performance
  int count = 0;
  
  
  values = new int[10];
  for(int n = 0; n < values.Length; n++)
  {
  values[n] = n;
  }
  
  
  Stopwatch stopWatch = new Stopwatch();
  stopWatch.Reset();
  stopWatch.Start();
  
  
  ForAllPermutation(values, (vals) =>
  {
  foreach(var v in vals)
  {
  count++;
  }
  return false;
  });
  
  
  stopWatch.Stop();
  Debug.Print($"Non Linq {count} items in {stopWatch.ElapsedMilliseconds} millisecs");
  
  
  count = 0;
  stopWatch.Reset();
  stopWatch.Start();
  
  
  foreach (var vals in GetPermutations(values, values.Length))
  {
  foreach (var v in vals)
  {
  count++;
  }
  }
  
  
  stopWatch.Stop();
  Debug.Print($"Linq {count} items in {stopWatch.ElapsedMilliseconds} millisecs");
  
  
  }
  }
  }
  

这里有一个易于理解的字符串和整数作为输入的置换函数。使用这个 甚至可以设置输出长度(在正常情况下它等于输入长度)

< em > String

    static ICollection<string> result;


public static ICollection<string> GetAllPermutations(string str, int outputLength)
{
result = new List<string>();
MakePermutations(str.ToCharArray(), string.Empty, outputLength);
return result;
}


private static void MakePermutations(
char[] possibleArray,//all chars extracted from input
string permutation,
int outputLength//the length of output)
{
if (permutation.Length < outputLength)
{
for (int i = 0; i < possibleArray.Length; i++)
{
var tempList = possibleArray.ToList<char>();
tempList.RemoveAt(i);
MakePermutations(tempList.ToArray(),
string.Concat(permutation, possibleArray[i]), outputLength);
}
}
else if (!result.Contains(permutation))
result.Add(permutation);
}

对于 整数，只要改变调用方法，排列()就不会受到影响:

    public static ICollection<int> GetAllPermutations(int input, int outputLength)
{
result = new List<string>();
MakePermutations(input.ToString().ToCharArray(), string.Empty, outputLength);
return result.Select(m => int.Parse(m)).ToList<int>();
}

下面是所提到的算法的另一个实现。

public class Program
{
public static void Main(string[] args)
{
string str = "abcefgh";
var astr = new Permutation().GenerateFor(str);
Console.WriteLine(astr.Length);
foreach(var a in astr)
{
Console.WriteLine(a);
}
//a.ForEach(Console.WriteLine);
}
}


class Permutation
{
public string[] GenerateFor(string s)
{


if(s.Length == 1)
{


return new []{s};
}


else if(s.Length == 2)
{


return new []{s[1].ToString()+s[0].ToString(),s[0].ToString()+s[1].ToString()};


}


var comb = new List<string>();


foreach(var c in s)
{


string cStr = c.ToString();


var sToProcess = s.Replace(cStr,"");
if (!string.IsNullOrEmpty(sToProcess) && sToProcess.Length>0)
{
var conCatStr = GenerateFor(sToProcess);






foreach(var a in conCatStr)
{
comb.Add(c.ToString()+a);
}




}
}
return comb.ToArray();


}
}

这里有一个在 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)));
}
}
}

以下是我的 JavaScript (NodeJS)解决方案。主要思想是我们一次只取一个元素，从字符串中“移除它”，改变其余的字符，并在前面插入元素。

function perms (string) {
if (string.length == 0) {
return [];
}
if (string.length == 1) {
return [string];
}
var list = [];
for(var i = 0; i < string.length; i++) {
var invariant = string[i];
var rest = string.substr(0, i) + string.substr(i + 1);
var newPerms = perms(rest);
for (var j = 0; j < newPerms.length; j++) {
list.push(invariant + newPerms[j]);
}
}
return list;
}


module.exports = perms;

以下是测试内容:

require('should');
var permutations = require('../src/perms');


describe('permutations', function () {
it('should permute ""', function () {
permutations('').should.eql([]);
})


it('should permute "1"', function () {
permutations('1').should.eql(['1']);
})


it('should permute "12"', function () {
permutations('12').should.eql(['12', '21']);
})


it('should permute "123"', function () {
var expected = ['123', '132', '321', '213', '231', '312'];
var actual = permutations('123');
expected.forEach(function (e) {
actual.should.containEql(e);
})
})


it('should permute "1234"', function () {
// Wolfram Alpha FTW!
var expected = ['1234', '1243', '1324', '1342', '1423', '1432', '2134', '2143', '2314', '2341', '2413', '2431', '3124', '3142', '3214', '3241', '3412', '3421', '4123', '4132'];
var actual = permutations('1234');
expected.forEach(function (e) {
actual.should.containEql(e);
})
})
})

这是我能想到的最简单的解决办法:

let rec distribute e = function
| [] -> [[e]]
| x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs]


let permute xs = Seq.fold (fun ps x -> List.collect (distribute x) ps) [[]] xs

distribute函数接受一个新元素 e和一个 n-元素列表，并返回一个 n+1列表列表，其中每个列表都在不同的位置插入了 e。例如，在列表 [1;2;3]中的四个可能位置中的每一个插入 10:

> distribute 10 [1..3];;
val it : int list list =
[[10; 1; 2; 3]; [1; 10; 2; 3]; [1; 2; 10; 3]; [1; 2; 3; 10]]

permute功能折叠在每个元素上，依次分布在迄今为止累积的排列上，最终在所有排列中达到高潮。例如，列表 [1;2;3]的6种排列:

> permute [1;2;3];;
val it : int list list =
[[3; 2; 1]; [2; 3; 1]; [2; 1; 3]; [3; 1; 2]; [1; 3; 2]; [1; 2; 3]]

为了保持中间累加器，将 fold改为 scan可以说明排列是如何一次产生一个元素的:

> Seq.scan (fun ps x -> List.collect (distribute x) ps) [[]] [1..3];;
val it : seq<int list list> =
seq
[[[]]; [[1]]; [[2; 1]; [1; 2]];
[[3; 2; 1]; [2; 3; 1]; [2; 1; 3]; [3; 1; 2]; [1; 3; 2]; [1; 2; 3]]]

列出字符串的排列。重复字符时避免重复:

using System;
using System.Collections;


class Permutation{
static IEnumerable Permutations(string word){
if (word == null || word.Length <= 1) {
yield return word;
yield break;
}


char firstChar = word[0];
foreach( string subPermute in Permutations (word.Substring (1)) ) {
int indexOfFirstChar = subPermute.IndexOf (firstChar);
if (indexOfFirstChar == -1) indexOfFirstChar = subPermute.Length;


for( int index = 0; index <= indexOfFirstChar; index++ )
yield return subPermute.Insert (index, new string (firstChar, 1));
}
}


static void Main(){
foreach( var permutation in Permutations ("aab") )
Console.WriteLine (permutation);
}
}

    //Generic C# Method
private static List<T[]> GetPerms<T>(T[] input, int startIndex = 0)
{
var perms = new List<T[]>();


var l = input.Length - 1;


if (l == startIndex)
perms.Add(input);
else
{


for (int i = startIndex; i <= l; i++)
{
var copy = input.ToArray(); //make copy


var temp = copy[startIndex];


copy[startIndex] = copy[i];
copy[i] = temp;


perms.AddRange(GetPerms(copy, startIndex + 1));


}
}


return perms;
}


//usages
char[] charArray = new char[] { 'A', 'B', 'C' };
var charPerms = GetPerms(charArray);




string[] stringArray = new string[] { "Orange", "Mango", "Apple" };
var stringPerms = GetPerms(stringArray);




int[] intArray = new int[] { 1, 2, 3 };
var intPerms = GetPerms(intArray);

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

以@Peter 的解决方案为基础，下面的版本声明了一个简单的 LINQ 风格的 Permutations()扩展方法，可以在任何 IEnumerable<T>上运行。

用法(关于字符串字符示例) :

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

产出:

a, b, c
a, c, b
b, a, c
b, c, a
c, b, a
c, a, b

或任何其他集合类型:

foreach (var permutation in (new[] { "Apples", "Oranges", "Pears"}).Permutations())
{
Console.WriteLine(string.Join(", ", permutation));
}

产出:

Apples, Oranges, Pears
Apples, Pears, Oranges
Oranges, Apples, Pears
Oranges, Pears, Apples
Pears, Oranges, Apples
Pears, Apples, Oranges

using System;
using System.Collections.Generic;
using System.Linq;


public static class PermutationExtension
{
public static IEnumerable<T[]> Permutations<T>(this IEnumerable<T> source)
{
var sourceArray = source.ToArray();
var results = new List<T[]>();
Permute(sourceArray, 0, sourceArray.Length - 1, results);
return results;
}


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


private static void Permute<T>(T[] elements, int recursionDepth, int maxDepth, ICollection<T[]> results)
{
if (recursionDepth == maxDepth)
{
results.Add(elements.ToArray());
return;
}


for (var i = recursionDepth; i <= maxDepth; i++)
{
Swap(ref elements[recursionDepth], ref elements[i]);
Permute(elements, recursionDepth + 1, maxDepth, results);
Swap(ref elements[recursionDepth], ref elements[i]);
}
}
}

以 彭阳 回答为基础/修订

灵感来自 Javascript 中的置换

C # 版本的 FunctionalPermutations应该是这样的

static IEnumerable<IEnumerable<T>> FunctionalPermutations<T>(IEnumerable<T> elements, int length)
{
if (length < 2) return elements.Select(t => new T[] { t });
/* Pengyang answser..
return _recur_(list, length - 1).SelectMany(t => list.Where(e => !t.Contains(e)),(t1, t2) => t1.Concat(new T[] { t2 }));
*/
return elements.SelectMany((element_i, i) =>
FunctionalPermutations(elements.Take(i).Concat(elements.Skip(i + 1)), length - 1)
.Select(sub_ei => new[] { element_i }.Concat(sub_ei)));
}

我希望这些就足够了:

using System;
                

public class Program
{
public static void Main()
{
//Example using word cat
permute("cat");
    

}


static void permute(string word){
for(int i=0; i < word.Length; i++){
char start = word[0];
for(int j=1; j < word.Length; j++){
string left = word.Substring(1,j-1);
string right = word.Substring(j);
Console.WriteLine(start+right+left);
}
if(i+1 < word.Length){
word = wordChange(word, i + 1);
}
            

}
}


static string wordChange(string word, int index){
string newWord = "";
for(int i=0; i<word.Length; i++){
if(i== 0)
newWord += word[index];
else if(i== index)
newWord += word[0];
else
newWord += word[i];
}
return newWord;
}

产出:

cat
cta
act
atc
tca
tac

这里有另一种方法，稍微更一般。

void Main()
{
var perms = new Permutations<char>("abc");
perms.Generate();
}




class Permutations<T> {
    

private List<T> permutation = new List<T>();
HashSet<T> chosen;
    

int n;
List<T> sequence;
    

public Permutations(IEnumerable<T> sequence)
{
this.sequence = sequence.ToList();
this.n = this.sequence.Count;
chosen = new HashSet<T>();
        

}
    

public void Generate()
{
if(permutation.Count == n) {
Console.WriteLine(string.Join(",",permutation));
}
else
{
foreach(var elem in sequence)
{
if(chosen.Contains(elem)) continue;
chosen.Add(elem);
permutation.Add(elem);
Generate();
chosen.Remove(elem);
permutation.Remove(elem);
}
}
}
}