Python2.7基于笛卡尔积算法实现N个数组的排列组合运算示例

2020-01-04 16:16:13

字体：大中小

来源：转载

供稿：网友

本文实例讲述了Python2.7基于笛卡尔积算法实现N个数组的排列组合运算。分享给大家供大家参考，具体如下：

说明：本人前段时间遇到的求n个数组的所有排列组合的问题，发现笛卡尔积算法可以解决，但是网上搜索的只有Java版本的实现，于是自己试着用python实现，由于新手代码不太规范。

代码：本人封装了一个类Cartesian（笛卡尔），其中封装了变量和方法：

1.变量

datagroup : 表示n个list(python 中的list与其他编程中的数组定义类似)的集合,即一个二维数组
counterIndex：datagroup反向下标值
counter : 用来记录当前datagroup中每一个数组输出的下标，初始全为0，因为从第一个开始输出

2.方法

countlength : 计算数组长度,即计算n的具体值
handle ：处理datagoroup二维数组中每一个一维数组输出的下标值
assemble ：对datagoroup中的n个一维数组中的每一元素进行排列组合输出

# -*- coding:utf-8 -*-# python 实现N个数组的排列组合(笛卡尔积算法)class Cartesian():  # 初始化  def __init__(self, datagroup):    self.datagroup = datagroup    # 二维数组从后往前下标值    self.counterIndex = len(datagroup)-1    # 每次输出数组数值的下标值数组(初始化为0)    self.counter = [0 for i in range(0, len(self.datagroup))]  # 计算数组长度  def countlength(self):    i = 0    length = 1    while(i < len(self.datagroup)):      length *= len(self.datagroup[i])      i += 1    return length  # 递归处理输出下标  def handle(self):    # 定位输出下标数组开始从最后一位递增    self.counter[self.counterIndex]+=1    # 判断定位数组最后一位是否超过长度，超过长度，第一次最后一位已遍历结束    if self.counter[self.counterIndex] >= len(self.datagroup[self.counterIndex]):      # 重置末位下标      self.counter[self.counterIndex] = 0      # 标记counter中前一位      self.counterIndex -= 1      # 当标记位大于等于0，递归调用      if self.counterIndex >= 0:        self.handle()      # 重置标记      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

测试：

注：测试代码中我只选取了长度为3的二维数组

if __name__ == "__main__":  # 构造二维数组  datagroup = [['aa1', ], ['bb1', 'bb2'], ['cc1', 'cc2', 'cc3']]  # 创建cartesian对象  cartesian = Cartesian(datagroup)  cartesian.assemble()

输出结果：

Python2.7,笛卡尔积,算法,数组,排列组合