Kombinationsalgorithmus
Die Idee dieses Programms besteht darin, ein Array zu öffnen, der Index stellt die Zahl von 1 bis m dar, der Wert des Array-Elements ist 1, was bedeutet, dass die Zahl Dargestellt durch den Index
ist Ausgewählt, wenn es 0 ist, ist es nicht ausgewählt.
Zuerst initialisieren, die ersten n Elemente des Arrays auf 1 setzen, was angibt, dass die erste Kombination die ersten n Zahlen sind.
Scannen Sie dann die „10“-Kombination des Array-Elementwerts von links nach rechts. Nachdem Sie die erste „10“-Kombination gefunden haben, ändern Sie sie in
„01“-Kombination und gleichzeitig Ändern Sie mit der Zeit die erste „10“-Kombination. Alle „1“ werden an das äußerste linke Ende des Arrays verschoben.
Wenn sich die erste „1“ an die m-n-Position des Arrays bewegt, d. h. wenn sich alle n „1“ an das äußerste rechte Ende bewegen, ist die letzte Kombination erreicht
.
Finden Sie zum Beispiel die Kombination für die Auswahl von 3 aus 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
Verwenden Sie Python zur Implementierung:
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
'第二步：把第一个10前面的所有１放在数组的最左边'
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)Vollständiger Permutationsalgorithmus
Geben Sie von 1 bis N die vollständige Permutation aus, insgesamt N! Streifen.
Analyse: Verwenden Sie die N-Base-Methode. Nehmen Sie ein Array von N Zellen an, fügen Sie eine zur ersten Zelle hinzu und fügen Sie
eine hinzu, wenn die volle N erreicht ist. Überprüfen Sie jedes Mal, wenn eine Bit-Array-Einheit hinzugefügt wird. Wenn es eine Wiederholung gibt, gehen Sie zurück und führen Sie die Additionsoperation durch. Wenn es keine Wiederholung gibt, bedeutet dies, dass ein Anordnungsplan erhalten wurde.
