清单字符串/整数的所有排列 [英] Listing all permutations of a string/integer
问题描述
在节目访谈的一项常见任务（而不是从我的采访，虽然经历）是一个字符串或整数，并列出每一种可能的排列。
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?
我已经看到了一些code片段，但他们并没有很好的注释/解释，因此很难跟随。
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. 1元件的排列是一个元素。
2.一组元素的置换是各元素的列表，连有其它元素的每一个的置换。
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:
如果设定的只是有一个元素 - >
返回。
烫发（一） - > A
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:
烫发（AB） - > 的
A +烫发（B） - > AB
a + perm(b) -> ab
B +烫发（一） - > BA
b + perm(a) -> ba
另外：对于集合中的每个字符：返回一个字符，连接在一起的perumation>中集的其余部分
Further: for each character in the set: return a character, concatenated with a perumation of > the rest of the set
烫发（ABC） - >
perm(abc) ->
A +烫发（BC） - > 农行 ACB
a + perm(bc) --> abc, acb
B +烫发（AC） - > BAC BCA
b + perm(ac) --> bac, bca
C +烫发（AB） - > 驾驶室 CBA
c + perm(ab) --> cab, cba
烫发（ABC ...... Z） - >
perm(abc...z) -->
A +烫发（...），B +烫发（....）
......
a + perm(...), b + perm(....)
....
我发现在伪code 的<一个href="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＃），从<一个href="http://radio.weblogs.com/0111551/stories/2002/10/14/permutations.html">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.
code：
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);
}
}
这篇关于清单字符串/整数的所有排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
