조합 알고리즘
이 프로그램의 아이디어는 배열을 여는 것이며, 아래 첨자는 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) #替换位置从第一个0的位置开始 location = number0_loc #判断第一个0和第一个1的位置哪个在前, #如果第一个0的位置小于第一个1的位置, #那么替换位置从第一个1位置后面找起 if number0_loc < number1_loc: location = group[number1_loc:].index(0) + number1_loc group[location] = 1 group[location - 1] = 0 '第二步:把第一个10前面的所有1放在数组的最左边' 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에 도달하면
하나를 추가합니다. 하나씩 추가할 때마다 각 비트 어레이 단위가 반복되는지 확인하고, 반복이 있으면 다시 돌아가서 추가 작업을 수행하면 배열 계획이 확보되었음을 의미합니다.