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

精选留言(36)

• 
  alic

  2018-12-28

   12

  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)

  展开

  作者回复: 可以的👍

• 
  Joe

  2019-01-09

   4

  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语言确实更简洁👍

• 
  qinggeouy...

  2019-02-08

   3

  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])
  

  展开
• 
  菩提

  2018-12-30

   3

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

  展开

  作者回复: 很赞

• 
  alic

  2018-12-28

   2

  怎么用递归来求？

  展开

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

• 
  QFann

  2019-04-29

   1

  交作业
  /**
       *
       * @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);
  
          }
  
      }

  展开
• 
  Jing

  2019-04-05

   1

  //思考题 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);
  }
  }

  展开
• suiyueran...

  2019-01-07

   1

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

  展开

  作者回复: 逻辑清晰

• 
  文刂 氵共...

  2018-12-28

   1

  思考题 - 递归思想-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

   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

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

  展开

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

• 
  枫林火山

  2019-03-26

  

  Go语言作业
  /**
  实现一个密码破解Demo,不用递归实现,实现最大长度的破解.
  这里复习用到了位运算和进制的概念
  */
  package main
  
  import (
      "flag"
      "fmt"
      "math"
      "strconv"
      "strings"
  )
  
  var inputPw = flag.String("pw", "a", "待测试密码")
  
  var pwSet = [5]string{"a", "b", "c", "d", "e"}
  
  type compareFunc = func(src string) bool
  
  func main() {
      flag.Parse()
      compare := createCompare(*inputPw)
      result, _ := getPassword(compare, len(*inputPw))
  
      fmt.Println(result)
  }
  
  func getPassword(compare compareFunc, maxLength int) (string, bool) {
      for length := 1; length <= maxLength; length++ {
          kindsFloat := math.Pow(float64(len(pwSet)), float64(length))
          kinds := int(kindsFloat)
          base := len(pwSet)
          for kind := 0; kind < kinds; kind++ {
              //10进制转为pwSet.length的进制
              numStr := strconv.FormatInt(int64(kind), base)
              var srcPw = ""
              for _, indexStr := range []byte(numStr) {
                  index, ok := strconv.ParseInt(string(indexStr), base, 64)
                  if ok == nil {
                      srcPw = pwSet[index] + srcPw
                  }
              }
              if compare(srcPw) == true {
                  return srcPw, true
              }
          }
      }
  
      return "未找到正确密码", false
  }
  
  ///返回比较函数
  func createCompare(target string) compareFunc {
      return func(src string) bool {
          return strings.Compare(target, src) == 0
      }
  }
  

  展开

  作者回复: Go语言最近很火啊，让我先补习一下Go语言 😆

• 
  jt

  2019-03-25

  

  /* jt [2019-03-25 周一] */
  #include <memory.h>
  #include <stdio.h>
  #include <math.h>
  
  #define PASSWD "eeee"
  #define PASSLEN 4
  
  /* return cnt(>1) if cracked */
  double crack(char *str, int len, char start, char end)
  {
      int i = 0;
      double limit, cnt = 0;
  
      limit = pow(end - start + 1, len); /* iter limit */
      while (cnt++ <= limit) {
          if (!memcmp(str, PASSWD, len)) return cnt; /* found! */
  
          str[0]++;
          /* 循环递加字母，超过范围则进位 */
          for (i = 0; i < len; i++) {
              if (str[i] <= end) {
                  break; /* 无需继续进位 */
              }
              if (i == (len - 1)) {
                  return 0; /* 最高位进位，表明没找到 */
              }
  
              str[i] = start; /* 循环进位递加字母 */
              str[i+1]++;
          }
      }
      return 0;
  }
  
  int main(void)
  {
      char buf[PASSLEN+1] = "aaaa";
      double cnt;
  
      if ((cnt = crack(buf, PASSLEN, 'a', 'e')) > 0) {
          printf("success! key is [%s], cnt=%.0f\n", buf, cnt);
      } else {
          printf("fail..\n");
      }
  
      return 1;
  }

  展开
• 梦倚栏杆

  2019-03-17

  

  @Getter
  @Setter
  class Permutation {
  
      // 排列词
      private List<Character> words;
  
      // 长度
      private int length;
  
      public List<ArrayList<Character>> getRepeatedFullyPermutation() {
          List<ArrayList<Character>> result = words.stream().map(character -> {
              ArrayList<Character> res = new ArrayList<>();
              res.add(character);
              return res;
          }).collect(Collectors.toList());
  
          for (int i = 1; i < length; i++) {
              List<ArrayList<Character>> newResult = new ArrayList<>();
              result.forEach(j -> words.forEach(
                      character -> {
                          ArrayList<Character> res = (ArrayList<Character>) j.clone();
                          res.add(character);
                          newResult.add(res);
                      }
                      )
              );
              result = newResult;
          }
  
          return result;
      }
  }

  展开
• 
  大王叫我来...

  2019-02-12

  

  ```go
  package main
  
  import "fmt"
  
  var option = []string{"a", "b", "c", "d", "e"}
  
  func main() {
      var password [4]string
      passwdGen(4, password)
  }
  
  // 最简单的情形就是只有密码只有1位，通过控制密码的位数，降低问题的规模
  func passwdGen(length int, password [4]string) {
      if length == 0 {
          fmt.Println(password)
          return
      } else {
          password := password
          for _, val := range option {
              password[length-1] = val
              passwdGen(length-1, password)
          }
      }
  
  }
  ```

  展开
• 
  qinggeouy...

  2019-02-08

  

  python
  二、思考题：
  import copy
  
  my_pwd = 'bada' # 实际密码
  pwd_char = ['a', 'b', 'c', 'd', 'e'] # 字符数组
  
  def decrypt(char, password=None):
      """
      使用函数的递归（嵌套）调用，找出所有可能的 4 位密码
      :param char: 组成密码的字符
      :param password: 当前找出的密码
      :return:
      """
      if password is None:
          password = []
      if len(password) == 4:
          if "".join(password) == my_pwd:
              print(password)
              print("密码破解成功！")
              return True
          else:
              return False
  
      for i in range(len(char)):
          new_password = copy.copy(password)
          new_password.append(char[i])
          rest_char = copy.copy(char)
          if decrypt(rest_char, new_password):
              return True
  
      return False
  
  if __name__ == "__main__":
      decrypt(pwd_char)
  

  展开

  作者回复: 正解

• 
  路过蜻蜓

  2019-01-22

  

  #python，一个复杂度高的写法，胜在少代码
  a = ['a','b','c','d','e']
  password = 'abcd'
  f=''
  for i in password:
      for n in a:
          if n == i:
              f+=i
  print('f=',f)

  展开

  作者回复: 代码是否没有贴全？好像这段代码只是比较了两个字符串

• pz

  2019-01-22

  

  作业pyhton
  dict = ["a","b","c","d","e"]
  origPsw = "caaeeae"
  
  def calcPsw(count,res):
  \t if (count <= 0):
  \t\t if(res==origPsw):
  \t\t\t print("password:"+res)
  \t\t return
  \t c = count-1
  \t for i in dict:
  \t\t newRes = res+i
  \t\t calcPsw(c,newRes)
  
  calcPsw(7,"")

  展开

  作者回复: 思路很清晰，代码也很简短👍

• 
  予悠悠

  2019-01-20

  

  用python来补作业。没有用递归，用了迭代来解决。
  LETTERS = ['a', 'b', 'c', 'd', 'e']
  
  def all_passwords():
      last_passwords = [[]]
      for i in range(4):
          new_passwords = []
          for password in last_passwords:
              for letter in LETTERS:
                  new_password = password + [letter]
                  new_passwords.append(new_password)
          last_passwords = new_passwords
      return last_passwords

  展开

  作者回复: 因为格式上看不出缩进，对Python而言有歧义。你可以使用\t来表示缩进，再贴一次代码

• 
  三木子

  2019-01-14

  

  只有4位密码的话，那可否是4个for循环搞定？

  展开

  作者回复: 是的 可以的