Python은 효율적인 순열 및 조합 알고리즘을 구현합니다.

조합 알고리즘

이 프로그램의 아이디어는 배열을 여는 것이며, 아래 첨자는 1부터 m까지의 숫자를 나타내며, 배열 요소의 값은 1입니다. 아래첨자

로 표현되는 것은 Selected이고, 0이면 선택되지 않은 것이다.

먼저 초기화하고 배열의 처음 n개 요소를 1로 설정합니다. 이는 첫 번째 조합이 처음 n개 숫자임을 나타냅니다.

그런 다음 배열 요소 값의 "10" 조합을 왼쪽에서 오른쪽으로 스캔합니다. 첫 번째 "10" 조합을 찾은 후

"01" 조합으로 변경합니다. 시간 변경 첫 번째 "10" 조합 모든 "1"이 배열의 가장 왼쪽 끝으로 이동됩니다.

첫 번째 "1"이 배열의 m-n 위치로 이동하면, 즉 n개의 "1"이 모두 가장 오른쪽 끝으로 이동하면 마지막 조합에 도달합니다

.

예를 들어 5개 중 3개를 선택하는 조합을 찾습니다.

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

파이썬을 사용하여 구현:

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)

전체 순열 알고리즘

1에서 N까지, 전체 순열을 출력하여 총 N! 조각.

분석: N-base 방법을 사용합니다. N개의 셀 배열을 가정하고 첫 번째 셀에 하나를 추가하고 전체 N에 도달하면

하나를 추가합니다. 하나씩 추가할 때마다 각 비트 어레이 단위가 반복되는지 확인하고, 반복이 있으면 다시 돌아가서 추가 작업을 수행하면 배열 계획이 확보되었음을 의미합니다.