VPF::Разбиение на классы эквивалентности

Dims

Дата 14.11.2007, 02:51 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1016
Регистрация: 21.11.2006

Репутация: 1
Всего: 11

Уже задавал похожий вопрос, теперь упрощаю.

Пусть есть N объектов, которые можно идентифицировать по номерам: 0, 1, 2, ..., N-1

Требуется по очереди генерировать разбиения на классы эквивалентности (разбиение на классы эквивалентности -- это разделение всех объекты на группы равных или неравных).

Возможный алгоритм.

Внешний цикл: пробегаем количество классов эквивалентности K от 1 до N
Внутренний цикл: генерируем размещения N различимых объектов по K неразличимым "ящикам"

Таким образом, вопрос сводится к тому, как генерировать такие размещения?

Усложнение: генерировать при условии, что про некоторые объекты известно, что они должны лежать в разных классах эквивалентности.

Что-то не могу сообразить: сколько вообще существует размещений N различимых объектов по K неразличимым "ящикам"?

Dims

Дата 14.11.2007, 04:10 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1016
Регистрация: 21.11.2006

Репутация: 1
Всего: 11

Вроде бы, получилось достаточно просто.

Правильно ли*

Цитата

Рассмотрим многовариантное дерево процесса раскладывания n различимых объектов по классам.

0-й объект можно положить только в один класс, пусть он так же будет 0-й.

1-й объект можно положить либо в 0-й (уже существующий) класс, либо в 1-й класс (завести новый).

Итого, каждый i-й объект можно положить либо в один из уже заведённых к тому времени j классов, либо завести ещё один класс.

Кстати, объекты подаются в строго определённом порядке.

Итак, размещение объектов кодируется многозначным числом.
Каждая цифра обозначает класс, в который положен соответствующий объект. Классы нумеруются в порядке заведения.

Первая цифра всегда 0, так как 0-й объект можно положить только в один новый класс эквивалентности.

Вторая цифра либо 0, либо 1.

Каждая следующая цифра может принимать значения от 0, до значения предыдущей цифры, увеличенного на 1.

Цифры располагаются слева-направо в порядке, описанном выше.

Самое первое число есть последовательность нулей, что означает, что все объекты помещаются в единственный класс эквивалентности.

Перебор чисел происходит путём "увеличения на единицу", которое происходит почти обычным образом: самый младший (правый) разряд увеличивается насколько можно, когда больше некуда, он сбрасывается на 0 и увеличивается более старший (левый) разряд, по тем же принципам.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »