私はTopCoderの問題を解決しようとしています。基本的に私が必要としているのは、次のアルゴリズムです。
S = [1、2、...、n]をシーケンスとします。mをn未満とします。
1）サイズmのSのすべてのサブシーケンスを見つけます（これは簡単です-n ^ m）。
2）要素が降順ではないサイズmのSのすべてのサブシーケンスを見つけます。
3）要素の繰り返しが許可されていないサイズmのSのすべてのサブシーケンスを検索します（これも簡単です-（n！）/（（nm）！）。
4）要素が降順ではなく、繰り返しが許可されていない、サイズmのSのすべてのサブシーケンスを検索します。
まだパート2と4の公式を見つけようとしています。少し助けていただければ幸いです。
前もって感謝します。
編集：
元の問題：
https://docs.google.com/document/d/1X1VK8Vq2DlqMbZpXHGLoWv9ULfRLVoLtMTRRU5nh5qs/edit?usp=sharing
4) を解決するには、反復なしの「非減少」は「増加」を意味することに注意してください。m要素を繰り返さずに構築された長さのすべてのシーケンスのセットを、サブシーケンスでS発生する要素のセットによって定義される等価クラスに分割します。各等価クラス内には、増加するシーケンスが 1 つだけあります (要素は で並べられ<ます)。各等価クラスのサイズは、要素の順列の数です。4)-シーケンスの数です(n!)/((n-m)! * m!) = n \choose m。
ad 2)、 のすべての要素の一連の出現回数 (含まれていない場合は 0 を含む) としてシーケンスをモデル化しSます。(s_i, k_i), i=1..n; s_i \in S, k_i \in IN, \foreach p,q in {1..n}, p!=q: s_p != s_qこれは、正確に長さのペアのシーケンスとして記述できますn。「非減少」は、増加に従って要素を配置することによって与えられるシーケンスの一意の許容順序を意味しs_iます。したがって、唯一の自由度は、 m: に合計するという制約に従わなければならない出現回数ですsum_{i=1..n} k_i = m。
この問題は、(特定の) 制限があり、ラティス パスをカウントするパーティションと同等です。IN^nこの条件を満たすn タプルの数の閉じた式はないと思います。
ただし、すべての可能性を列挙する標準アルゴリズムがあります。ここ