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

精选留言(54)

• 

  alic

  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)

  作者回复: 可以的👍

  2018-12-28

   1

   16
• 

  qinggeouye

  python
  一、田忌和齐王双方都随机选择马匹出战顺序
  import copy
  # 设置齐王的马跑完所需时间
  q_horses_time = {"q1": 1.0, "q2": 2.0, "q3": 3.0}
  # 设置田忌的马跑完所需时间
  t_horses_time = {"t1": 1.5, "t2": 2.5, "t3": 3.5}
  # 双方均随机选择出战的马匹
  
  q_horses = ["q1", "q2", "q3"]
  t_horses = ["t1", "t2", "t3"]
  
  def permutation(horses, result=None, all_results=None):
      """
      使用函数的递归（嵌套）调用，找出所有可能的马匹出战顺序
      :param all_results: 马匹出战顺序的所有排列（全排列）
      :param horses: 目前还剩多少马没有出战
      :param result: 保存当前已经出战的马匹及顺序（其中一种排列）
      :return:
      """
      if result is None:
          result = []
      if all_results is None:
          all_results = []
  
      # 所有马匹都已经出战，返回出战顺序
      if len(horses) == 0:
          all_results.append(result)
          return
  
      for k in range(len(horses)):
          # 从剩下的未出战马匹中 选择一匹 加入结果
          new_result = copy.copy(result)
          new_result.append(horses[k])
          # 将已选择的马匹从未出战的列表中移除
          rest_horses = copy.copy(horses)
          rest_horses.pop(k)
          # 递归调用 对于剩余的马匹继续生成排列
          permutation(rest_horses, new_result, all_results)
      return all_results
  
  
  def compare(t, q):
      t_won_cnt = 0
      for m in range(len(t)):
          print(str(t_horses_time.get(t[m])) + ',' + str(q_horses_time.get(q[m])))
          if t_horses_time.get(t[m]) < q_horses_time.get(q[m]):
              t_won_cnt = t_won_cnt + 1
      if t_won_cnt > len(t)//2:
          print("田忌获胜！")
      else:
          print("齐王获胜！")
  
  if __name__ == '__main__':
      # 双方均随机安排马匹出战，田忌获胜的概率仍为 1/6
      t_results = permutation(t_horses)
      q_results = permutation(q_horses)
      print(t_results)
      print(q_results)
      for i in range(len(t_results)):
          for j in range(len(q_results)):
              compare(t_results[i], q_results[j])
  

  2019-02-08

  

   5
• 

  菩提

  交作业：
  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<>());
  }
  
  }

  作者回复: 很赞

  2018-12-30

  

   5
• 

  Joe

  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;
  }
  

  作者回复: c语言确实更简洁👍

  2019-01-09

  

   4
• 

  Jing

  //思考题 c#版本
  private static char[] _letters = { 'a', 'b', 'c', 'd', 'e' };
  public static void GetPassword()
  {
  string password = "abded";
  CrackPassword(password.Length, new StringBuilder(), password);
  }
  
  private static void CrackPassword(int length, StringBuilder result, string realPsd)
  {
  if (length == 0)
  {
  if (realPsd.Equals(result.ToString()))
  {
  Console.WriteLine("Your password is:" + result.ToString());
  }
  result.Length = 0;
  return;
  }
  else if (length < 0)
  {
  return;
  }
  for (int i = 0; i < _letters.Length; i++)
  {
  StringBuilder temp = new StringBuilder();
  temp.Append(result.ToString());
  temp.Append(_letters[i]);
  CrackPassword(length - 1, temp, realPsd);
  }
  }

  2019-04-05

  

   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, '')
  

  作者回复: 代码很简洁

  2019-01-09

  

   2
• 

  文刂 氵共 超

  思考题 - 递归思想-C++
  #include <iostream>
  #include<string>
  
  using std::string;
  using namespace std;
  
  void BreakPassword( string Words, int PasswordLen, string result)
  {
  if (result.length() == PasswordLen)
  {
  //C++中string类型不能直接输出，需加头问题#include<string>，不能用#include<string.h>
  cout << result << " ";
  return;
  }
  
  for (int i = 0; i < Words.length(); ++i)
  {
  string newResult = result;
  newResult.insert( newResult.end(), Words[i] );
  BreakPassword(Words, PasswordLen, newResult);
  }
  }
  
  int _tmain(int argc, _TCHAR* argv[])
  {
  int passwordLen = 4;
  string words("abcde");
  string result = "";
  
  BreakPassword(words, passwordLen, result);
  
  return 0;
  }

  2018-12-28

  

   2
• 

  alic

  怎么用递归来求？

  作者回复: 具体是指哪道题目？

  2018-12-28

  

   2
• 

  毛毛

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

  作者回复: 密码短的话，循环嵌套就可以了。如果密码很长，或者长度是满足某种条件的，就需要递归

  2018-12-28

  

   2
• 

  QFann

  交作业
  /**
       *
       * @param password 密码组成元素
       * @param result 密码可能组合
       * @param number 密码个数
       */
      public static void getPassword(ArrayList<String> password,ArrayList<String> result,int number){
  
          if(result.size() >= number ){
              System.out.println(result);
              return;
          }
  
          for (int i = 0;i < password.size() ; i++){
              ArrayList<String> new_result = (ArrayList<String>) result.clone();
              new_result.add(password.get(i));
              getPassword(password,new_result,number);
  
          }
  
      }

  2019-04-29

  

   1
• 

  suiyueranzly

  来补作业了，老师
  -------------------------代码-----------------------------------
   /**
       * 排列
       *
       * @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);
  
          }
      }

  作者回复: 逻辑清晰

  2019-01-07

  

   1
• 

  风轨

  public class Crack {
      static char[] pwdcs = new char[] { 'a', 'b', 'c', 'd', 'e' };
      static String[] crack(int len) {
          String[] ps = new String[] { "" };
          while (len-- > 0) {
              String[] nps = new String[ps.length * pwdcs.length];
              int nsbsi = 0;
              for (String pwd : ps) {
                  for (char c : pwdcs) {
                      nps[nsbsi++] = pwd + c;
                  }
              }
              ps = nps;
          }
          return ps;
      }
      
      
      public static void main(String[] args) {
          String[] pwds = crack(4);
          for (String pwd : pwds) {
              System.out.println(pwd);
          }
          /**
           * 输出结果
           * aaaa
           * aaab
           * aaac
           * aaad
           * aaae
           * aaba
           * ....
           * 省略517行
           * ....
           * eeed
           * eeee
           *
           */
      }
  }
  

  2018-12-28

  

   1
• 

  石佳佳_Gemtra

  对于 n 个元素里取出 m(0<m≤n) 个元素的重复排列数量是 nxnxnx…xn，也就是 n^m。

  2018-12-28

  

   1
• 

  半湖思絮

  ```
  public class Lesson7_3 {
  
      private static final String[] charArr = {"a", "b", "c", "d", "e"};
  
      public static void permutate(int bit, String[] charArr, List<String> hasList) {
          if (bit == 0) {
              System.out.println(hasList);
          } else {
              int size = charArr.length;
              for (int i = 0; i < size; i++) {
                  List<String> tmpHas = new ArrayList<>(hasList);
                  tmpHas.add(charArr[i]);
                  permutate(bit - 1, charArr, tmpHas);
              }
          }
      }
  
      public static void main(String[] args) {
          permutate(4, charArr, new ArrayList<>());
      }
  }
  ```

  2019-12-10

  

  
• 

  teddytyy

  破解密码的排列应该是可重复的，最终排列数是n^m，而非n！

  作者回复: 对，取决于密码的每一位是否可以重用

  2019-12-05

  

  
• 

  teddytyy

  void brutalSolve(vector<char> factor, int num, vector<char> result, vector<char> passwd){
      if (num==0) {
          for(int i = 0; i < result.size(); i++) {
              if(result[i] != passwd[i]) return;
              cout<<result;
          }
      }
      num--;
      for (int i=0; i<factor.size(); i++) {
          result.pushback(factor[i]);
          brutalSolve(factor, num, result, passwd);
      }
  }

  2019-12-05

  

  
• 

  Geek_89b79a

  from copy import copy
  password = 'dftegaukfhsjndfgaweyjukfhcjnarieukvfyreaufyyhweaicuaru'
  a = [chr(97+i) for i in range(26)]
  def crack(length, result=""):
      if result != password[0:len(result)]:
          return
      if length == 0:
          if result == password:
              print(result)
              return
      else:
          for i in a:
              new_result = copy(result)
              new_result = new_result + i
              crack(length - 1, new_result)
  
  crack(len(password))

  2019-11-25

  

  
• 

  Vincent🌫

  205 次
  package cn.algorithm;
  
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.HashMap;
  
  public class Sort02 {
  
      static int ttt=0;
  
      public static void generatePassword(ArrayList<String> source,ArrayList<String> result,int count){
  
          if(result != null && result.size() == 4){
              System.out.println(result);
              return;
          }
  
          for(int i = 0 ; i < source.size() ; i++){
              ArrayList<String> new_result = (ArrayList<String>) result.clone();
              new_result.add(source.get(i));
              ArrayList<String> rest_source = (ArrayList<String>) source.clone();
              rest_source.remove(i);
              ttt++;
              generatePassword(rest_source,new_result,count);
          }
      }
  
      public static void main(String[] args) {
          int count = 4;
          ArrayList<String> source = new ArrayList<String>();
          source.add("a");
          source.add("b");
          source.add("c");
          source.add("d");
          source.add("e");
          ArrayList<String> result = new ArrayList<String>();
          generatePassword(source,result,count);
          System.out.println(ttt);
      }
  
  }
  

  2019-11-15

  

  
• 

  流氓汉高祖

  
  public static void main(String[] args) {
      
      ArrayList<String> t_horses = new ArrayList<String>(Arrays.asList("t1", "t2", "t3"));
      Lesson7_2.permutate(t_horses, new ArrayList<String>(), t_results);
      
      ArrayList<String> q_horses = new ArrayList<String>(Arrays.asList("q1", "q2", "q3"));
      Lesson7_2.permutate(q_horses, new ArrayList<String>(), q_results);
      
      System.out.println(t_results);
      System.out.println(q_results);
      System.out.println();
      
      for (int i = 0; i < t_results.size(); i++) {
        for (int j = 0; j < q_results.size(); j++) {
          Lesson7_2.compare(t_results.get(i), q_results.get(j));
        }
      }
      
    }
   
  
  这段代码中q_results和t_results是啥？还有就是Lesson7_2的代码怎么没有？

  作者回复: q_results表示齐王的出马顺序，t_results表示田忌的出马顺序，Lesson7_2是编辑错误，应该是Lesson7_1

  2019-11-14

  

  
• 

  顾骨

  go 版本
  --------------------------------------------------------
  
  var letters = "abcdefghijklmnopqrstuvwxyz"
  
  func breakPassword(password, result string) bool {
  if len(password) == len(result) {
  if password == result {
  fmt.Println(result)
  return true
  }
  return false
  }
  
  for _, letter := range letters {
  netResult := result
  netResult += string(letter)
  if found := breakPassword(password, netResult); found {
  return true
  }
  }
  return false
  }
  
  func main(){
      out := breakPassword("jgfdgh", "") // output: true
      out = breakPassword("zzzz", "")// output: true
      out = breakPassword("1zzz", "") // output: false
  }
  
  

  2019-11-12

  

  