配列の組み合わせインデックスのアルゴリズム

Question

binomial coefficientのnとkの計算方法を知っています（それにライブラリを使用しています）。 これらの組み合わせをすべて配列内に格納するとします。各組み合わせにはインデックスがあります。実際に配列に格納する必要はありませんが、配列を格納する場合は配列のインデックスはどの組み合わせになるのかを知る必要があります。

など。可能な組み合わせのC（n、k）集合の要素が与えられていれば、実際に配列全体を作成することなく、配列内にそのインデックスiを与える関数が必要です。プログラミング言語は問題ではありませんが、私はこの関数をjavaで実装する必要がありますが、任意の（擬似）言語アルゴリズムはそれをjavaに変換します。

例えば、N = 5、K = 2の場合には、私が経験的に、この機能f(n, k, [a,b]) => Nを定義：

（3,5）の組み合わせは、配列内のインデックス8を占有することを意味

f(5, 2, [1,2]) = 0 
f(5, 2, [1,3]) = 1 
f(5, 2, [1,4]) = 2 
f(5, 2, [1,5]) = 3 
f(5, 2, [2,3]) = 4 
f(5, 2, [2,4]) = 5 
f(5, 2, [2,5]) = 6 
f(5, 2, [3,4]) = 7 
f(5, 2, [3,5]) = 8 
f(5, 2, [4,5]) = 9 

は。 、[1,2,3]上記の例では

、[2,4：N = 5、K = 3の他の例は、経験的に

f(5, 3, [1,2,3]) = 0 
f(5, 3, [1,2,4]) = 1 
f(5, 3, [1,2,5]) = 2 
f(5, 3, [1,3,4]) = 3 
f(5, 3, [1,3,5]) = 4 
f(5, 3, [1,4,5]) = 5 
f(5, 3, [2,3,4]) = 6 
f(5, 3, [2,3,5]) = 7 
f(5, 3, [2,4,5]) = 8 
f(5, 3, [3,4,5]) = 9 

コメント後の明確化のためEDITとして定義され、f(n, k, [a,b,c]) => Nあります5]などは、C（n、k）集合の要素の1つです。 n個の可能な番号のうちのk個の数字の可能な組合せの1つ。この関数は配列内のインデックスを計算するために関数を必要とします。

しかし、この関数はnとkの一般的な値と、配列を作成しないで書く必要があります。おそらく、このような関数がいくつかのコンビナトリアル計算ライブラリに既に存在しているかもしれませんが、私はそれがどのように呼び出されるか分かりません。

Answer 1

「combinatorial number system」のセクション「注文の組み合わせの場所」をご覧ください。

さらに役立つ例があります：National Lottery example in Excel。 （申し訳ありませんが、私はここで任意の数学を入力することはできません。）

あなたのケースでは、これは

f(5, 3, [2,3,4]) = binom(5,3) - 1 - binom(5-2,3) - binom(5-3,2) - binom(5-4,1) = 
       = 10 - 1 - 1 - 1 - 1 = 6 

たり、逆の順序を受け入れるならば、あなたはbinom(5,3) - 1一部を省略することになりますと、この方法は、可能性がJavaでは

f'(5, 3, [2,3,4]) = binom(5-2,3) + binom(5-3,2) + binom(5-4,1) - 1 = 
        = 1 + 1 + 1 - 1 = 2 

（binom(5, 3)はここで本当に必要ではありませんので、これは、あなたにいくつかの時間を節約する必要があります。）

計算

int f(int n, int k, int[] vars) { 
    int res = binom(n, k) - 1; 

    for(int i = 0; i < k; i++) { 
     res -= binom(n - vars[i], k - i); 
    } 

    return res; 
} 

又は

int fPrime(int n, int k, int[] vars) { 
    int res = -1; 

    for(int i = 0; i < k; i++) { 
     res += binom(n - vars[i], k - i); 
    } 

    return res; 
} 

int binom(int n, int k)

方法及びn < kためbinom(n, k) = 0を想定。