07 | 排列：如何让计算机学会“田忌赛马”？

password = 'bacdce' classes = ['a', 'b', 'c', 'd', 'e'] def get_password(n, result = ''): if n == 0: if result == password: print(password) else: for i in classes: new_result = copy.copy(result) new_result = new_result + i get_password(n - 1, new_result) get_password(6)

交作业： public class L7_2 { public static void calLetterList(ArrayList<String> l, ArrayList<String> result) { if (result.size() == l.size()) { System.out.println(result); return; } for (String letter : l) { ArrayList<String> newResult = (ArrayList<String>) result.clone(); newResult.add(letter); calLetterList(l, newResult); } } public static void main(String[] args) { ArrayList<String> l = new ArrayList<>(Arrays.asList("a", "b", "c", "d", "e")); calLetterList(l, new ArrayList<>()); } }

C++形式交作业，好像用list数据结果会方便一点。 /** permutaion: 排列。 * 从n个数中选出m个数的方式，若不考虑顺序Cn(m)，若考虑顺序An(m) */ /* 问题：密码排列 * 假设有一个 4 位字母密码，每位密码是 a～e 之间的小写字。 * 编写密码可能排列方式。 */ #include <iostream> #include <vector> using namespace std; class Permutation { private: int resultCount_ = 0; public: /** Details: 根据输入字母列表，获得所有的排列方式。 * params: result- 当前排列形式， candidate- 未排列字母表。 * return: null */ void breakPassword(vector<string> result, vector<string> candidate) { int len = candidate.size(); if (0 == len) { // 无字母剩余，输出排列结果 outputResult(result); resultCount_++; return; } for (int i = 0; i < len; i++) { vector<string> resultNew; vector<string> candidateLeft; // 读取排列字母 resultNew = result; resultNew.push_back(candidate[i]); // 获得剩余字母表 candidateLeft = candidate; vector<string>::iterator it = candidateLeft.begin(); candidateLeft.erase(it + i); // 递归 breakPassword(resultNew, candidateLeft); } } // 输出结果 void outputResult(vector<string> result) { for (unsigned int i = 0; i < result.size(); i++) { cout << result[i]; } cout << endl; } // 获得所有可能密码总数 int getResultCount() { return resultCount_; } }; int main(void) { vector<string> fourAlphabetString = {"a", "b", "c", "d", "e"}; vector<string> res; Permutation test; test.breakPassword(res, fourAlphabetString); cout << "可能的密码形式："; cout << test.getResultCount() << "种" << endl; }

茶艺师学编程 1、学完这节课要记住的 ●不重复排列 n!/(n-m)! （1≤m≤n） ●不重复全排列 n！ ●重复排列 n＾m 2、田忌赛马也好，穷举破解法也好，背后的数学原理都是一样的，就是排列。由此我获得两点体会 ●这就是所谓“等价问题”。正因为存在“等价”，才能实现“融会贯通”。 ●正如黄老师所说，在确定好数学的解决办法后，程序的解法也自然出来了。 把这项本领练到极致的话，也许就能像那位高德纳（《计算机程序设计艺术》的作者），总是能用最慢的电脑获得编程大赛的第一名。

var chars = ['a', 'b', 'c', 'd', 'e'] var result = [] function getPassword(passwordChars, num, password) { if (num == 0) { return result.push(password) } else { for (var i = 0; i < passwordChars.length; i++) { getPassword(passwordChars, num - 1, password + passwordChars[i]) } } } getPassword(chars, 4, '')

怎么用递归来求？

最笨的方法，一个数组A容纳a~e，四个for循环遍历数组A，拼成一个新一维数组B，多个数组B再拼成二维数组，就是最后结果。

python3 一行解决 answer, = [f"{a}{b}{c}{d}" for a in "abcde" for b in "abcde" for c in "abcde" for d in "abcde" if f"{a}{b}{c}{d}" in password]

来补作业了，老师 -------------------------代码----------------------------------- /** * 排列 * * @param passwords 待排列的字符 * @param results 排列的结果 ***/ public void range(ArrayList<String> passwords, ArrayList<String> results) { //如果为空则不需要排列 if (passwords.isEmpty()) { String collect = String.join("", results); System.out.print(collect + "\t"); } for (int i = 0; i < passwords.size(); i++) { String password = passwords.get(i); ArrayList<String> newResult = (ArrayList<String>) results.clone(); ArrayList<String> newPassword = (ArrayList<String>) passwords.clone(); newResult.add(password); newPassword.remove(i); range(newPassword,newResult); } }

田忌赛马还可以用贪心算法来解