Calculate combination index

✔ Recommended Answer

Math.

function getIndex($lists, $a, $b, $c) {    $a_pos = array_search($a, $lists['first']);    $b_pos = array_search($b, $lists['second']);    $c_pos = array_search($c, $lists['third']);        $a_len = count($lists['first']);    $b_len = count($lists['second']);    $c_len = count($lists['third']);        return $c_pos + ( $b_pos * $c_len ) + ( $a_pos * $b_len * $c_len );}

If you look at your list of indexes and how the values repeat in the columns it should be obvious how this works.

But once you have lists of indeterminate or changing lengths, non-perfect orderings, or gaps in the lists this will break down immediately. At that point you'll likely need a hash table, and at that point you should be putting this data in a database instead.

In fact, you probably should already unless this is purely a learning exercise.

Source: stackoverflow.com

Answered By: Sammitch

Method #2

To calculate the index of a combination, you can use the following formula:

scss
index = C(n, k) - C(n - a[1], k) - C(n - a[2], k - 1) - ... - C(n - a[k-1], 2) - a[k]

where n is the total number of items, k is the size of the combination, a is an array containing the indices of the selected items (0-indexed), and C(n, k) is the binomial coefficient, which can be calculated as:

scss
C(n, k) = n! / (k! * (n-k)!)

Here's an example code snippet in Python that implements this formula:

perl
import math

def combination_index(n, k, a):
    index = math.comb(n, k)
    for i in range(k):
        index -= math.comb(n - a[i], k - i)
    return index - 1  # 0-indexed

# Example usage:
n = 5
k = 3
a = [1, 3, 4]
index = combination_index(n, k, a)
print(index)  # Output: 8

In this example, the combination_index function takes in n, k, and a as arguments, where n is the total number of items, k is the size of the combination, and a is a list of the indices of the selected items. The function returns the 0-indexed index of the combination in the list of all possible combinations of size k of n items.