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