xorがゼロである整数のパーティションの数を計算する効率的な方法を探しています。F（n、c）=＃{（x1、x2、...、xc）| x1 + x2 + ... + xc = n＆x1 xor x2 xor ... xor xc = 0}
nとcの値が小さい場合、ネストされたループを実行してこれらの値を計算するのは簡単です。しかし、より大きな値の場合、それは扱いにくいです。動的計画法を可能にする閉じた形または少なくとも再帰式を取得したいのですが。
1 に答える
1
あなたの問題の制約が特に巧妙で非常に自明でない解決策につながらない限り、研究数学の最先端にある非常に難しい質問をしていると思います。
まず、整数の単純な無制限の分割を数えること (つまり、正の整数の和として整数を表現する区別可能で順序に依存しない方法の数を数えること) は、何百年も前の歴史を持つ深い数学の問題です。
http://en.wikipedia.org/wiki/Partition_%28number_theory%29#Partition_function_formulas
いくつかの追加の非正統的な制約があります---最初に、特定の数の用語を持つパーティションのサブセットのみが必要であり(これにより簡単になる可能性があります)、次に、おそらく扱いが非常に難しい用語です。
n をどのくらいの大きさにするつもりですか? 上記の参照は、p(1000) がおよそ 2.44 * 10^31 であることを示しています。
n が大きければ、c も小さくなると思いますか? それは物事を非常に単純化するでしょう。
問題を解決するには、この分野を専門とする研究数学者の関心を引く必要があります。
www.aimath.org/news/partition/
「パーティション」をキーワードとして使用して、Math Overflow を試すことができます。
正確に c (この部分には 'k' を使用) の個々の部分への分割に関するこのスレッドを見つけました。これは、あなたの最初の (より簡単な) 制約です。
于 2011-11-22T09:39:06.143 に答える