Нумерация всех комбинаций

[B@R5uk]

Помогите, пожалуйста, решить следующую задачу.

Имеется множество $E$ перенумерованных объектов (их количество $M$). Из этого множества выбирается подмножество $S$. Требуется составить некоторую функцию (некоторое соответствие), которая перенумеровывала бы все возможные подмножества $S$. То есть, при фиксированном $M$, каждому подмножеству сопоставить некоторое целое число. Причём, если подмножества разные, то сопоставляемые им числа так же должны быть разными (обратимость функции), а если в одном подмножестве элементов больше, чем во втором, то его номер должен быть больше номера второго соответственно.

Очевидно, что количество всех способов выбрать подмножество $S$ из множества $E$ будет равно $2^M$ (включая сюда пустое подмножество $S$). Логично тогда перенумеровать все комбинации подмножеств $S$ числами от 0 до $2^M-1$. Каждому биту этого номера поставить в соответствие один элемент исходного множества $E$ и, если этот бит равен единице, то потребовать, чтобы этот элемент принадлежал подмножеству $S$. При такой нумерации подмножеств числу $0$ будет соответствовать пустое подмножество, числу $2^M-1$ — подмножество состоящее из всего множества $E$, числам $2^k$, где $k$ от $0$ до $M-1$ — подмножества из, соответственно, единственного элемента с номером $k$ (если считать, что элементы множества $E$ нумеруются от $0$ до $M-1$). И всё бы хорошо, но...

Но эта нумерация не удовлетворяет требованию

Цитата:

если в одном подмножестве элементов больше, чем в другом, то его номер должен быть больше номера второго соответственно

Например, при указанной выше нумерации подмножество номер $8$ состоит из одного элемента (номер $3$), а подмножество номер $7$ состоит из трёх элементов исходного множества с номерами $0$, $1$ и $2$.

Первый шар на пути к решению, если я не ошибаюсь, это вспомнить биномиальные коэффициенты. Количество пустых подмножеств равно единице, количество подмножеств из одного элемента — $M$, количество подмножеств из двух элементов — $M(M-1)/2$ и так далее. Для подмножества из $k$ элементов — $\frac{M!}_{k!(M-k)!}$. Сумма всех этих чисел равна $2^M$. Можно записать отдельно для подмножеств из фиксированного числа $k$ элементов все возможные выборки. Номера выбираемых элементов записать в порядке возрастания, все записи отсортировать в порядке возрастания их позиционной записи, а затем все эти последовательности для разных $k$ записать друг за другом в порядке возрастания $k$ и перенумеровать от $0$ до $2^M-1$. Получится что-то типа этого:

0   ничего
 1   1
 2   2
 3   3
 4   4
 5   1, 2
 6   1, 3
 7   1, 4
 8   2, 3
 9   2, 4
10   3, 4
11   1, 2, 3
12   1, 2, 4
13   1, 3, 4
14   2, 3, 4
15   1, 2, 3, 4

И всё бы хорошо, но...

Но эта нумерация очень неудобна в плане вычисления обратной функции. То есть если ввести функцию, которая по заданному числу элементов исходного множества $M$, заданному номеру комбинации $N$ и заданному номеру элемента $m$ исходного множества будет возвращать единицу или ноль в случае, когда, соответственно, этот элемент $m$ принадлежит подмножеству с номером $N$, то эта функция будет весьма трудоёмко и некрасиво выражаться через числа $M$, $N$ и $m$. Вспомните ту красоту для самой первой приведённой мной комбинации: обратная функция возвращает бит с номером $m$ в двоичной записи числа $N$.

И так вопрос: как надо перенумеровать все комбинации, чтобы обратная функция вычислялась бы красиво и просто.

[svv]

1) Нумерации, удовлетворяющей обоим требованиям, может и не существовать.
2) Искать можно не только более удобную нумерацию, но и более простой алгоритм (как прямой, так и обратный) для уже выбранной нумерации.
В общем, компромиссы.

[B@R5uk]

В книге Окулов - Программирование в алгоритмах в главе "Комбинаторные алгоритмы" есть примеры генерации сочетания по его номеру в лексикографическом порядке и вычисление номера по сочетанию. В купе с вычислением биномиальных коэффициентов эти алгоритмы можно обобщить для решения поставленной мной выше задачи.

Надо же! Четыре года ушло на поиск решения.

[maxal]

В английской википедии тоже есть: Combinatorial number system