Теоретические сведения

Приведём эффективные алгоритмы, генерирующие основные комбинаторные объекты.

1. Размещения с повторениями.

Данный алгоритм генерирует наиболее общий класс размещений с повторениями, когда i-ый элемент размещения выбирается из своего множества X_i . Генерация выполняется в лексикографическом порядке.

Используемые обозначения:

A – массив, содержащий размещение;

x – массив, содержащий минимальные значения элементов размещения;

y – массив, содержащий максимальные значения элементов размещения;

k – количество элементов в размещении.

{ i := k ; for ( j = ) A_j := x_j ;

while ( i ³ 1 )

{вывод массива A;

i := k ;

while ( A_i = y_i ) i := i -1;

if ( i ³1) {A_i := A_i +1;

for (j = ) A_j := x_j ;

}

}

}

2. Перестановки без повторений.

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

Используемые обозначения:

P – массив, содержащий перестановку;

n – количество элементов в перестановке;

« – поменять местами переменные.

reverse ( m )

{ i :=1; j := m ;

while ( i <j ) {P_i «P_j ;

i :=i +1; j :=j -1;

}

}

Antilex ( m )

{ if( m =1) вывод массива P ;

else for (i = )

{ Antilex ( m -1);

if (i < m )

{ P_i «P_m ;

reverse ( m -1);

}

}

}

{ for (i = ) P_i := i ;

Antilex ( n );

}

3. Сочетания без повторений.

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

Используемые обозначения:

С – массив, содержащий сочетание;

k – количество элементов в сочетании;

n – количество элементов в исходном множестве.

{ for (i = ) C_i := i ;

p :=k ;

while ( p ³1)

{вывод массива C;

if ( C_k = n ) p := p -1;

else p :=k ;

if ( p ³1) for (i = )

C_i := C_p + i – p +1;

}

}

4. Размещения без повторений.

При генерации размещений без повторений используется комбинация двух алгоритмов: генерация сочетаний без повторений и перестановок без повторений. Для этого в алгоритме генерации сочетаний без повторений вместо печати сгенерированной комбинации выполняется генерация всех её перестановок (так как размещения отличаются от сочетаний тем, что в них учитывается порядок выбранных элементов). При реализации этого алгоритма сначала в массиве С генерируется сочетание, затем, вместо вывода массива С, его элементы копируются в массив P и вызывается рекурсивная процедура генерации перестановок.