12

同じ長さ N の 2 つのリスト L1 と L2 があるとします。prodSum を次のように定義します。

def prodSum(L1, L2) :
    ans = 0
    for elem1, elem2 in zip(L1, L2) :
        ans += elem1 * elem2

    return ans

L1 がソートされていると仮定して、prodSum(L1, L2) < 事前に指定された値となるような L2 の順列の数を見つけるための効率的なアルゴリズムはありますか?

問題を簡単にするために、L1 と L2 はどちらも [1, 2, ..., N] の整数のリストであると仮定できます。

編集：マナグの答えは、L1とL2が[1、2、...、N]からの整数のリストであると仮定しないと、これは不可能だと確信しました。この制約を前提としたソリューションにはまだ興味があります。

4

4 に答える 4

9

最初に数学に関するある程度の混乱を解消し、次に 2 つの解決策について議論し、そのうちの 1 つのコードを示したいと思います。

yes-no クラス NP によく似た #P と呼ばれるカウント クラスがあります。質的にはNPよりも難しいです。このカウント問題が #P-hard よりも優れていると信じる特別な理由はありませんが、それを証明するのは難しいか簡単かもしれません.

ただし、多くの #P 困難問題と NP 困難問題は、実際に解決するのにかかる時間が大きく異なります。特定の困難な問題でさえ、入力のプロパティに応じて難しくなったり、簡単になったりすることがあります。NP 困難または #P 困難が意味するのは、困難なケースがあるということです。一部の NP 困難および #P 困難問題には、困難なケースが少ないか、完全に簡単なケースさえあります。(他のケースでは、最も難しいケースよりもはるかに簡単に見えるケースがほとんどありません。)

したがって、実際の問題は、関心のある入力に大きく依存する可能性があります。しきい値が高い側または低い側にある、または適切な数のキャッシュされた結果に対して十分なメモリがあるとします。次に、2 つのアイデアを利用する便利な再帰アルゴリズムがあります。そのうちの 1 つは既に述べたものです。そのうちの。(2) メモリが許す限り、残りのしきい値と一部のリスト フラグメントの小計をキャッシュする必要があります。キャッシングを改善するには、リストの 1 つから要素を順番に選択することもできます。

このアルゴリズムを実装する Python コードを次に示します。

list1 = [1,2,3,4,5,6,7,8,9,10,11]
list2 = [1,2,3,4,5,6,7,8,9,10,11]
size = len(list1)
threshold = 396     # This is smack in the middle, a hard value

cachecutoff = 6     # Cache results when up to this many are assigned

def dotproduct(v,w):
    return sum([a*b for a,b in zip(v,w)])

factorial = [1]
for n in xrange(1,len(list1)+1):
    factorial.append(factorial[-1]*n)

cache = {}

# Assumes two sorted lists of the same length

def countprods(list1,list2,threshold):
    if dotproduct(list1,list2) <= threshold:            # They all work
        return factorial[len(list1)]
    if dotproduct(list1,reversed(list2)) > threshold:   # None work
        return 0
    if (tuple(list2),threshold) in cache:               # Already been here
        return cache[(tuple(list2),threshold)]
    total = 0
    # Match the first element of list1 to each item in list2
    for n in xrange(len(list2)):
        total += countprods(list1[1:],list2[:n] + list2[n+1:],
            threshold-list1[0]*list2[n])
    if len(list1) >= size-cachecutoff:
        cache[(tuple(list2),threshold)] = total
    return total

print 'Total permutations below threshold:',
print countprods(list1,list2,threshold)
print 'Cache size:',len(cache)

コメント行にあるように、しきい値のハード値を使用してこのコードをテストしました。すべての順列に対する単純な検索よりもかなり高速です。

3 つの条件が満たされる場合、このアルゴリズムよりも優れた別のアルゴリズムがあります: (1) 適切なキャッシュを作成するのに十分なメモリがない、(2) リスト エントリが小さな負でない整数である、(3)最も難しいしきい値に関心があります。この 2 番目のアルゴリズムを使用する 2 番目の状況は、他の条件が満たされているかどうかに関係なく、すべてのしきい値のカウントをフラットにしたい場合です。長さ n の 2 つのリストにこのアルゴリズムを使用するには、まず n 階乗より大きい 10 または 2 のべき乗である基数 x を選択します。今マトリックスを作る

M[i][j] = x**(list1[i]*list2[j])

Ryser の公式を使用してこの行列 M のパーマネントを計算すると、基数 x のパーマネントの k 桁目が、内積が正確に k である順列の数を示します。さらに、Ryser 式は、すべての順列を直接合計するよりもかなり高速です。(しかし、それでも指数関数的であるため、パーマネントの計算が #P 困難であるという事実と矛盾しません。)

また、順列の集合が対称群であることは事実です。このカウントの問題を加速するために、何らかの方法で群論を使用できれば素晴らしいことです。しかし、私の知る限り、その質問の説明からはそれほど深いものは何も得られません。

最後に、しきい値を下回る順列の数を正確にカウントするのではなく、その数を概算するだけでよい場合、おそらくゲームは完全に変わります。(パーマネントを多項式時間で概算できますが、ここでは役に立ちません。) どうすればよいかを考えなければなりません。いずれにせよ、それは提起された問題ではありません。

上記の説明と上記のコードに欠けている別の種類のキャッシング/動的プログラミングがあることに気付きました。コードに実装されているキャッシングは初期段階のキャッシングです。list1 の最初の数個の値だけが list2 に割り当てられ、残りのしきい値が複数回発生した場合、キャッシュによりコードは結果を再利用できます。これは、list1 と list2 のエントリが大きすぎない整数である場合にうまく機能します。ただし、エントリが典型的な浮動小数点数である場合は、失敗したキャッシュになります。

ただし、list1 のほとんどの値が割り当てられている場合は、反対側で事前計算することもできます。この場合、残りのすべての値の小計のソート済みリストを作成できます。そして、list1 を順番に使い切って、list2 側ですべての順列を実行できることを覚えておいてください。たとえば、list1 の最後の 3 つのエントリが [4,5,6] であり、list2 の 3 つの値 (中間のどこか) が [2.1,3.5,3.7] であるとします。次に、6 つの内積のソート済みリストをキャッシュします。

endcache[ [2.1, 3.5, 3.7] ] = [44.9, 45.1, 46.3, 46.7, 47.9, 48.1]

これはあなたにとって何をしますか？私が投稿したコードを見ると、関数 countprods(list1,list2,threshold) はサブスレッショルドで再帰的に動作します。最初の引数 list1 は、引数としてではなく、グローバル変数として使用する方が適している可能性があります。list2 が十分に短い場合、リスト endcache[list2] でバイナリ検索を実行することにより、countprods ははるかに高速に作業を行うことができます。(スタックオーバーフローから、これが Python の bisect モジュールに実装されていることを知りましたが、いずれにせよパフォーマンス コードは Python では記述されません。) ヘッド キャッシュとは異なり、エンド キャッシュはコードを大幅に高速化できます。 list1 と list2 のエントリ間に数字の一致はありません。Ryser のアルゴリズムは、数値の一致がなければこの問題にも悪臭を放ちます。そのため、このタイプの入力では、2 つの加速度しか見られません。

于 2009-12-05T23:30:02.393 に答える
7

おそらくそうではありません（単純化する仮定なしで）：あなたの問題は NP-Hard です。これはSUBSET-SUMへの簡単な還元です。「 prodSum count_perms(L1, L2, x)(L1, L2) < x となるような L2 の順列の数をカウントする」という関数を表現します。

SUBSET_SUM(L2,n): # (determine if any subset of L2 adds up to n)
    For i in [1,...,len(L2)]
        Set L1=[0]*(len(L2)-i)+[1]*i
        calculate count_perms(L1,L2,n+1)-count_perms(L1,L2,n)
        if result positive, return true
    Return false

したがって、関数を効率的に計算する方法があれば、count_perms(L1, L2, x)SUBSET_SUM(L2,n) を計算する効率的なアルゴリズムが得られます。

于 2009-11-29T03:10:56.603 に答える
2

これも抽象代数の問題です。しばらく時間が経ちましたが、ここでいくつかのことを始めましょう。以下については特に重要なことは何もありません (すべて非常に基本的なものです。すべてのグループが順列グループに同型であるという事実の拡張です) が、問題を別の方法で見ることができます。

かなり標準的な表記法に固執しようとします。「x」はベクトルであり、「x i」は x の i番目のコンポーネントです。"L" がリストの場合、Lは同等のベクトルです。" 1 n " はすべての成分が 1 のベクトルです。自然数の集合 ℕ は正の整数と見なされます。"[a,b]" は、a から b までの整数のセットです。"θ( x , y )" は、 xとyによって形成される角度です。

注prodSumは内積です。この問題は、θ( L1 , L ) が所定の角度 α より小さいような L2 の操作 (要素の置換) によって生成されたすべてのベクトルLを見つけることと同じです。この操作は、プレゼンテーションを使用してサブスペースを介して ℕ<sup>n 内のポイントを反映することと同じです。

< ℕ<sup>n | ( x i x j -1 ) (i,j) ∈ A >

ここで、i と j は [1,n] にAあり、少なくとも 1 つの要素を持ち、(i,i) はありませんA(つまり、| | > 0の [1,n] 2Aの非再帰サブセットです)。より明確に (そしてよりあいまいに) 述べると、部分空間は、1 つまたは複数のコンポーネントが 1 つまたは複数の他のコンポーネントと等しいポイントです。リフレクションは、列がすべて標準基底ベクトルである行列に対応します。A

リフレクション グループに "RP n "という名前を付けましょう(別の名前を付ける必要がありますが、メモリに失敗します)。RP nは対称群 S nと同形です。したがって

|RP n | = |S n | =ん！

3 次元では、次数 6 の群が得られます。反射群は、立方体対称群のサブグループとしての三角形対称群D 3です。1 nに沿った線の周りでL2を π/3 ずつ回転させることによって、点を生成することもできます。これはモジュラー群 ℤ<sub>6 であり、これは可能な解決策を示しています: 次数 n の群を見つけてください! 最小数のジェネレーターを使用し、それを使用して、 L2との角度が増加してから減少するシーケンスとして L2 の順列を生成します。そこから、要素Lを θ( L1 , L) < α 直接 (たとえば、各シーケンスの前半をビンサーチして遷移点を見つけることができます。これにより、条件を満たすシーケンスの残りを指定し、O(1) 時間でカウントできます)。この群を RP' nとしましょう。

RP' 4は ℤ<sub>6 に同型の 4 つの部分空間で構成されます。より一般的には、RP' nは、RP' n-1に同型の n 個の部分空間で構成されます。

これは、私の抽象代​​数の筋肉が実際に機能しなくなるところです。私は建設に取り組み続けようとしますが、マナグの答えはあまり希望を残していません. RP 3を ℤ<sub>6 に削減することが、私たちができる唯一の有効な削減ではないかと心配しています。

于 2009-12-02T03:34:19.073 に答える
0

l1 と l2 が両方とも high->low (または low->high など、同じ順序である場合) に順序付けられている場合、結果は最大化され、逆に順序付けられている場合、結果は最小化され、その他のように見えます。順序の変更は、いくつかの規則に従っているようです。整数の連続したリストで 2 つの数値を交換すると、それらの距離に関連しているように見える一定量だけ合計が常に減少します (つまり、1 と 3 または 2 と 4 を交換しても同じ効果があります)。これはちょっといじっただけですが、アイデアは、最大値と最小値があり、事前に指定された値がそれらの間にある場合、それを可能にする順列をカウントする方法があるということです (ただし;リストが均等に配置されていない場合は、そうではありません.まあ、私が知っていることではありません.l2が(1 2 4 5)の場合、1 2と2 4を交換すると異なる効果があります）

于 2009-11-29T03:57:44.540 に答える