Python implementiert einen effizienten Permutations- und Kombinationsalgorithmus

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
  
    &#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)

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.