Python实现排列组合及笛卡尔积

Dear 丶 2022-10-09 12:13 213阅读 0赞

[itertools][]为高效循环而创建迭代器的函数  
**排列组合迭代器：**

<table> 
 <thead> 
  <tr> 
   <th align="left">迭代器</th> 
   <th align="left">实参</th> 
   <th align="left">结果</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left"><a href="https://docs.python.org/zh-cn/3/library/itertools.html#itertools.product" rel="nofollow"><code>product()</code></a></td> 
   <td align="left">p, q, … [repeat=1]</td> 
   <td align="left">笛卡尔积，相当于嵌套的for循环</td> 
  </tr> 
  <tr> 
   <td align="left"><a href="https://docs.python.org/zh-cn/3/library/itertools.html#itertools.permutations" rel="nofollow"><code>permutations()</code></a></td> 
   <td align="left">p[, r]</td> 
   <td align="left">长度r元组，所有可能的排列，无重复元素</td> 
  </tr> 
  <tr> 
   <td align="left"><a href="https://docs.python.org/zh-cn/3/library/itertools.html#itertools.combinations" rel="nofollow"><code>combinations()</code></a></td> 
   <td align="left">p, r</td> 
   <td align="left">长度r元组，有序，无重复元素</td> 
  </tr> 
  <tr> 
   <td align="left"><a href="https://docs.python.org/zh-cn/3/library/itertools.html#itertools.combinations_with_replacement" rel="nofollow"><code>combinations_with_replacement()</code></a></td> 
   <td align="left">p, r</td> 
   <td align="left">长度r元组，有序，元素可重复</td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <thead> 
  <tr> 
   <th align="left">例子</th> 
   <th align="left">结果</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="left"><code>product('ABCD', repeat=2)</code></td> 
   <td align="left"><code>AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD</code></td> 
  </tr> 
  <tr> 
   <td align="left"><code>permutations('ABCD', 2)</code></td> 
   <td align="left"><code>AB AC AD BA BC BD CA CB CD DA DB DC</code></td> 
  </tr> 
  <tr> 
   <td align="left"><code>combinations('ABCD', 2)</code></td> 
   <td align="left"><code>AB AC AD BC BD CD</code></td> 
  </tr> 
  <tr> 
   <td align="left"><code>combinations_with_replacement('ABCD', 2)</code></td> 
   <td align="left"><code>AA AB AC AD BB BC BD CC CD DD</code></td> 
  </tr> 
 </tbody> 
</table>

**函数实现**

from itertools import combinations, combinations_with_replacement,permutations, product
    alist = ['a', 'b', 'c', 'd']
    
    # 排列
    per = list(combinations(alist, 2))
    print(per)
    """ [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'a'), ('b', 'c'), ('b', 'd'), ('c', 'a'), ('c', 'b'), ('c', 'd'), ('d', 'a'), ('d', 'b'), ('d', 'c')] """
    # 无重复的组合C
    com = list(combinations(alist, 2))
    print(com)
    """ [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')] """
    
    # 有重复的组合
    cwr = list(combinations_with_replacement(alist, 2))
    print(cwr)
    """ [('a', 'a'), ('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'b'), ('b', 'c'), ('b', 'd'), ('c', 'c'), ('c', 'd'), ('d', 'd')] """
    
    # 笛卡尔积
    blist = [1, 2, 3, 4]
    pro = list(product(alist, blist))
    print(pro)
    """ [('a', 1), ('a', 2), ('a', 3), ('a', 4), ('b', 1), ('b', 2), ('b', 3), ('b', 4), ('c', 1), ('c', 2), ('c', 3), ('c', 4), ('d', 1), ('d', 2), ('d', 3), ('d', 4)] """

排列  
 A n m = n ( n − 1 ) ( n − 2 ) ⋯ ( n − m + 1 ) = n ! ( n − m ) ! A\_n^m=n(n-1)(n-2)\\cdots(n-m+1)=\\frac\{n!\}\{(n-m)!\}\\\\ Anm=n(n−1)(n−2)⋯(n−m\+1)=(n−m)!n!

无重复组合  
 C n m = A n m A m = n ! m ! ( n − m ) ! C n m = n ( n − 1 ) ( n − 2 ) ⋯ ( n − m + 1 ) m ! C\_n^m = \\frac\{A\_n^m\}\{A\_m\}=\\frac\{n!\}\{m!(n-m)!\}\\\\ C\_n^m = \\frac\{n(n-1)(n-2)\\cdots(n-m+1)\}\{m!\}\\\\ Cnm=AmAnm=m!(n−m)!n!Cnm=m!n(n−1)(n−2)⋯(n−m\+1)  
 C n m = A n m A m = n ! m ! ( n − m ) ! C n m = n ( n − 1 ) ( n − 2 ) ⋯ ( n − m + 1 ) m ! C\_n^m = \\frac\{A\_n^m\}\{A\_m\}=\\frac\{n!\}\{m!(n-m)!\}\\\\ C\_n^m = \\frac\{n(n-1)(n-2)\\cdots(n-m+1)\}\{m!\}\\\\ Cnm=AmAnm=m!(n−m)!n!Cnm=m!n(n−1)(n−2)⋯(n−m\+1)  
有重复组合  
 H n m = C n + m − 1 m = ( n + m − 1 ) ! m ! ( n − 1 ) ! H\_n^m=C\_\{n+m-1\}^m=\\frac\{(n+m-1)!\}\{m!(n-1)!\} Hnm=Cn\+m−1m=m!(n−1)!(n\+m−1)!  
积笛卡尔乘积是指在数学中，两个集合*X*和*Y*的笛卡尔积（Cartesian product），又称直积，表示为*X*×*Y*，第一个对象是*X*的成员而第二个对象是*Y*的所有可能有序对的其中一个成员  
 A = \{ a , b \} , B = \{ 0 , 1 , 2 \} A ∗ B = \{ ( a , 0 ) , ( a , 1 ) , ( a , 2 ) , ( b , 0 ) , ( b , 1 ) , ( b , 2 ) \} B ∗ A = \{ ( 0 , a ) , ( 0 , b ) , ( 1 , a ) , ( 1 , b ) , ( 2 , a ) , ( 2 , b ) \} A=\\\{a, b\\\}, B=\\\{0,1, 2\\\}\\\\ A\*B = \\\{(a,0), (a,1), (a,2), (b,0), (b,1), (b,2)\\\}\\\\ B\*A=\\\{(0, a), (0, b), (1, a), (1, b), (2, a), (2, b)\\\} A=\{ a,b\},B=\{ 0,1,2\}A∗B=\{ (a,0),(a,1),(a,2),(b,0),(b,1),(b,2)\}B∗A=\{ (0,a),(0,b),(1,a),(1,b),(2,a),(2,b)\}

[itertools]: https://docs.python.org/zh-cn/3/library/itertools.html