Algorithm for combination index in array

Question

I know how to compute the binomial coefficient given n and k (and I use a library for that). Now imagine you store all of those combinations inside an array. Each combination has an index. I don't actually need to store them in an array, but I need to know, if I were to store them, what the array index would be for each combination.

E.g. given an element of the C(n,k) set of possible combinations, I need a function that gives me its index i inside the array, withtout actually creating the whole array. The programming language does not matter, though I need to implement the function in java, but any (pseudo-)language algorithm will do, I will then translate it to java.

For example, in the case of n=5 and k=2, I empirically define this function f(n, k, [a,b]) => N as:

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

meaning that the (3,5) combination would occupy index 8 in the array. Another example with n=5 and k=3 is f(n, k, [a,b,c]) => N, empirically defined as

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 for clarification after comments:

In the example above [1,2,3], [2,4,5] and so on, are one of the elements of the C(n,k) set, e.g. one of the possible combinations of k numbers out of n possible numbers. The function needs them in order to compute their index in the array.

However I need to write this function for generic values of n and k and without creating the array. Maybe such a function already exists in some combinatorial calculus library, but I don't even know how it would be called.

@wildplasser no, I'm afraid it's not. The number of elements in the array is the binomial coefficient of n and k, e.g. n!/(k!(n-k)!) — Lucio Crusca
– Lucio Crusca, Commented Jun 11, 2016 at 14:04
You are talking about the contents of the array. I was talking about the array's size ( := number of elements), in your case (5*4/2) is 10. — wildplasser
– wildplasser, Commented Jun 11, 2016 at 14:10
No, I'm talking about array size too. 5*2 is also 10, but that does not mean the correct function is n*k. — Lucio Crusca
– Lucio Crusca, Commented Jun 11, 2016 at 14:13
Hint2: the index is the number of elements before it. (assuming base zero indexing) — wildplasser
– wildplasser, Commented Jun 11, 2016 at 14:23

triangular · Accepted Answer · 2016-06-11 16:22:05Z

You should have a look at the combinatorial number system, the section "Place of a combination in the ordering" in particular.

There is even an example, which might help you: National Lottery example in Excel. (I'm sorry, but I can't type any math in here.)

In your case this would be

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

or if you accept a reversed order, you may omit the binom(5,3) - 1 part and calculate

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

(This should save you some time, as binom(5, 3) is not really necessary here.)

In Java the method could be

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;
}

or

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;
}

assuming a method int binom(int n, int k) and binom(n, k) = 0 for n < k.

Collectives™ on Stack Overflow

Algorithm for combination index in array

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related