Генерация перестановок из n элементов с минимальными изменениями.

Генерация булеана конечного множества.

Определение 1. Пусть дано некоторое множество A. Булеаном множества А называется множество, состоящее из всех подмножеств А.

Как получить булеан множества А? Пусть множество А состоит из n элементов. Тогда каждое его подмножество B можно задать характеристической последовательностью из n нулей и единиц. Единица на i-м месте последовательности означает, что i-й элемент множества А входит в подмножество В, ноль – что не входит. Таким образом, вместо генерации всех подмножеств данного множества можно генерировать всевозможные последовательности из нулей и единиц длины n.

Генерация всех последовательностей длины n из нулей и единиц в лексикографическом порядке.

Определим лексикографический порядок на множестве последовательностей. Будем считать, что последовательность a предшествует последовательности b, если первые i членов у этих последовательностей одинаковы, а i+1 – й член у последовательности a меньше.

Последовательности из нулей и единиц можно считать двоичными числами. Тогда последовательность a предшествует b, если ее двоичное число меньше. Сгенерировать все n – разрядные двоичные числа очень просто. Нужно начать с числа 000…0 и прибавлять по единице до тех пор, пока не получим число 111…1. Для того, чтобы прибавить к двоичному числу единицу, необходимо перебирать цифры данного числа справа налево до тех пор, пока в каком-нибудь разряде не встретим 0. Затем этот разряд нужно сделать равным 1, а все разряды, лежащие справа от него, сделать нулями.

Генерация всех последовательностей длины n из чисел 0,1…k-1 в лексикографическом порядке.

Аналогично можно генерировать все последовательности длины n из чисел 0,1,…k-1. Начинаем с последовательности 000…0. Печатаем очередную последовательность. Строим по ней следующую. Для этого, двигаясь с конца последовательности, находим элемент, который меньше k-1. Увеличиваем его на 1, а все элементы, расположенные правее его, делаем нулями. Печатаем следующую последовательность и т.д. Процесс продолжается до тех пор, пока все элементы последовательности не станут равны k-1.

Коды Грея длины n.

Часто возникает необходимость генерировать все подмножества данного множества таким образом, чтобы следующее подмножество получалось из предыдущего добавлением или удалением одного элемента. В терминах характеристических последовательностей это означает, что каждая следующая характеристическая последовательность отличается от предыдущей в одном разряде. Набор всех последовательностей из нулей и единиц длины n, удовлетворяющих этому свойству, называется бинарным кодом Грея. Наиболее часто применяют рефлексивный бинарный код Грея.

Приведем рефлексивный бинарный код Грея для n=1,2,3.

Если отбросить старший разряд, станет понятно, почему данный код называется рефлексивным (т.е. отраженным). Дело в том, что вторая половина значений в оставшейся части кода Грея эквивалентна первой половине, только в обратном порядке. В примере для n=2 и n=3 первая и вторая половины выделены желтым и синим цветом. Если же разделить каждую половину ещё раз пополам, свойство будет сохраняться для каждой из половин половины и т. Д.

Будем начинать генерацию с последовательности 000…0. Для продолжения процесса генерации нам необходимо на каждом шаге знать номер разряда, который будет на этом шаге изменяться. Будем хранить эти номера в массиве y. Очевидно, что в массиве должно быть 2ⁿ – 1 элементов. Элемент y_i будет обозначать номер разряда, который изменяется при переходе от i – той последовательности к следующей. В примере справа от кодов Грея записаны элементы массива yдля n=1,2,3. Если мы знаем массив у кода Грея для i элементов, нетрудно получить значения элементов массива y для i+1- го элемента. Для этого нужно переписать старый массив y, затем записать в массив i, а затем снова переписать старый массив y.Это наблюдение позволяет написать несложную программу генерации кода Грея длины n.

Если сравнить номера элементов последовательности кодов Грея и элементы массива y, можно заметить, что y_i – это количество нулей, которыми заканчивается число i+1 в двоичной записи. Чтобы получить y_i , нужно найти максимальную степень двойки, на которую делится i+1. Это позволяет написать следующую версию программы генерации кода Грея:

Генерация всех последовательностей длины n из чисел 0,1…k-1 с минимальными изменениями.

Требуется перечислить все последовательности длины n из чисел 0,..k-1 в таком порядке, чтобы каждая следующая отличалась от предыдущей в единственной цифре, причем не более, чем на 1.

Генерация сочетаний в лексикографическом порядке.

Рассмотрим множество Z = {1,2,3,…n}. Требуется сгенерировать все его подмножества, состоящие из k элементов.

Будем считать, что элементы нашего подмножества располагаются в порядке возрастания. Начинаем с подмножества {1,2,3,…k}. По предыдущему подмножеству {x₁,x₂,…,x_k} будем строить следующее таким образом: просматривая наше подмножество справа налево, находим самый первый элемент, не достигший максимального значения. Очевидно, что максимальное значение для x_k равно n, для x_k-1 – n-1 и т. д. Найденный элемент x_i увеличиваем на 1, а все элементы справа от него делаем самыми маленькими из возможных: x_i+1 = x_i +1, x_i+2 = x_i+1 +1 и.т.д.

Генерация перестановок из n элементов в лексикографическом порядке.

Рассмотрим множество Z = {1,2,3,…n}. Требуется сгенерировать все перестановки элементов множества Z.

Меняем местами x_i с x_j. Теперь элементы справа от x_i образуют убывающую последовательность. Переписываем элементы от x_i+1 до x_n в обратном порядке.

Генерация перестановок из n элементов с минимальными изменениями.

Рассмотрим множество Z = {1,2,3,…n}. Требуется сгенерировать все перестановки элементов множества Z. При этом необходимо, чтобы каждая следующая перестановка получалась из предыдущей при помощи одной транспозиции (перестановки) двух соседних элементов. Например, при n = 3 допустим такой порядок: 3 2 1 -> 2 3 1 -> 2 1 3 -> 1 2 3 -> 1 3 2 -> 3 1 2.

Теперь вспомним решение задачи о генерации всех последовательностей длины n из чисел 0,1…k-1 с минимальными изменениями. Заменим прямоугольную доску доской в форме лестницы (пронумеруем вертикали от 0 до n-1, высота i-ой вертикали равна i). Двигая шашки по тем же правилам, мы сгенерируем все возможные последовательности y. Параллельно с изменением yбудем корректировать перестановку. Для этого можно искать в ней число i+1, но это требует лишних действий. Поэтому мы будем для получения i+1 в массиве inv_x хранить перестановку, обратную нашей, изменяя ее по мере необходимости.

Первой будет сгенерирована перестановка n,n-1,…1. Ей соответствует последовательность yиз одних нулей.

Не нашли, что искали? Воспользуйтесь поиском по сайту: