Форум программистов [Powered by Invision Power Board]

Цитата

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

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

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

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

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

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

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

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

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

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

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

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