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

问题:

编程访谈中的一个常见任务(不是从我的访谈经验)是采取字符串或整数,列出每个可能的排列。
有没有这样做的例子和解决这个问题的逻辑?
我看过几个代码片段,但他们没有很好的评论/解释,因此很难跟踪。

回答:

首先:它闻起来像recursion当然!
既然你也想知道这个原则,我尽力解释它的人文语言。我认为递归很多时候很简单。你只需要掌握两个步骤:

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

人类语言

简而言之:
1. 1元素的排列是一个元素。
2.一组元素的排列是每个元素的列表,与其他元素的每个排列相连。
 
如果集合只有一个元素 – >
返回。
烫发(a) – >一个
如果集合有两个字符:对于其中的每个元素:返回元素,其余元素的置换如下所示:
 perm(ab) ->
a + perm(b) – > AB
b + perm(a) – > BA
另外:对于集合中的每个字符:返回一个字符,并连接到集合的其余部分
perm(abc) – >
a + perm(bc) – > ABCACB
b + perm(ac) – > BACBCA
c + perm(ab) – > 出租车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 } } [/code]  C#
OK,还有一些比较精细的东西(因为它被标记为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;

a ^= b;
b ^= a;
a ^= b;
}

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); } } [/code]     Code问答: http://codewenda.com/topics/python/
Stackoverflow: Listing all permutations of a string/integer

*转载请注明本文链接以及stackoverflow的英文链接

发表评论

电子邮件地址不会被公开。 必填项已用*标注

+ 20 = 25