1

リストから同じサイズまたはリストより小さいすべての順列を見つけようとしています。

例えば：

>>>allPermutations([a,b])
[[a,b], [b,a], [a], [b]]

これは、現在 Python で使用している反復コードです。現時点でどれだけ効率的かはわかりません。

import itertools

def getAllPossibleSubSchedules( seq ):
    fullSet = set()
    curSet = set()
    curSet.add(tuple(seq))
    for i in reversed(range(1, len(seq) + 1)):
        permutations = set()
        for curTuple in curSet:
            permutationsList = list(itertools.permutations(curTuple, i))
            for permutation in permutationsList:
                permutations.add(permutation)
        curSet = set()
        for permutation in permutations:
            curSet.add(permutation)
            fullSet.add(permutation)
    return fullSet

アルゴリズムがnの合計を生成すると確信しています! 1 -> n 個の順列から、かなり急速に成長します。これまでのところ、多くの繰り返し操作を行うため、信じられないほど遅い再帰的な方法を作成しました。私は繰り返してそれをやろうとしていますが、繰り返し操作を制限する方法がわかりません。私はpythonを使用していますが、疑似コードも大いに役立ちます。どんな助けでも大歓迎です。前もって感謝します！

4

3 に答える 3

4

以下が機能するはずです。

from itertools import permutations

def allPermutations(seq):
    return (x for i in range(len(seq),0,-1) for x in permutations(seq, i))

例えば：

>>> list(allPermutations('abc'))
[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'b'), ('a',), ('b',), ('c',)]
于 2013-03-06T21:29:16.143 に答える
0

おそらく、可能なすべてのサイズのリストのすべての順列を反復します。明確にするために：

def all_permutations(input_list):
    for i in xrange(len(input_list)):
        sublist = input_list[:i]
        for variant in permutations(sublist):
            yield variant
于 2013-03-06T21:29:10.213 に答える
-1

permutations.add()あなたのandcurSet.add()と のfullSet.add()呼び出しにより、あなたのルーチンはすぐに停止してしまうと確信しています。配列のサイズを変更し続けると、割り当てられたメモリが「スペース不足」になり、新しい場所を見つける必要があります。これは、配列全体がコピーされることを意味します。そして、別の要素を追加します-すすぎと繰り返し。

必要な要素の数を計算し、そのためのスペースを事前に割り当てる必要があります。したがって、要素が 5 つある場合、最終結果には ( 5! + 5*4! + 10*3! + 10*2! + 5 ) x 5 要素を割り当てる必要があり、中間結果にはそれより少なくなります。次に、メモリのブロックをシャッフルせずにこれらの配列を埋めます。それは物事を大幅に高速化します。

于 2013-03-06T21:19:12.097 に答える