プロジェクト オイラーの問題の 1 つを解決しようとしています。結果として、セットのすべての可能なパーティションを任意の順序で見つけるのに役立つアルゴリズムが必要です。
たとえば、 set が与えられた場合2 3 3 5:
2 | 3 3 5
2 | 3 | 3 5
2 | 3 3 | 5
2 | 3 | 3 | 5
2 5 | 3 3
等々。セットのメンバーのほぼすべての可能な組み合わせ。もちろん、ネットを検索しましたが、私は高度な数学ではなくプログラマーを話すので、直接役立つ情報はあまり見つかりませんでした。
誰でもこれで私を助けることができますか? 私は BASIC から Haskell まで、ほとんどすべてのプログラミング言語を読むことができるので、好きな言語で投稿してください。
探索木を考えたことはありますか? 各ノードは要素を配置する場所の選択を表し、リーフ ノードは答えです。Project Euler の楽しみの一部なので、コードは提供しません ;)
を見てみましょう：
The Art of Computer Programming, Volume 4, Fascicle 3: すべての組み合わせとパーティションの生成
7.2.1.5. 設定されたすべてのパーティションの生成
一般に、構成の数を計算するために使用される再帰の構造を調べ、それらを列挙するために同様の再帰を作成します。整数と構成の間の1対1のマッピングを計算するのが最善です。これは、順列、組み合わせなどに適切に機能し、各構成が1回だけ列挙されるようにします。
現在、いくつかの同一アイテムのパーティション数の再帰でさえ、かなり複雑です。
マルチセットのパーティションの場合、カウントは、プロジェクトオイラー問題181の一般化を任意のマルチセットに解決することになります。
さて、問題には 2 つの側面があります。
まず、アイテムは任意の順序で配置できます。したがって、N 個の項目の場合、N 個あります。順列（アイテムが一意として扱われると仮定）。
第 2 に、分割を示す各アイテム間のビット フラグとしてグループ化を想定できます。これらのフラグは N-1 個あるため、特定の順列では 2^(N-1) 個のグループ化が可能です。
これは、N 個のアイテムの場合、合計 N!*(2^(N-1)) 個のグループ化/順列が存在し、非常に急速に大きくなることを意味します。
あなたの例では、上位 4 つの項目は 1 つの順列のグループ化です。最後の項目は、別の順列のグループ化です。あなたのアイテムは次のように見ることができます：
2 オン 3 オフ 3 オフ 5
2 オン 3 オン 3 オフ 5
2 オン 3 オフ 3 オン 5
2 オン 3 オン 3 オン 5
2 オフ 5 オン 3 オフ 3
順列 (表示の順序) は、他の 2 つが述べたように、それらをツリーのように見て導き出すことができます。これにはほぼ確実に、hereのような再帰が含まれます。グループ化は、多くの点でそれらから独立しています。すべての順列を取得したら、必要に応じてそれらをグループ化にリンクできます。
問題のこの部分に必要なコードは次のとおりです。
def memoize(f):
memo={}
def helper(x):
if x not in memo:
memo[x]=f(x)
return memo[x]
return helper
@memoize
def A000041(n):
if n == 0: return 1
S = 0
J = n-1
k = 2
while 0 <= J:
T = A000041(J)
S = S+T if k//2%2!=0 else S-T
J -= k if k%2!=0 else k//2
k += 1
return S
print A000041(100) #the 100's number in this series, as an example
これを行うためのコードをすぐに作成しました。ただし、実際に必要かどうかわからなかったので、指定されたリストのすべての可能な組み合わせを分離することを省略しましたが、必要に応じて簡単に追加できるはずです。
いずれにせよ、コードは少量であれば非常にうまく動作しますが、CodeByMoonlight が既に述べたように、可能性の量は非常に急速に増加するため、それに応じてランタイムが増加します。
とにかく、ここにpythonコードがあります：
import time
def separate(toseparate):
"Find every possible way to separate a given list."
#The list of every possibility
possibilities = []
n = len(toseparate)
#We can distribute n-1 separations in the given list, so iterate from 0 to n
for i in xrange(n):
#Create a copy of the list to avoid modifying the already existing list
copy = list(toseparate)
#A boolean list indicating where a separator is put. 'True' indicates a separator
#and 'False', of course, no separator.
#The list will contain i separators, the rest is filled with 'False'
separators = [True]*i + [False]*(n-i-1)
for j in xrange(len(separators)):
#We insert the separators into our given list. The separators have to
#be between two elements. The index between two elements is always
#2*[index of the left element]+1.
copy.insert(2*j+1, separators[j])
#The first possibility is, of course, the one we just created
possibilities.append(list(copy))
#The following is a modification of the QuickPerm algorithm, which finds
#all possible permutations of a given list. It was modified to only permutate
#the spaces between two elements, so it finds every possibility to insert n
#separators in the given list.
m = len(separators)
hi, lo = 1, 0
p = [0]*m
while hi < m:
if p[hi] < hi:
lo = (hi%2)*p[hi]
copy[2*lo+1], copy[2*hi+1] = copy[2*hi+1], copy[2*lo+1]
#Since the items are non-unique, some possibilities will show up more than once, so we
#avoid this by checking first.
if not copy in possibilities:
possibilities.append(list(copy))
p[hi] += 1
hi = 1
else:
p[hi] = 0
hi += 1
return possibilities
t1 = time.time()
separations = separate([2, 3, 3, 5])
print time.time()-t1
sepmap = {True:"|", False:""}
for a in separations:
for b in a:
if sepmap.has_key(b):
print sepmap[b],
else:
print b,
print "\n",
これは、QuickPerm アルゴリズムに基づいています。詳細については、QuickPerm を参照してください。
基本的に、私のコードは n 個の分離を含むリストを生成し、それらを指定されたリストに挿入してから、リスト内の分離のすべての可能な順列を見つけます。
したがって、あなたの例を使用すると、次のようになります。
2 3 3 5
2 | 3 3 5
2 3 | 3 5
2 3 3 | 5
2 | 3 | 3 5
2 3 | 3 | 5
2 | 3 3 | 5
2 | 3 | 3 | 5
0.000154972076416 秒。
しかし、私はあなたがやっている問題の問題の説明を読んで、あなたがこれをどのように解決しようとしているのかを理解していますが、ランタイムがどれだけ速く増加するかを見て、あなたが期待するほど速く動作するとは思いません. Project Euler の問題は約 1 分で解決するはずです。