Алгоритм получения ранга конкретной комбинации элементов из ряда множеств - PullRequest
Новая
       1

Алгоритм получения ранга конкретной комбинации элементов из ряда множеств

0 голосов
/ 27 мая 2011

У меня есть несколько наборов, скажем, S1, S2, S3, ... Каждый набор имеет разные элементы.Скажем, S1 = {A, B, C}, S2 = {X, Y}, S3 = {P, Q, R, T}

Существует комбинация этих наборов K = {S1, S2,S3}.Например, экземпляром этой комбинации будет {A, X, P}.Очевидно, что возможны комбинации 3 x 2 x 4 = 24.Что мне нужно, так это «ранг» конкретной комбинации, рассчитанный с использованием простого упорядоченного перечисления слева направо и наоборот.

Очевидно, я могу легко вычислить это, просто перечислив все комбинации и сравнив ихна запрошенную комбинацию при сохранении счетчика, но мне нужен эффективный алгоритм, поскольку мои наборы могут содержать до 20000 элементов каждый, а количество комбинированных наборов для некоторого случая> 10.

Кстати, я знаюпоток Вычислить ранг комбинации? здесь в переполнении стека.Но, к сожалению, здесь это неприменимо, поскольку мои комбинации состоят из наборов разных размеров для разных позиций

Я был бы признателен за реализацию в C #, но другие языки или псевдокод также были бы очень полезны.

Любые предложения, пожалуйста

kemal

ОБНОВЛЕНИЕ: @spinning_plane & @aasmund.Спасибо за ответы.Они оба дают мне одну и ту же формулу для расчета ранга.

Но мне также нужен другой путь.т.е. получить комбинацию для данного ранга (на основе нуля).Например, если присвоить ранг 0, результатом будет {A, X, P}, для 3 {A, X, R} и т. Д. Кто-нибудь с алгоритмом, пожалуйста?

Ответы [ 2 ]

4 голосов
/ 27 мая 2011

Думайте о вашем наборе как о числе, возможные значения которого для каждой цифры - это размер соответствующего набора.Чтобы увидеть это, предположим, что размер каждого набора S1 ... S3 одинаков, скажем, 2 для простоты.Чтобы вычислить ранг набора, вы просто интерпретируете K как двоичное число и переведете его в его эквивалент 10.rank (x) - это просто индекс на основе 0 элемента в наборе. 

rank(A)*2^0 + rank(X)*2^1 + rank(P)*2^2

Теперь, чтобы обобщить это на случай, когда наборы могут быть разного размера, мы можем выписать выражение для вычисления

rank(A) + rank(X)*len(S1) + rank(P)*len(S2)*len(S1) ... etc.

В псевдо-коде 

input = {'a','b','x'}
output = 0;
cumulative = 1;
for i in range(len(K)):
     output += cumulative*rank(input[i],K[i]) # this returns the index of input[i] in set K[i]
     cumulative*=len(K[i])
3 голосов
/ 27 мая 2011

Так выглядит полная «ранжированная последовательность»? 

0: {A, X, P}
1: {A, X, Q}
2: {A, X, R}
3: {A, X, S}
4: {A, Y, P}
5: {A, Y, Q}
...

Если это так, пусть наборы нумеруются справа налево как S1 , S2 , ..., Sn , и пусть ранги выбранных элементов в их собственных наборах (например, A = 0, B = 1, C = 2) будут r1 , r2 , ..., рН .Формула должна тогда быть 

rn * |S(n-1)| * ... * |S2| * |S1| + ... + r3 * |S2| * |S1| + r2 * |S1| + r1

Почему?Допустим, мы выбрали {C, Y, Q}.Их ранговые ранги в соответствующих наборах равны 2, 1 и 2 соответственно.Поскольку крайний левый ранг равен 2, это означает, что для того, чтобы попасть в эту часть последовательности ранжирования, нам нужно, чтобы крайняя правая и средняя позиции выполнили два полных «раунда», всего (в данном случае) r2 * |S2| * |S1| = 2 * 2 * 4 = 16строк.Затем мы должны пропустить 1 раунд крайней правой позиции, чтобы достичь Y и т. Д.

Редактировать: формулу можно упростить до 

(((...) * |S3| + r3) * |S2| + r2) * |S1| + r1

(и это, безусловно, должнорассчитываться таким образом).Следите за целочисленным переполнением, кстати ...

...