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

问题描述：

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

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.

答

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

First of all: it smells like recursion of 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 个元素的排列是一个元素.
一组元素的排列是每个元素的列表，并与其他元素的每个排列连接起来.

示例:

如果集合只有一个元素 -->
归还.
烫发(a)->一个

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

如果集合有两个字符:for其中的每个元素:返回元素，与添加的其余元素，如下所示:

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:

烫发(ab) ->

a + perm(b) ->ab

a + perm(b) -> ab

b + perm(a) ->巴

b + perm(a) -> ba

进一步:对于集合中的每个字符:返回一个字符，用 > 的排列连接起来.其余部分

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

烫发(abc)->

perm(abc) ->

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

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

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

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

c + perm(ab) -->出租车、cba

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

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

perm(abc...z) -->

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

我在伪代码>http://www.programmersheaven.com/mb/Algorithms/369713/369713/permutation-algorithm-help/:

I found the pseudocode on 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:比较长，但我还是决定复制它，所以帖子不依赖于原文.

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.

该函数接受一串字符，并记下该确切字符串的所有可能排列，例如，如果ABC"已提供，应该溢出:

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、ACB、BAC、BCA、CAB、CBA.

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

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

相关推荐