本文實(shí)例講述了Python2.7基于笛卡爾積算法實(shí)現(xiàn)N個(gè)數(shù)組的排列組合運(yùn)算。分享給大家供大家參考，具體如下：
說(shuō)明：本人前段時(shí)間遇到的求n個(gè)數(shù)組的所有排列組合的問(wèn)題，發(fā)現(xiàn)笛卡爾積算法可以解決，但是網(wǎng)上搜索的只有Java版本的實(shí)現(xiàn)，于是自己試著用python實(shí)現(xiàn)，由于新手代碼不太規(guī)范。
代碼：本人封裝了一個(gè)類(lèi)Cartesian（笛卡爾），其中封裝了變量和方法：
1.變量
datagroup : 表示n個(gè)list(python 中的list與其他編程中的數(shù)組定義類(lèi)似)的集合,即一個(gè)二維數(shù)組
counterIndex：datagroup反向下標(biāo)值
counter : 用來(lái)記錄當(dāng)前datagroup中每一個(gè)數(shù)組輸出的下標(biāo)，初始全為0，因?yàn)閺牡谝粋€(gè)開(kāi)始輸出
2.方法
countlength : 計(jì)算數(shù)組長(zhǎng)度,即計(jì)算n的具體值
handle ：處理datagoroup二維數(shù)組中每一個(gè)一維數(shù)組輸出的下標(biāo)值
assemble ： 對(duì)datagoroup中的n個(gè)一維數(shù)組中的每一元素進(jìn)行排列組合輸出
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
# -*- coding:utf-8 -*-# python 實(shí)現(xiàn)N個(gè)數(shù)組的排列組合(笛卡爾積算法)class Cartesian(): # 初始化 def __init__(self, datagroup): self.datagroup = datagroup # 二維數(shù)組從后往前下標(biāo)值 self.counterIndex = len(datagroup)-1 # 每次輸出數(shù)組數(shù)值的下標(biāo)值數(shù)組(初始化為0) self.counter = [0 for i in range(0, len(self.datagroup))] # 計(jì)算數(shù)組長(zhǎng)度 def countlength(self): i = 0 length = 1 while(i < len(self.datagroup)): length *= len(self.datagroup[i]) i += 1 return length # 遞歸處理輸出下標(biāo) def handle(self): # 定位輸出下標(biāo)數(shù)組開(kāi)始從最后一位遞增 self.counter[self.counterIndex]+=1 # 判斷定位數(shù)組最后一位是否超過(guò)長(zhǎng)度，超過(guò)長(zhǎng)度，第一次最后一位已遍歷結(jié)束 if self.counter[self.counterIndex] >= len(self.datagroup[self.counterIndex]): # 重置末位下標(biāo) self.counter[self.counterIndex] = 0 # 標(biāo)記counter中前一位 self.counterIndex -= 1 # 當(dāng)標(biāo)記位大于等于0，遞歸調(diào)用 if self.counterIndex >= 0: self.handle() # 重置標(biāo)記 self.counterIndex = len(self.datagroup)-1 # 排列組合輸出 def assemble(self): length = self.countlength() i = 0 while(i < length): attrlist = [] j = 0 while(j<len(self.datagroup)): attrlist.append(self.datagroup[j][self.counter[j]]) j += 1 print attrlist self.handle() i += 1 |
測(cè)試：
注：測(cè)試代碼中我只選取了長(zhǎng)度為3的二維數(shù)組
|
1
2
3
4
5
6
|
if __name__ == "__main__": # 構(gòu)造二維數(shù)組 datagroup = [['aa1', ], ['bb1', 'bb2'], ['cc1', 'cc2', 'cc3']] # 創(chuàng)建cartesian對(duì)象 cartesian = Cartesian(datagroup) cartesian.assemble() |
輸出結(jié)果：
備注：此算法實(shí)現(xiàn)用python2.7版本
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
原文鏈接：http://blog.csdn.net/liujun19930313/article/details/73527174
