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

https://stackoverflow.com/questions/756055

09-09-2019
|

题

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

是否有一个示例说明如何完成此操作以及解决此类问题背后的逻辑？

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

解决方案

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

既然你们也想知道原理，我就尽量用人性化的语言来解释一下。我认为大多数时候递归是非常简单的。只需要掌握两步：

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

在 人类语言:

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

例子：

如果集合只有一个元素 -->
把它返还。
烫发(a) -> a

如果集合有两个字符：对于其中的每个元素：返回元素，并添加其余元素的排列，就像这样：

烫发(ab) ->

a + 烫发(b) -> ab

b + 烫发(a) -> 巴

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

烫发(abc) ->

a + 烫发(bc) --> ABC, 阿克布

b + 烫发(ac) --> 巴克, BCA

c + 烫发(ab) --> 出租车, 篮球协会

烫发(abc...z) -->

a + 烫发(...), b + 烫发(...)
....

我找到了 伪代码 在 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#），来自 http://radio.weblogs.com/0111551/stories/2002/10/14/permutations.html ：相当冗长，但我还是决定复制它，所以这篇文章不依赖于原文。

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

其他提示

这只是两行代码如果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或更高。

下面我已经找到了解决方案。它是用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; }

<强>递归是没有必要的，这里是关于这个溶液良好的信息。

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

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

您可以写你的交换功能来交换字符。结果这是被称为置换（字符串，0）;

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

需要注意的是一组大小为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

稍作修改的版本在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; } }

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

var tail = chars.Except(new List<char>(){c});
使用除将导致除去所有出现，
即当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; }

我只是简单地删除使用卸下摆臂和.IndexOf找到的第一个发生。似乎是为我使用的至少工作。我敢肯定，它可以作出更聪明。

有一点要注意，虽然：结果列表可能包含重复的，所以一定要将该方法返回例如一个HashSet代替或使用您喜欢的任何方法除去返回后的重复。

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

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

C++ 和 Python 都内置了下一个排列和 itertools.排列分别发挥作用。

这里的一个单纯的功能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 }

性能可以通过改变交换采取的CLR阵列的可变性质的优点大大提高，但这种实现是线程安全与关于源阵列和可能在某些情况下是期望的。此外，对于具有多于16个元件的阵列INT必须用类型的具有更大的/任意精度阶乘17所导致一个Int32溢出代替。

下面是使用递归在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))); } } }

下面是一个易于理解字符串和整数作为输入permutaion功能。与此的甚至可以设定输出长度（其在正常情况下，它等于输入长度）

<强> 字符串

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

和用于<强> 整数只是改变呼叫者方法和 MakePermutations（）保持不变：

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

示例1：GetAllPermutations（ “ABC”，3）; “ABC”， “ACB” “BAC”， “BCA”， “出租车”， “CBA”

实施例2：GetAllPermutations（ “ABCD”，2）; “AB”， “AC”， “广告”， “BA”， “BC”， “BD” “CA”， “CB”， “CD”， “DA”， “DB”， “DC”

实施例3：GetAllPermutations（486,2）; 48 46 84 86 64 68

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

下面是将打印所有排列的功能。此函数实现由彼得解释逻辑。

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

下面的是我的执行置换。不介意的变量名，因为我在做它的乐趣:)

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

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

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

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

正如 10 的 Linq 实现的比较！（包括代码）：

这：235 毫秒内 36288000 个项目

林克：50051 毫秒内有 36288000 个项目

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

下面是我在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列表的列表。例如，在列表中的每个10四个可能的地方的插入[1;2;3]：

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

下面是将递归地打印所有排列的功能。

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

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

这是我的解决方案，它很容易让我明白

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

下面是一个更实施提到的ALGO的。

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

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

/// <summary> /// Print All the Permutations. /// </summary> /// <param name="inputStr">input string</param> /// <param name="strLength">length of the string</param> /// <param name="outputStr">output string</param> private void PrintAllPermutations(string inputStr, int strLength,string outputStr, int NumberOfChars) { //Means you have completed a permutation. if (outputStr.Length == NumberOfChars) { Console.WriteLine(outputStr); return; } //For loop is used to print permutations starting with every character. first print all the permutations starting with a,then b, etc. for(int i=0 ; i< strLength; i++) { // Recursive call : for a string abc = a + perm(bc). b+ perm(ac) etc. PrintAllPermutations(inputStr.Remove(i, 1), strLength - 1, outputStr + inputStr.Substring(i, 1), 4); } }

许可以下： CC-BY-SA 和归因

不隶属于 StackOverflow