Python implements efficient permutation and combination algorithm

Combination Algorithm

The idea of ​​​​this program is to open an array, whose subscript represents 1 to m numbers. The value of the array element is 1, which means that the number represented by its subscript

is selected, and if it is 0, it is not selected.

First initialize, set the first n elements of the array to 1, indicating that the first combination is the first n numbers.

Then scan the "10" combinations of the array element values ​​from left to right. After finding the first "10" combination, change it into the

"01" combination, and at the same time move all the "1"s to the left of it to the array the far left end of.

When the first "1" moves to the m-n position of the array, that is, when all n "1"s move to the rightmost end, the last combination is reached.

For example, find the combination of choosing 3 out of 5:

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

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

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

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

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

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

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

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

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

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

Use python to implement:

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):
  
    '第一步：先把10换成01'
    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)

Full permutation algorithm

From 1 to N, output the full permutation, total N! strip.

Analysis: Use the N-base method. Assume an array of N cells, add one to the first cell, and add

one when full N is reached. Every time one is added, check whether each bit array unit is repeated. If there is any duplication, go back and do the addition operation. If there is no repetition, it means that an arrangement plan has been obtained.