1

入力セットが与えられると、そこからすべての事前注文関係 (または、同等にすべての弱い注文) を生成する、中途半端に効率的なアルゴリズムを探しています。n 個のラベル付き要素のすべての優先配置と呼ぶこともできます。

最初にサイズ n のすべての順列を生成し、次にそれらのサブシーケンスを '~' で折りたたむことによって、これを実装しようとしましたが、これは多くの重複のために非常に非効率的であり、いくつかの結果を逃しました。サイズは、Fubini 番号 1、1、3、13、75、541、4683、47293、545835、... (OEIS 番号 A000670) で指定され、n と共に急速に成長しています。n=8 まで、最初の数個だけが必要です。

例: A={a, b, c} で n=3 の場合、結果は 13 の予約注文になります。

b>a>c、b>a~c、b>c>a、b~c>a、c>b>a、c>a~b、c>a>b、a~c>b、a> c>b、a>b~c、a>b>c、a~bc、a~b~c

4

1 に答える 1

4

難しすぎない。Python 3 では:

import itertools

def weakorders(A):
    if not A:  # i.e., A is empty
        yield []
        return
    for k in range(1, len(A) + 1):
        for B in itertools.combinations(A, k):  # i.e., all nonempty subsets B
            for order in weakorders(set(A) - set(B)):
                yield [B] + order

などで呼び出しlist(weakorders(range(8)))ます。

于 2015-09-21T11:56:28.133 に答える