私は最初に数学についてのある程度の混乱を払拭し、次に2つの解決策について話し合い、そのうちの1つにコードを与えたいと思います。

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

ただし、多くの#P困難問題とNP困難問題は、実際に解決するのにかかる時間が大幅に異なり、1つの特定の困難な問題でさえ、入力のプロパティに応じて困難または容易になる可能性があります。NP困難または#P困難が意味するのは、ハードケースがあるということです。一部のNP困難および#P困難の問題には、それほど困難ではない場合や、まったく簡単な場合もあります。（他の人は、最も難しいケースよりもはるかに簡単に見えるケースがほとんどありません。）

したがって、実際の質問は、関心のある入力に大きく依存する可能性があります。しきい値がハイサイドまたはローサイドにあるか、キャッシュされた結果の適切な数に十分なメモリがあるとします。次に、2つのアイデアを利用する便利な再帰アルゴリズムがあります。そのうちの1つはすでに説明しました。（1）値の一部を割り当てた後、リストフラグメントの残りのしきい値によってすべての順列が除外されるか、すべてが許可される場合があります。そのうちの。（2）メモリが許せば、残りのしきい値とリストフラグメントの小計をキャッシュする必要があります。キャッシングを改善するには、リストの1つから要素を順番に選択することもできます。

このアルゴリズムを実装するPythonコードは次のとおりです。

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

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

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

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

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

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

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

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