python實現高效率的排列組合演算法-Python教學-PHP中文網

python實現高效率的排列組合演算法

高洛峰

發布： 2016-10-18 10:37:19

原創

2255 人瀏覽過

組合演算法

本程式的想法是開一個數組，其下標表示1到m個數，數組元素的值為1表示其下標

代表的數被選中，為0則沒選中。

先初始化，將陣列前n個元素置1，表示第一個組合為前n個數。

接著從左到右掃描數組元素值的「10」組合，找到第一個「10」組合後將其變為

「01」組合，同時將其左邊的所有「1」全部移至數組的最左端。

當第一個「1」移動到陣列的m-n的位置，也就是n個「1」全部移到最右端時，就得

到了最後一個組合。

例如求5中選3的組合：

1 1 1 0 0 //1,2,3

1 //1,2,3

1 //1

1 0 1 1 0 //1,3 ,4

0 1 1 1 0 //2,3,4

1 1 0 1 //1,3,5

0 1 1 0 1 //2,3,5

1 0 0 1 1 //1,4,5

0 1 1 1 //3,4,5

使用python實作：

group = [1, 1, 1, 0, 0, 0]
group_len = len(group)
#计算次数
ret = [group]
ret_num = (group_len * (group_len - 1) * (group_len - 2)) / 6
for i in xrange(ret_num - 1):
  
    &#39;第一步：先把10换成01&#39;
    number1_loc = group.index(1)
    number0_loc = group.index(0)
  
    #替换位置从第一个０的位置开始
    location = number0_loc
      #判断第一个０和第一个１的位置哪个在前，
      #如果第一个０的位置小于第一个１的位置，
      #那么替换位置从第一个１位置后面找起
  
    if number0_loc < number1_loc:
        location = group[number1_loc:].index(0) + number1_loc
  
    group[location] = 1
    group[location - 1] = 0
  
    &#39;第二步：把第一个10前面的所有１放在数组的最左边&#39;
    if location - 3 >= 0:
        if group[location - 3] == 1 and group[location - 2] == 1:
            group[location - 3] = 0
            group[location - 2] = 0
            group[0] = 1
            group[1] = 1
        elif group[location - 3] == 1:
            group[location - 3] = 0
            group[0] = 1
        elif group[location - 2] == 1:
            group[location - 2] = 0
            group[0] = 1
  
    print group
    ret.append(group)

登入後複製

全排列演算法

從1到N，輸出全排列，共N！條。

分析：用N進位的方法吧。設一個N個單元的數組，對第一個單元做加一操作，滿N進

一。每加一次一就判斷一下各位數組單元有無重複，有則再轉回去做加一操作，沒

有則說明得到了一個排列方案。