効率的な配列組合せアルゴリズム--「プログラミングビーズ磯」--python実現

コンビネーションアルゴリズム本プログラムの考え方は,1個の配列を開き,その下付き文字は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 1 0 1 0//1,2,4 1 0 1 1 0//1,3,4 0 1 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 0 1 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を使用して実装:
方法1:

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

#最初の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     １        '

    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)

方法2:
 

charters = ['A', 'B', 'C', 'D', 'E', 'F']

s4 = time.time()

group = [1, 1, 1, 0, 0, 0]

group_len = len(group)

ret_num = (group_len * (group_len - 1) * (group_len - 2)) / 6

#   group  １     

indexes = [0, 1, 2]

for i in xrange(ret_num - 1):



    '''



       ：  10  01

       ：    10     １        



    '''

    tmp = []

    #location:   10     

    #  　indexes　                ，    　group　    10    

    #[tmp.append(charters[i]) for i in indexes]

    tmp.append(charters[indexes[0]])

    tmp.append(charters[indexes[1]])

    tmp.append(charters[indexes[2]])

    print tmp

    

    if indexes[0] + 1 < indexes[1]:

        location = indexes[0]

        indexes[0] = location + 1



    #  　indexes　                ，    　group　    10   

    elif indexes[1] + 1 < indexes[2]:

        location = indexes[1]

        indexes[1] = location + 1

        #　indexes　   １    ，    １      ０，    　group　      

        group[indexes[1] - 1] = 0

        group[0] = 1

        indexes[0] = 0



    #  　indexes　           ，    　group　    10    

    elif indexes[0] + 1 == indexes[1] and indexes[1] + 1 == indexes[2]:

        location = indexes[2]

        indexes[2] = location + 1

        group[indexes[0]] = 0

        group[indexes[1]] = 0

        group[0] = 1

        group[1] = 1

        indexes[0] = 0

        indexes[1] = 1



    if location < 5:

        group[location] = 0

        group[location + 1] = 1

    else:

        group[location] = 1





print time.time() - s4,'*************'

#print ret,'**********'

第2の方法は最適化され,かなり効率が高い.1600億余りのサイクル計算をテストしたが,方法は1分で22分,方法は2分で1分しかかからなかった.
全配列アルゴリズム1からNまで、出力全配列、共N!バー.分析:N進法を使いましょう.1つのN個のユニットの配列を設けて、第1のユニットに対して1つの操作をして、満Nは1に入ります.1回加算するたびに各配列ユニットが重複しているかどうかを判断し,ある場合は戻って加算操作を行い,ない場合は配列案を説明した.