9

私が現在取り組んでいるプロジェクトでは、自分のプログラムでやりたいことの約 80% を実装しており、その結果には非常に満足しています。

残りの 20% では、解決方法が少しわからない問題に直面しています。ここにあります：

いくつかの数字 (任意の長さ) を含むリストのリストを作成しました。たとえば:

listElement[0] = [1, 2, 3]
listElement[1] = [3, 6, 8]
listElement[2] = [4, 9]
listElement[4] = [6, 11]
listElement[n] = [x, y, z...]

ここで、n は最大 40,000 程度に達する可能性があります。

リストの各要素が (数学的な意味で) 数値のセットであると仮定すると、相互に排他的なセットのすべての組み合わせを導き出すことが目的です。つまり、上記のリスト要素のパワーセットと同様ですが、互いに素ではない集合要素はすべて除外されます。

したがって、n=4 の例を続けると、次の組み合わせを持つリストを作成したいと思います。

newlistElement[0] = [1, 2, 3]
newlistElement[1] = [3, 6, 8]
newlistElement[2] = [4, 9]
newlistElement[4] = [6, 11] 
newlistElement[5] = [[1, 2, 3], [4, 9]]
newlistElement[6] = [[1, 2, 3], [6, 11]]
newlistElement[7] = [[1, 2, 3], [4, 9], [6, 11]]
newlistElement[8] = [[3, 6, 8], [4, 9]]
newlistElement[9] = [[4, 9], [6, 11]

たとえば、[[1, 2, 3], [3, 6, 8]] の組み合わせは無効です。これは、3 が 2 つの要素で共通であるためです。これを行うエレガントな方法はありますか？フィードバックをお寄せいただき、誠にありがとうございます。

最初のリストには非常に多数の要素が含まれる可能性があり (n は最大 40000 になる可能性があると述べたように)、非常に多くの要素でべき乗セットを取得すると決して終了しないため、べき乗関数を実行したくないことも指定する必要があります。 .

4

6 に答える 6

4

以下は再帰ジェネレーターです。

def comb(input, lst = [], lset = set()):
   if lst:
      yield lst
   for i, el in enumerate(input):
      if lset.isdisjoint(el):
         for out in comb(input[i+1:], lst + [el], lset | set(el)):
            yield out

for c in comb([[1, 2, 3], [3, 6, 8], [4, 9], [6, 11]]):
   print c

これは、多くのセットに共通の要素がある状況では、他のソリューションよりもはるかに効率的である可能性があります (もちろん、最悪の場合でも、パワーセットの2**n要素を反復処理する必要があります)。

于 2012-11-26T22:04:22.507 に答える
4

私はジェネレーターを使用します：

import itertools

def comb(seq):
   for n in range(1, len(seq)):
      for c in itertools.combinations(seq, n): # all combinations of length n
         if len(set.union(*map(set, c))) == sum(len(s) for s in c): # pairwise disjoint?
            yield list(c)

for c in comb([[1, 2, 3], [3, 6, 8], [4, 9], [6, 11]]):
   print c

これにより、次が生成されます。

[[1, 2, 3]]
[[3, 6, 8]]
[[4, 9]]
[[6, 11]]
[[1, 2, 3], [4, 9]]
[[1, 2, 3], [6, 11]]
[[3, 6, 8], [4, 9]]
[[4, 9], [6, 11]]
[[1, 2, 3], [4, 9], [6, 11]]

結果を単一のリストに保存する必要がある場合:

print list(comb([[1, 2, 3], [3, 6, 8], [4, 9], [6, 11]]))
于 2012-11-26T20:30:44.550 に答える
3

以下のプログラムで使用されている方法は、素ではないセットを除外するという点で以前のいくつかの回答に似ているため、通常、すべての組み合わせをテストするわけではありません。可能な限りすべてのセットを貪欲に除外することで、以前の回答とは異なります。これにより、NPE のソリューションよりも数倍高速に実行できます。以下は、0 から 20 の範囲の要素を持つ 200、400、... 1000 個のサイズ 6 セットの入力データを使用して、2 つの方法の時間を比較したものです。

Set size =   6,  Number max =  20   NPE method
  0.042s  Sizes: [200, 1534, 67]
  0.281s  Sizes: [400, 6257, 618]
  0.890s  Sizes: [600, 13908, 2043]
  2.097s  Sizes: [800, 24589, 4620]
  4.387s  Sizes: [1000, 39035, 9689]

Set size =   6,  Number max =  20   jwpat7 method
  0.041s  Sizes: [200, 1534, 67]
  0.077s  Sizes: [400, 6257, 618]
  0.167s  Sizes: [600, 13908, 2043]
  0.330s  Sizes: [800, 24589, 4620]
  0.590s  Sizes: [1000, 39035, 9689]

上記のデータでは、左の列は実行時間を秒単位で示しています。数字のリストには、単一結合、二重結合、または三重結合がいくつ発生したかが示されます。プログラム内の定数は、データ セットのサイズと特性を指定します。

#!/usr/bin/python
from random import sample, seed
import time
nsets,   ndelta,  ncount, setsize  = 200, 200, 5, 6
topnum, ranSeed, shoSets, shoUnion = 20, 1234, 0, 0
seed(ranSeed)
print 'Set size = {:3d},  Number max = {:3d}'.format(setsize, topnum)

for casenumber in range(ncount):
    t0 = time.time()
    sets, sizes, ssum = [], [0]*nsets, [0]*(nsets+1);
    for i in range(nsets):
        sets.append(set(sample(xrange(topnum), setsize)))

    if shoSets:
        print 'sets = {},  setSize = {},  top# = {},  seed = {}'.format(
            nsets, setsize, topnum, ranSeed)
        print 'Sets:'
        for s in sets: print s

    # Method by jwpat7
    def accrue(u, bset, csets):
        for i, c in enumerate(csets):
            y = u + [c]
            yield y
            boc = bset|c
            ts = [s for s in csets[i+1:] if boc.isdisjoint(s)]
            for v in accrue (y, boc, ts):
                yield v

    # Method by NPE
    def comb(input, lst = [], lset = set()):
        if lst:
            yield lst
        for i, el in enumerate(input):
            if lset.isdisjoint(el):
                for out in comb(input[i+1:], lst + [el], lset | set(el)):
                    yield out

    # Uncomment one of the following 2 lines to select method
    #for u in comb (sets):
    for u in accrue ([], set(), sets):
        sizes[len(u)-1] += 1
        if shoUnion: print u
    t1 = time.time()
    for t in range(nsets-1, -1, -1):
        ssum[t] = sizes[t] + ssum[t+1]
    print '{:7.3f}s  Sizes:'.format(t1-t0), [s for (s,t) in zip(sizes, ssum) if t>0]
    nsets += ndelta

編集: functionaccrueでは、引数(u, bset, csets)は次のように使用さ れ
ます 。 の最初の行がによって置き換えられ 、7 番目の行が によって置き換えられた 場合 (つまり、パラメーターが並べ替えられ、u と bset にデフォルトが指定された場合)、を介して呼び出して、互換性のある共用​​体のリストを生成できることに注意してください。


accrue
def accrue(csets, u=[], bset=set()):

for v in accrue (ts, y, boc):
accrue[accrue(listofsets)]

ValueError: zero length field name in formatPython 2.6 を使用した場合に発生するというコメントに記載されているエラーについては、次のことを試してください。

# change:
    print "Set size = {:3d}, Number max = {:3d}".format(setsize, topnum)
# to:
    print "Set size = {0:3d}, Number max = {1:3d}".format(setsize, topnum)

プログラム内の他のフォーマットでも同様の変更 (適切なフィールド番号の追加) が必要になる場合があります。2.6ページの新機能には、「str.format() メソッドのサポートが Python 2.6 にバックポートされました」と記載されていることに注意してください。フィールド名または番号が必要かどうかは示されていませんが、それらのない例は示されていません。対照的に、2.7.3 ではどちらの方法でも機能します。

于 2012-11-27T02:39:08.933 に答える
1

itertools.combinations、set.intersectionおよびfor-elseループを使用：

from itertools import *
lis=[[1, 2, 3], [3, 6, 8], [4, 9], [6, 11]]
def func(lis):
    for i in range(1,len(lis)+1):
       for x in combinations(lis,i):
          s=set(x[0])
          for y in x[1:]:
              if len(s & set(y)) != 0:
                  break
              else:
                  s.update(y)    
          else:
              yield x


for item in func(lis):
    print item

出力：

([1, 2, 3],)
([3, 6, 8],)
([4, 9],)
([6, 11],)
([1, 2, 3], [4, 9])
([1, 2, 3], [6, 11])
([3, 6, 8], [4, 9])
([4, 9], [6, 11])
([1, 2, 3], [4, 9], [6, 11])
于 2012-11-26T20:51:47.927 に答える
1

NPE のソリューションに似ていますが、再帰がなく、リストを返します。

def disjoint_combinations(seqs):
    disjoint = []
    for seq in seqs:
        disjoint.extend([(each + [seq], items.union(seq))
                            for each, items in disjoint
                                if items.isdisjoint(seq)])
        disjoint.append(([seq], set(seq)))
    return [each for each, _ in disjoint]

for each in disjoint_combinations([[1, 2, 3], [3, 6, 8], [4, 9], [6, 11]]):
    print each

結果：

[[1, 2, 3]]
[[3, 6, 8]]
[[1, 2, 3], [4, 9]]
[[3, 6, 8], [4, 9]]
[[4, 9]]
[[1, 2, 3], [6, 11]]
[[1, 2, 3], [4, 9], [6, 11]]
[[4, 9], [6, 11]]
[[6, 11]]
于 2012-11-27T01:05:17.990 に答える
0

itertools パッケージを使用しないワンライナー。これがあなたのデータです：

lE={}
lE[0]=[1, 2, 3]
lE[1] = [3, 6, 8]
lE[2] = [4, 9]
lE[4] = [6, 11]

ワンライナーは次のとおりです。

results=[(lE[v1],lE[v2]) for v1 in lE for v2  in lE if (set(lE[v1]).isdisjoint(set(lE[v2])) and v1>v2)]
于 2012-11-26T20:56:20.070 に答える