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

У меня есть куча наборов, скажем, 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 #, но другие языки или псевдокод также были бы очень полезны.

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

кемаль

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

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


.net rank algorithm combinations
person Kemal Erdogan    schedule 27.05.2011    source источник

Ответы (2)


arrow_upward
4
arrow_downward

Думайте о своем наборе как о числе, возможные значения каждой цифры которого являются размером связанного набора. Чтобы увидеть это, предположим, что размер каждого набора 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])
person dfb    schedule 27.05.2011
comment
Еще раз спасибо за эту ценную помощь. Я также очень ценю ответ от Осмунда. Но я принимаю ваш, поскольку вы также предоставили для него псевдокод. - person Kemal Erdogan; 30.05.2011

arrow_upward
3
arrow_downward

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

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. Тогда формула должна быть

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

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

person Aasmund Eldhuset    schedule 27.05.2011