2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Нумерация всех комбинаций
Сообщение30.01.2014, 14:30 
Аватара пользователя
Помогите, пожалуйста, решить следующую задачу.

Имеется множество $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$.

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

 
 
 
 Re: Нумерация всех комбинаций
Сообщение30.01.2014, 15:59 
Аватара пользователя
1) Нумерации, удовлетворяющей обоим требованиям, может и не существовать.
2) Искать можно не только более удобную нумерацию, но и более простой алгоритм (как прямой, так и обратный) для уже выбранной нумерации.
В общем, компромиссы.

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

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

 
 
 
 Re: Нумерация всех комбинаций
Сообщение01.02.2018, 20:43 
Аватара пользователя
В английской википедии тоже есть: Combinatorial number system

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group