2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



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


26/05/12
1534
приходит весна?
Помогите, пожалуйста, решить следующую задачу.

Имеется множество $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 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Нумерация всех комбинаций
Сообщение07.01.2018, 11:51 
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Нумерация всех комбинаций
Сообщение01.02.2018, 20:43 
Модератор
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group