1

たとえば、2 つの文字 A と B が与えられた場合、x A と y B を持つ長さ n のすべての文字列を生成したいと思います。

これを効率よく進めていきたい。私が考えた 1 つの方法は、長さ x の A のリストを作成し、y の B をあらゆる方法でリストに挿入することです。しかし、Python リストへの挿入は直線的であるため、リストが大きくなると、この方法はうまくいきません。

パフォーマンスの目標 (これは不合理かもしれませんが、私の希望です): A と B の数が等しい長さ 20 のすべての文字列を 1 分以内に生成します。

編集: permutations('A' * x, 'B' * y) の使用が提案されています。悪い考えではありませんが、多くのことを無駄にしています。x = y = 4 の場合、文字列 'AAAABBBB' を何度も生成します。各文字列を一度だけ生成するより良い方法はありますか? set(permutations('A' * x, 'B' * y)) の効果を持つコードを試しましたが、遅すぎます。

4

3 に答える 3

3

パフォーマンスに関するあなたの懸念に関して、これはあなたのアイデアの実際のジェネレーター実装です（なしinsert）。の位置が検索され、それBに応じてリストが埋められます。

import itertools

def make_sequences(num_a, num_b):
    b_locations = range(num_a+1)
    for b_comb in itertools.combinations_with_replacement(b_locations, num_b):
        result = []
        result_a = 0
        for b_position in b_comb:
            while b_position > result_a:
                result.append('A')
                result_a += 1
            result.append('B')
        while result_a < num_a:
            result.append('A')
            result_a += 1
        yield ''.join(result)

パフォーマンスは向上します。Greg Hewgillのソリューションとの比較(命名make_sequences2):

In : %timeit list(make_sequences(4,4))
10000 loops, best of 3: 145 us per loop

In : %timeit make_sequences2(4,4)
100 loops, best of 3: 6.08 ms per loop

編集

一般化されたバージョン:

import itertools

def insert_letters(sequence, rest):
    if not rest:
        yield sequence
    else:
        letter, number = rest[0]
        rest = rest[1:]
        possible_locations = range(len(sequence)+1)
        for locations in itertools.combinations_with_replacement(possible_locations, number):
            result = []
            count = 0
            temp_sequence = sequence
            for location in locations:
                while location > count:
                    result.append(temp_sequence[0])
                    temp_sequence = temp_sequence[1:]
                    count += 1
                result.append(letter)
            if temp_sequence:
                result.append(temp_sequence)
            for item in insert_letters(''.join(result), rest):
                yield item

def generate_sequences(*args):
    '''
    arguments : squence of (letter, number) tuples
    '''
    (letter, number), rest = args[0], args[1:]
    for sequence in insert_letters(letter*number, rest):
        yield sequence

使用法： 

for seq in generate_sequences(('A', 2), ('B', 1), ('C', 1)):
    print seq

# Outputs
# 
# CBAA
# BCAA
# BACA
# BAAC
# CABA
# ACBA
# ABCA
# ABAC
# CAAB
# ACAB
# AACB
# AABC
于 2012-05-02T23:37:27.013 に答える
3

これを行う簡単な方法は次のとおりです。

import itertools

def make_sequences(x, y):
    return set(itertools.permutations("A" * x + "B" * y))

このitertools.permutations()関数は、入力リストで繰り返される要素を考慮しません。それは、以前に生成された順列の複製である順列を生成することになります。したがって、set()コンストラクターを使用すると、結果の重複要素が削除されます。

于 2012-05-02T23:05:32.047 に答える
1

これにより、アイデアが得られるはずです（何が起こっているかを確認できるように、すべてのステップを含めました）：

>>> x = 2
>>> y = 3
>>> lst_a = ['A'] * x
>>> lst_b = ['B'] * y
>>> print lst_a, lst_b
['A', 'A'] ['B', 'B', 'B']
>>> lst_a.extend(lst_b)
>>> lst_a
['A', 'A', 'B', 'B', 'B']
>>> print list(itertools.permutations(lst_a))
于 2012-05-02T23:06:02.783 に答える