Чет про программирование / асимптотика

π i

m = n,

то опре-

Лемма 4. Если −→

имеет переставляемый элемент

̸

π i+1, . . . , π i+n

, число

n

является переставляе-

делены перестановки −→

−→

π j

при

j = i + 1, . . . , i + n

−

1

и не

мым элементом в перестановке −→

π i+n

. Кроме того,

является переставляемым элементом в перестановке −→

→−

\ {

}

→−

\ {

}

→−

\ {

}

π i+1

n

= π i+2

n

= . . . = π i+n

n

.

Доказательство леммы 4. По замечанию 1 имеем m ≠ 1. По за-

π i	имеет вид	( n , . . .)		или	(. . . , n )
мечанию 2 перестановка →−			←−				−→ . В теле
	π i		элементы		m	m	меняются
внешнего while-цикла в перестановке −→						,

местами, и над всеми элементами, б´ольшими чем m, стрелка меняет-

		π i+1.		Так как
ся на противоположную. Полученная перестановка есть →−
π i+1	( n , . . .)	или	(. . . , n )			. По
n > m > m , перестановка −→	имеет вид −→			←−
			π i+1		. Да-
замечанию 2 число n является переставляемым элементом в −→

лее снова по замечанию 2 число n будет переставляемым элементом

π i+2, . . . , π i+n 1							π i+n	, которая
в →−	−→	− . Поэтому определена перестановка −→
будет иметь вид (. . . ,			−→	или	←−	. Понятно, что направления всех
			n )		( n , . . .)
			π i+1, . . . , π i+n				совпадают. Лемма 4 доказана.
чисел в перестановках →−					−→

Теперь индукцией по n покажем, что алгоритм P Min(n) корректен, строит все перестановки из Sn без повторений, и для любого i ≠ n! перестановка −→π i имеет переставляемый элемент, а −→π n! не имеет кандидата

для перемещения. Базис индукции n = 1 очевиден. Пусть для n − 1 всё доказано. Рассмотрим работу алгоритмов P Min(n) и P Min(n−1) одновременно. В силу замечания 2 алгоритмом P Min(n) будут напечатаны следующие n перестановок:

π

= (←− ←−

←−−−

←−

−→

−

1

1 , 2 , . . . , n 1, n ),

π

= (←− ←−

←−

←−−−

−→

−

2

1 , 2 , . . . , n , n

1),

.

.

.

π

= ( n , ←− ←−

←−−−

−→

n

←−

1 , 2 , . . . , n

−

1).

Так как

n

= . . . = π

n

= (←− ←−

←−−−

−→

\ {

}

\ {

}

1

−→

n

−

π

1 , 2 , . . . , n

1)

41

есть первая напечатанная алгоритмом P Min(n−1) перестановка, по ин-

−→n

дукционному предположению π \ {n} имеет переставляемый элемент

m1, при условии (n − 1)! ≠ 1, и m1 ≠ n. Тогда m1 — переставляемый

→− n

элемент в π , и по лемме 4 определены следующие n перестановок

−→π n+1, . . . , −→π 2n Sn, причём

→−	\ {		}	−→		\ {		}
π n+1		n		= . . . = π	2n		n

является второй напечатанной алгоритмом P Min(n−1) перестановкой.

π

2n

\ {

n

}

имеет переставляемый

По индукционному предположению →−

элемент m2, при условии (n

π

2n

имеет вид

−

1)! = 2, и перестановка →−

(←−

или

−→

̸

2 является

по лемме 4 и замечанию 2. Поэтому

m

n , . . .)

(. . . , n )

π 2n

и

m

= n

i

переставляемым элементом в −→

2

̸

. В общем случае в -м блоке

π

(i

−

1)n+1, . . . , π (i 1)n+n

S

n,

определены следующие n перестановок →−

−→

−

−→

−

\ {

}

−→

\ {

}

π

(i 1)n+1

n

= . . . = π in

n

есть i-я напечатанная алгоритмом P Min(n

π in

− 1) перестановка и −→

имеет переставляемый элемент mi

̸=

n, при условии (n − 1)!

̸= i.

При i

π in

имеет переставляемый эле-

= (n − 1)! − 1 перестановка −→

мент mn!−n ≠ n. По лемме 4 определены следующие n перестано-

π n! n+1, . . . , π n!

S

n, причём число

n

не является переставляе-

вок −→

−

−→

π n!

. По индукционному предположению перестанов-

мым элементом в →−

π n!

\ {

n

} из

S

n−1

не имеет кандидата для перемещения. Поэтому

ка −→

π n!

также не имеет кандидата для перемещения. Таким

перестановка −→

π i

имеет переставляемый эле-

образом, для любого i = n! перестановка →−

̸

π n!

не имеет кандидата для перемещения. После печати переста-

мент, а −→

π n!

и выхода из внутреннего while-цикла переменная

m

примет

новки −→

значение 1. Поэтому алгоритм P Min(n) остановит свою работу.

В результате работы алгоритма P Min(n) напечатанные перестановки πi, i = 1, . . . , n! разбиты на (n − 1)! блоков по n штук в каждом. В любом i-м блоке перестановки различаются между собой положением числа n, причём πin \ {n} является i-й напечатанной перестановкой

42

при работе алгоритма P Min(n−1). По индукционному предположению получаем πin \ {n} ̸= πi′n \ {n} при i ≠ i′. Следовательно, перестановки в разных блоках различны. Таким образом, мы получили все n! перестановок из Sn без повторений. Лемма 4 доказана.

Перейдём к программной реализации алгоритма Джонсона – Трот-

−→

тера. Чтобы задать перестановку с направлениями её компонент π , введём два массива π и τ, где π — собственно сама перестановка и τ

— массив из чисел −1, +1. Причём τi указывает направление числа πi:

+1 означает стрелку →, а −1 означает стрелку ← . Для формализации условия внутреннего while-цикла по числу m требуется найти его дублёра m . Если мы знаем number(m), номер позиции числа m в перестановке π и направление τm числа m, то дублёр определяется просто как m = πnumber(m)+ m . Поэтому для хранения номера числа m

в перестановке π введём ещё один массив σ = (σ1, . . . , σn) такой, что

σi = number(i) — номер позиции числа i в перестановке π. Другими словами, σ — обратная перестановка к π. Тогда для любого m имеем

π m = m и π m+ m = m . Условие, что m не кандидат для перемещения

→−

в π , означает, что π m+ m > m, за исключением двух ситуаций, когда мы находимся в крайних позициях следующего вида:

←−

π = (m, . . . ), σm = 1, τm = −1;

−→

π = (. . . , m), σm = n, τm = +1.

Поэтому нужно доопределить значения π0 и πn+1 так, чтобы в этих ситуациях число m не являлось кандидатом для перемещения. Например, полагаем π0 = πn+1 = n + 1. Тогда π0 > m и πn+1 > m для для любого m ≤ n.

В условии внутреннего while-цикла есть неравенство m > 1. Его можно исключить, если при m = 1 произойдёт выход из этого цикла. Это означает, что неравенство π m+ m > m не должно выполняться при m = 1. Так как π 1 = 1, для этого достаточно определить τ1 = 0. При этом ничего не нарушится, поскольку по замечанию 1 число 1 не

−→

является кандидатом для перемещения в любой перестановке π .

43

Алгоритм P Min(n) генерации всех перестановок в порядке минимального изменения

for i = 1 to n do begin

πi := i; τi := −1;

σi := i

end;

π0 := n + 1; πn+1 := n + 1; τ1 := 0;

m := 0;

while m ≠ 1 do begin

write(π1, . . . , πn); m := n;

while π m+ m > m do begin

τm := −τm; m := m − 1

end;

Swap(π m , π m+ m ); Swap(σm, σ m + m )

end.

Теорема 5. Алгоритм P Min(n) корректен и строит все перестановки из Sn без повторений в порядке минимального изменения за время O(n!).

Доказательство. Ввиду леммы 3 остается только оценить сложность T (n) алгоритма P Min(n). Из доказательства леммы 3 вытекает, что последовательность π1, π2, . . . , πn! всех перестановок из Sn,

44

= 1 + tkn−1 и

напечатанных в ходе работы алгоритма P Min(n), разбивается на n-

элементные блоки Snk, k = 1, . . . , (n − 1)!. Введём обозначения:

•In — число сравнений, выполняемых в условии внутреннего whileцикла во время работы алгоритма P Min(n);

•tin — число сравнений, выполняемых в условии внутреннего whileцикла во время работы алгоритма P Min(n), начиная с печати перестановки πi и до печати πi+1, i < n!;

•tnn! — число сравнений, выполняемых в условии внутреннего whileцикла во время работы алгоритма P Min(n), начиная с печати перестановки πn! и до окончания работы алгоритма.

Индукцией по n докажем, что

∑n

In = i!.

i=1

Действительно, базис индукции n = 1 очевиден. Пусть n ≥ 2 и для n−1

это равенство справедливо. Имеем

n!	(n−1)!
∑	∑ ∑
In = tni =	tni .
i=1	k=1 i: i Snk

Из доказательства леммы 3 следует, что число n является переставляемым элементом в первых n − 1 перестановках каждого блока Snk,

πkn \{n} есть k-я напечатанная перестановка во время работы алгоритма P Min(n−1), причём переставляемые элементы в перестановках πkn

и πkn \ {n} совпадают и не равны n. Следовательно, tknn

tin = 1 для любого i такого, что πi Snk и i ≠ kn. Учитывая индукционное предположение, получаем

	(n−1)!	(n−1)!	n
	∑	∑	∑
In =	(n − 1 + tnkn) =	(n + tnk−1) = n! + In−1 =	i!.
	k=1	k=1	i=1
		45

Очевидно, T (n) = O(n) + O(I ). Так как I		=	n	i! = n! + o(n!)13,
получаем T (n) = O(n!). Теоремаn5 доказана.	n		∑i=1

Более детальное сравнение сложности линейных алгоритмов генерации P Lex(n) и P Min(n) показывает, что алгоритм P Min(n) быстрее. Кроме того, алгоритм P Min(n) интересен тем, что перестановки выписываются в порядке минимального изменения, а это очень важно, если с порождаемой перестановкой в требуемом алгоритме необходимо производить какие-либо вычисления, связанные с элементами самой перестановки. В этом случае имеется возможность использовать результаты вычислений, полученные для предыдущей перестановки, отличающейся от следующей только лишь транспозицией соседних элементов.

2. Подмножества конечного множества

Пусть P(A) — множество всех подмножеств n-элементного множества

A = {a0, a1, . . . , an−1}. Мощность множества P(A) равна 2 n. Существует биективное отображение f : P(A) → En из множества всех подмножеств P(A) в n-мерный единичный куб E n,14 определяемое по правилу f(B) = χ B для произвольного подмножества B A, где

χ B = (χ B0 , . . . , χ Bn−1),

{

χ Bi =

1, если ai B,

0, если ai ̸ B.

Таким образом, задача генерации всех подмножеств заданного n элементного множества A сводится к задаче порождения всех n-разрядных двоичных последовательностей. Также отметим, что генерация всех двоичных векторов длины n по сути есть прохождение всех вершин n-мерного единичного куба без повторений.

13 f(n) = o(g(n)), если lim f(n) = 0: n→∞ g(n)

14 Здесь E n — множество вершин единичного куба, т. е. множество всех n-разряд- ных двоичных последовательностей.

46

Для любого целого положительного числа a существует его единственное двоичное представление (bn−1bn−2 . . . b1b0) 2 = a, где bi определяются из следующих соотношений:

a = b0 + b12 + b22 2 + . . . + bn−12 n−1,

bi {0, 1}, i = 0, . . . , n − 1.

Поэтому для любого a < 2 n существует единственное двоичное n-раз- рядное представление. Множество двоичных векторов длины n с лексикографическим порядком (E n, ) есть линейно упорядоченное множество с наименьшим элементом (0, 0, . . . , 0) и наибольшим элементом

(1, 1, . . . , 1), причём (bn−1 . . . b0) 2 есть номер вектора (bn−1, . . . , b0) относительно этого упорядочивания. Поэтому все n-разрядные двоичные последовательности можно сгенерировать следующим образом. Пробегая значение индекса i от 0 до 2 n − 1, по числу i восстанавливаем его двоичное представление длины n, т. е. двоичный вектор с номером i в

лексикографическом порядке. Однако такой алгоритм генерации не будет линейным, так как время восстановления двоичного представления длины n не ограничено константой. Поэтому требуется другой алгоритм генерации двоичных векторов.

2.1. Генерация двоичных векторов и подмножеств

Будем порождать все двоичные векторы длины n в лексикографическом порядке, начиная с наименьшего элемента. Как перейти от заданного вектора b = (bn−1, . . . , b0) к непосредственно следующему вектору в лексикографическом порядке? Просматривая справа налево вектор b, ищем самую правую позицию i такую, что bi = 0. Запишем в эту i-ю позицию 1, а все элементы bj, j < i, стоящие справа от bi, полагаем равными 0. Очевидно, что мы получим требуемый вектор.

Для программной реализации этого алгоритма дополним массив b = (bn−1, . . . , b0) элементом bn. При инициализации полагаем bn = 0. Для всех порождаемых последовательностей при поиске правой позиции i

47

элемент bn не изменяется, за исключением ситуации, когда генерируется последний вектор (1, 1, . . . , 1), i = n и bn станет равным 1. Поэтому равенство bn = 1 будет условием остановки алгоритма. Программная реализация данного алгоритма приведена в следующем псевдокоде.

Алгоритм V Lex(n) генерации всех двоичных векторов длины n

for i = 0 to n do bi := 0; while bn ≠ 1 do

begin

write (bn−1, bn−2, . . . , b0); i := 0;

while bi = 1 do begin

bi := 0; i := i + 1

end; bi := 1

end.

Оценим время T (n) работы алгоритма V Lex(n). Пусть W n — число проверок условия внутреннего while-цикла и Win — число проверок ра-

венства bi = 1. Очевидно, что T (n) = O(n) + O(W n) и W n = ∑n Win.

i=0

Проверка условия bi = 1 осуществляется тогда и только тогда, когда cj = 1 для любого j < i, где (cn−1, cn−2, . . . , c0) — последний вектор, выведенный на печать перед проверкой этого условия. Следовательно,

W n =

|{

(c

n−1

, c

n−2

, . . . , c )

E n

|

j < i c = 1

}|

= 2 n−i,

i

0

j

n

∑i

W n =

2 n−i = 2n+1 − 1 = O(2 n).

=0

Поэтому T (n)

=

O(n) + O(2 n)

=

O(2 n). Таким образом, алгоритм

V Lex(n) генерации двоичных векторов линеен.

48

Учитывая биекцию f : P(A) → En, перевод алгоритма V Lex(n)

на язык подмножеств множества {a0, a1, . . . , an−1} приводит к следующему алгоритму генерации всех подмножеств (здесь дополнительно рассматривается фиктивный элемент an ̸ a{0, . . . , an−1}).

Алгоритм SLex(n) генерации подмножеств n-элементного множества {a0, . . . , an−1}

B := Ø;

while an ̸ B do begin

write(B); i := 0;

while ai B do begin

B := B \ {ai}; i := i + 1

end;

B := B {ai} end.

Пример 6. Генерация двоичных векторов bi длины n = 3 и подмножеств Bi множества A = {a0, a1, a2}, i = 1, . . . , 8.

b1 = (0, 0, 0), B1 = Ø, i = 0; b2 = (0, 0, 1), B2 = {a2}, i = 1; b3 = (0, 1, 0), B3 = {a1}, i = 0;

b4 = (0, 1, 1), B4 = {a1, a2}, i = 2; b5 = (1, 0, 0), B5 = {a0}, i = 0;

b6 = (1, 0, 1), B6 = {a0, a2}, i = 1; b7 = (1, 1, 0), B7 = {a0, a1}, i = 0; b8 = (1, 1, 1), B8 = A, i = 3.

49

2.2. Коды Грея и алгоритм их генерации

В этом разделе мы познакомимся с алгоритмом генерации всех n- разрядных двоичных векторов в порядке минимального изменения. Рассмотренные алгоритмы V Lex(n), SLex(n) порождения двоичных векторов и подмножеств не обладают этим свойством (см. пример 6), так как минимальные изменения при переходе от одного множества к другому соответствуют добавлению или удалению ровно одного элемента, а в терминах двоичных векторов это означает, что последовательные векторы должны отличаться в одном разряде. Такие наборы двоичных векторов известны как коды Грея.

Определение 9. n-разрядным кодом Грея называется упорядоченная последовательность 2 n различных двоичных n-разрядных векторов (кодовых слов), последовательные векторы которой различаются в одном разряде. Код Грея называется циклическим, если его первый и последний векторы также различаются в одном разряде.

В этих терминах задача генерации всех n-разрядных двоичных векторов в порядке минимального изменения есть задача построения n- разрядного кода Грея. Очевидно, что всякий n-разрядный код Грея определяет гамильтонов путь в n-мерном единичном кубе E n, и наоборот, всякий гамильтонов путь в E n задаёт n-разрядный код Грея. Аналогичное соответствие имеется между циклическим кодом Грея и гамильтоновым циклом. Единичный куб E n гамильтонов при n ≥ 2. Одно из построений гамильтонова цикла может быть получено индуктивно: в двух копиях E n, разбивающих куб E n+1, выбираются такие циклы и достраиваются до требуемого цикла (n + 1)-мерного куба. Эти рассуждения показывают существование различных (с точностью до циклических сдвигов) циклических кодов Грея при n ≥ 3.

Рассмотрим другой способ задания циклического кода Грея. Ввиду цикличности начальным кодовым словом считаем вектор (0, 0, . . . , 0).

50