Python は効率的な順列および結合アルゴリズムを実装します-Python チュートリアル-php.cn

Python は効率的な順列および結合アルゴリズムを実装します

高洛峰

リリース： 2016-10-18 10:37:19

オリジナル

2254 人が閲覧しました

組み合わせアルゴリズム

このプログラムのアイデアは、添字が 1 から m までの数値を表す配列を開くことです。配列要素の値は 1 であり、その添字

で表される数値が選択されることを意味します。、0の場合は選択されていません。

まず初期化し、配列の最初の n 要素を 1 に設定します。これは、最初の組み合わせが最初の n 個の数値であることを示します。

次に、配列要素の値の「10」の組み合わせを左から右にスキャンし、最初の「10」の組み合わせを見つけたら、それを

「01」の組み合わせに変更し、同時にすべての「」を移動します。その左側の 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

Python を使用して実装します:

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):
  
    &#39;第一步：先把10换成01&#39;
    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 ベースの方法を使用します。 N 個のセルの配列を想定し、最初のセルに 1 つ追加し、完全な N に達したら

1 つ追加します。加算するたびに、各ビット配列単位が重複しているかどうかを確認し、重複があれば戻って加算操作を行い、重複がなければ配置計画が得られたことを意味する。