在朋友QQ空間看到一道題，如下：
當時順手畫了條數軸，在數軸上標出了各個算式的解的特點：和為7的算式的解關于4對稱,和為9的解關于5對稱等等。草草算了下，發現很難同時滿足5個條件。而細算又太麻煩，算了，反正是程序員，寫程序求解吧。
因為是4個算式，很自然的就想到窮舉法。將每個算式可能的結果放在一起算笛卡爾積，如果有解的話，則必然存在一個笛卡爾積里面存在1到8這8個不同的元素。
計算笛卡爾積的代碼如下：
/// <summary>/// 計算元素集列表的笛卡爾積/// </summary>/// <typeparam name="T">元素具體類型</typeparam>/// <param name="sets">元素集列表</param>/// <returns>笛卡爾積列表</returns>public static T[][] CalculateCartesianPRoduct<T>(this IList<IList<T>> sets){ // 笛卡爾積總數 int total = 1; // 元素集個數 int setCount = 0; foreach (var set in sets) { total *= set.Count; setCount++; } // 笛卡爾積列表 var products = new T[total][]; // 除數列表，用于計算每個笛卡爾積的情況 var dividers = new int[setCount]; int divider = 1; // 倒序循環，因為后面的多種情況對應前面的一種情況 for (int counter = setCount - 1; counter >= 0; counter--) { dividers[counter] = divider; divider *= sets[counter].Count; } // 計算笛卡爾積,共有permutationNumber個笛卡爾積, // 從0到permutationNumber中,每個數字對應一種笛卡爾積情況 for (int counter = 0; counter < total; counter++) { // 一個笛卡爾積的情況 var permutation = new T[setCount]; int index = 0; foreach (var set in sets) { // 將數字映射到元素集中的位置 var pos = (counter / dividers[index]) % set.Count; permutation[index] = set[pos]; index++; } products[counter] = permutation; } return products;}
原理是將笛卡爾積解的總個數里的每個數字映射到一個解。
比如前面幾個笛卡爾積如下：
[2, 1] [3, 1] [1, 6] [1, 8]
[2, 1] [3, 1] [1, 6] [2, 7]
[2, 1] [3, 1] [1, 6] [3, 6]
[2, 1] [3, 1] [1, 6] [4, 5]
[2, 1] [3, 1] [2, 5] [1, 8]
[2, 1] [3, 1] [2, 5] [2, 7]
[2, 1] [3, 1] [2, 5] [3, 6]
[2, 1] [3, 1] [2, 5] [4, 5]
后面我又想到，實際上計算全排列也可以解決此題。將1到8取全排列，如果此題有解的話，則必然存在一個全排列，使得每兩個元素為一對，依次滿足4個算式。
代碼如下：
/// <summary>/// 計算指定元素集的全排列/// </summary>/// <typeparam name="T">元素的具體類型</typeparam>/// <param name="collection">元素集</param>/// <returns>全排列</returns>public static IEnumerable<T[]> CalculatePermutationCrude<T>(ICollection<T> collection){ // 元素個數 int elementCount = collection.Count(); // 全排列列表 var permutations = new List<T[]>(); // 一個全排列 var permutation = new List<T>(); CalculatePermutationCrude(permutations, permutation, collection, elementCount); return permutations;}/// <summary>/// 計算指定元素集的全排列/// </summary>/// <typeparam name="T">元素的具體類型</typeparam>/// <param name="permutations">全排列列表</param>/// <param name="permutation">一個全排列</param>/// <param name="collection">元素集</param>/// <param name="setLength">集合長度</param>private static void CalculatePermutationCrude<T>( List<T[]> permutations, List<T> permutation, ICollection<T> collection, int setLength){ if (permutation.Count < setLength) { foreach (var item in collection) { // 不是可重排列,不能包含 if (!permutation.Contains(item)) { var temp = permutation.ToList(); temp.Add(item); if (temp.Count == setLength) { // 達到最大計算深度,表示完成一個全排列,添加 permutations.Add(temp.ToArray()); } else { CalculatePermutationCrude(permutations, temp, collection, setLength); } } } }}
原理是有多少個元素，就循環多少次，將包含重復元素的排列剔除掉，自然就是集合的全排列了。
代碼如下：
/// <summary> /// 計算指定元素集的全排列 /// </summary> /// <typeparam name="T">元素的具體類型</typeparam> /// <param name="set">元素集</param> /// <returns>全排列</returns> public static IEnumerable<T[]> CalculatePermutationDFS<T>(IEnumerable<T> set) { var permutations = new List<T[]>(); var path = new List<T>(); bool[] visited = new bool[set.Count()]; CalculatePermutationDFS(set, permutations, path, visited); return permutations; } /// <summary> /// 計算指定元素集的全排列 /// </summary> /// <typeparam name="T">元素的具體類型</typeparam> /// <param name="set">元素集</param> /// <param name="permutations">全排列</param> /// <param name="path">排列的元素列表</param> /// <param name="visited">元素訪問與否的數組</param> private static void CalculatePermutationDFS<T>( IEnumerable<T> set, List<T[]> permutations, List<T> path, bool[] visited) { if (path.Count == set.Count()) { permutations.Add(path.ToArray()); } for (int i = 0; i < set.Count(); i++) { if (!visited[i]) { path.Add(set.ElementAt(i)); visited[i] = true; CalculatePermutationDFS(set, permutations, path, visited); path.RemoveAt(path.Count - 1); visited[i] = false; } } }
在代碼中使用了一個輔助列表保存遍歷過的元素，一個輔助數組保存元素的訪問情況，在深度遍歷前設置相關信息，遍歷完成后重置相關信息。
上面的兩種解法使用了遞歸，眾所周知，全排列的個數為待排列個數的階乘。而在數據量較大時，階乘比指數爆炸更可怕。如果不使用自建堆棧，將遞歸化為迭代，有沒有其他辦法計算全排列，就像前面計算笛卡爾積一樣，將每個數字映射到一個解。經過多次試錯，總算被我想到了一個辦法。
將每一個全排列對應一個數，以1234為例，如下圖：
將每個序號（從0開始）對應到一個數。對應數的有如下規律：
終于可以上代碼了：
/// <summary> /// 計算指定元素集的全排列 /// </summary> /// <typeparam name="T">元素的具體類型</typeparam> /// <param name="collection">元素集</param> /// <returns>全排列</returns> public static IEnumerable<T[]> CalculatePermutation<T>(IList<T> collection) { // 全排列總數 int total = 1; // 元素個數 int elementCount = collection.Count; // 除數列表，用于計算每個全排列的情況 var dividers = new int[elementCount - 1]; for (int i = 2; i <= elementCount; i++) { dividers[i - 2] = total; total *= i; } // 全排列列表 var permutations = new T[total][]; // 計算全排列,共有permutationNumber個全排列, // 從0到permutationNumber中,每個數字對應一種全排列情況 for (int counter = 0; counter < total; counter++) { // 一個全排列的情況 var permutation = new T[elementCount]; // 指示數組，指示全排列對應元素集中的位置 var indicates = new int[elementCount - 1]; // 使用數組，指示元素集中對應的元素是否已使用 var usedFlags = new bool[elementCount]; for (int j = 0; j < elementCount - 1; j++) { // 從右向左計算 indicates[elementCount - 2 - j] = (counter / dividers[j]) % (j + 2); } // 全排列的索引 int index = 0; foreach (var indicate in indicates) { int pos = 0; // 統計未使用的元素 int unusedCount = -1; for (; pos < elementCount; pos++) { if (!usedFlags[pos]) { unusedCount++; } // 找到了要放入的元素位置 if (unusedCount >= indicate) { break; } } permutation[index] = collection[pos]; usedFlags[pos] = true; index++; } // 將最后剩余的元素放入全排列 for (int j = 0; j < elementCount; j++) { if (!usedFlags[j]) { permutation[elementCount - 1] = collection[j]; break; } } permutations[counter] = permutation; } return permutations; }
經過一番勞累，結局是悲傷的，答案就是沒有答案。可能有的朋友會說特殊運算，由于題目的限制，冪跟對數是不可能了，唯一能夠使用的特殊運算就只有平方，在這種情況下，依然沒有答案。當然，如果你硬要說立方也是特殊運算，那么還是有解的。
此刻我的內心是崩潰的
新聞熱點
疑難解答
