【面试题28】字符串的排列

【题目描述】

输入一个字符串，打印出该字符串中字符的所有排列。

【解决方案】

递归，依次与其后数字交换，交换一次，输出一次。

我的代码实现，仅供参考：

 1         public static void Permutation(char[] str, int start)
 2         {
 3             if (str == null || str.Length < 1)
 4             {
 5                 return;
 6             }
 7 
 8             if (start == str.Length - 1)
 9             {
10                 foreach (char ch in str)
11                 {
12                     Console.Write(ch);
13                 }
14 
15                 Console.WriteLine();
16             }
17 
18             for (int i = start; i < str.Length; i++)
19             {
20                 char temp = str[i];
21                 str[i] = str[start];
22                 str[start] = temp;
23 
24                 Permutation(str, start + 1);
25 
26                 temp = str[i];
27                 str[i] = str[start];
28                 str[start] = temp;
29             }
30         }

【本题扩展】

如果不是求排列，而是求数字的所有组合该怎么求？例如输入a,b,c，则他们的组合有a,b,c,ab,ac,bc,abc。

我的代码实现，仅供参考：

 1         public static void Perm(string str)
 2         {
 3             List<char> result = new List<char>();
 4 
 5             for (int i = 1; i <= str.Length; i++)
 6             {
 7                 Perm(str, i, result);
 8             }
 9         }
10 
11         public static void Perm(string str, int len, List<char> result)
12         {
13             if (len == 0)
14             {
15                 foreach (char ch in result)
16                     Console.Write(ch);
17                 Console.WriteLine();
18                 return;
19             }
20 
21             for (int i = 0; i < str.Length; i++)
22             {
23                 result.Add(str[i]);                
24                 Perm(str.Substring(i+1), len - 1, result);
25                 result.RemoveAt(result.Count - 1);
26             }
27         }

【相关题目】

1. 输入一个含有8个数字的数组，判断有没有可能把这8个数字分别放到正方体的8个顶点，使得正方体上三组相对的面上的4个顶点的和都相等。

解析：

我的代码实现，仅供参考：

 1         public static bool IsValid(int[] arr)
 2         {
 3             if (arr == null || arr.Length < 1)
 4             {
 5                 return false;
 6             }
 7 
 8             return Permutation(arr, 0);
 9         }
10 
11         public static bool Permutation(int[] arr, int begin)
12         {
13             if (begin == arr.Length)
14             {
15                 if (arr[0] + arr[1] + arr[2] + arr[3] == arr[4] + arr[5] + arr[6] + arr[7] &&
16                     arr[0] + arr[2] + arr[4] + arr[6] == arr[1] + arr[3] + arr[5] + arr[7] &&
17                     arr[0] + arr[1] + arr[4] + arr[5] == arr[2] + arr[3] + arr[6] + arr[7])
18                     return true;
19                 else
20                     return false;
21             }
22 
23             bool resul = false;
24 
25             for (int i = begin; i < arr.Length; i++)
26             {
27                 int temp = arr[begin];
28                 arr[begin] = arr[i];
29                 arr[i] = temp;
30 
31                 resul = Permutation(arr, i + 1);
32 
33                 if (resul)
34                     return true;
35 
36                 temp = arr[begin];
37                 arr[begin] = arr[i];
38                 arr[i] = temp;
39             }
40 
41             return false;
42         }

【举一反三】

如果面试题是按照一定要求摆放若干个数字，我们可以先求出这些数字的所有排列，然后再一一判断每个排列是不是满足题目给定的要求。