Calculate combination index

✔ Recommended Answer


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.


Answered By: Sammitch

Method #2

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

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:

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

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

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.


Most Popular

Remove Unicode Zero Width Space PHP

PhpStorm, return value is expected to be 'A', 'object' returned

Laravel file upload returns forbidden 403, file permission is 700 not 755