Тема: Лингвистические основы совершенствования речевой деятельности учащихся (стр. 2 )

а) Перечисление перестановок

Пусть выборка содержит два элемента. Запишем их в определенном порядке, который будем рассматривать как исходный, фиксированный: а, b. Очевидно, что эти два элемента можно переставить только одним способом, поменяв их местами, – получаем два варианта перестановок: a, b; b, а. Если выборка содержит три элемента, то запишем их в исходном порядке: а, b, с.

Далее действуем так.

1шаг. Берем первый элемент (а) из исходной записи, фиксируем его на первом месте. Дописываем к нему поочередно обе перестановки из двух оставшихся элементов (b и с): а, b, с; а, с, b.

2 шаг. Берем второй элемент (b) из исходной записи, фиксируем его на первом месте. Дописываем поочередно обе перестановки
из двух оставшихся элементов (а и с): b, а, с; b, с, а.

3 шаг. Берем третий элемент (с) из исходной записи, фиксируем
его на первом месте. Дописываем поочередно обе перестановки из
двух оставшихся элементов (а и b): с, а, b; с, b, а.

Работа закончена. Мы получили все 6 возможных перестановок
из трех элементов. Обратите внимание, что последняя перестановка
(с, b, а) есть полная инверсия исходной (a, b, с).

Если выборка содержит четыре элемента, то запишем их в исходном порядке: а, b, с, d.

Формируем перестановки.

1 шаг. Берем первый элемент (а) из исходной записи, фиксируем его на первом месте. Дописываем поочередно каждую из 6 возможных перестановок из трех оставшихся элементов (b, с, d), которые формируем с помощью алгоритма, описанного выше:

abcd

abdc

acbd

aedb

adbc

adcb

2 шаг. Берем второй элемент (b) из исходной записи, фиксируем его на первом месте. Дописываем поочередно каждую из 6 возможных перестановок из трех оставшихся элементов (а, с, d)

bacd

badc

bcad

bcda

bdac

bdca

3  и 4 шаги выполняются аналогично:

cabd dabc

cadb dacb

cbad dbac

cbda dbca

cdab dcab

cdba dcba

Получаем все 24 перестановки из 4 элементов. Последняя перестановка (dcba) – инверсия исходной (abcd).

Если исходных элементов 5, то на первое место выбираем поочередно каждый из 5 элементов, дописывая к нему по 24 перестановки из 4 оставшихся элементов, получим 120 перестановок (см. табл. 4). Заметим, что последняя перестановка является инверсией исходной записи, то есть в ней все элементы записаны в обратном порядке по сравнению с исходной записью.

Теперь легко понять общее правило составления таблицы всех перестановок из п элементов. Таблица будет состоять из п столбцов, в каждом столбце (п – 1) строк.

Таблица 1

Всевозможные перестановки пяти элементов

a

b

c

d

e

b

a

c

d

e

c

a

b

d

e

d

a

b

c

e

e

a

b

c

d

a

b

c

e

d

b

a

c

e

d

c

a

b

e

d

d

a

b

e

c

e

a

b

d

c

a

b

d

c

e

b

a

d

c

e

c

a

d

b

e

d

a

c

b

e

e

a

c

b

d

a

b

d

e

c

b

a

d

e

c

c

a

d

e

b

d

a

c

e

b

e

a

c

d

b

a

b

e

c

d

b

a

e

c

d

c

a

e

b

d

d

a

e

b

c

e

a

d

b

c

a

b

e

d

c

b

a

e

d

c

c

a

e

d

b

d

a

e

c

b

e

a

d

c

b

a

c

b

d

e

b

c

a

d

e

c

b

a

d

e

d

b

a

c

e

e

b

a

c

d

a

c

b

e

d

b

c

a

e

d

c

b

a

e

d

d

b

a

e

c

e

b

a

d

c

a

c

d

b

e

b

c

d

a

e

c

b

d

a

e

d

b

c

a

e

e

b

c

a

d

a

c

d

e

b

b

c

d

e

a

c

b

d

e

a

d

b

c

e

a

e

b

c

d

a

a

c

e

b

d

b

c

e

a

d

c

b

e

a

d

d

b

e

a

c

e

b

d

a

c

a

c

e

d

b

b

c

e

d

a

c

b

e

d

a

d

b

e

c

a

e

b

d

c

a

a

d

b

c

e

b

d

a

c

e

c

d

a

b

e

d

c

a

b

e

e

c

a

b

d

a

d

b

e

c

b

d

a

e

c

c

d

a

e

b

d

c

a

e

b

e

c

a

d

b

a

d

c

b

e

b

d

c

a

e

c

d

b

a

e

d

c

b

a

e

e

c

b

a

d

a

d

c

e

b

b

d

c

e

a

c

d

b

e

a

d

c

b

e

a

e

c

b

d

a

a

d

e

b

c

b

d

e

a

c

c

d

e

a

b

d

c

e

a

b

e

c

d

a

b

a

d

e

c

b

b

d

e

c

a

c

d

e

b

a

d

c

e

b

a

e

c

d

b

a

a

e

b

c

d

b

e

a

c

d

c

e

a

b

d

d

e

a

b

c

e

d

a

b

c

a

e

b

d

c

b

e

a

d

c

c

e

a

d

b

d

e

a

c

b

e

d

a

c

b

a

e

c

b

d

b

e

c

a

d

c

e

b

a

d

d

e

b

a

c

e

d

b

a

c

a

e

c

d

b

b

e

c

d

a

c

e

b

d

a

d

e

b

c

a

e

d

b

c

a

a

e

d

b

c

b

e

d

a

c

c

e

d

a

b

d

e

c

a

b

e

d

c

a

b

a

e

d

c

b

b

e

d

c

a

c

e

d

b

a

d

e

c

b

a

e

d

c

b

a

Прежде всего, устанавливаем исходный порядок элементов.

Первым элементом во всех (n – 1)! строках первого столбца будет первый элемент из исходной записи, во втором столбце – второй и т. д.

Вторым элементом в каждом столбце записываем по порядку каждый из элементов исходной записи, кроме того, который стоит на первом месте. При этом каждый элемент пишем подряд в (п – 2) строках.

Третьим элементом в каждом столбце ставим по порядку каждый элемент исходной записи кроме двух, стоящих на первом и втором местах; каждый элемент пишем подряд в (п – 3)! cтроках.

Такое заполнение продолжаем до тех пор, пока не запишем в каждом столбце по (п – 2)! элемента из п заданных. Последние два элемента дописываем, меняя их порядок в каждых двух соседних строках. Последняя перестановка в последнем столбце будет полной инверсией исходной записи.

Применять этот алгоритм вручную при п > 5 вряд ли когда-нибудь придется. Мы описали алгоритм в общем виде только для того, чтобы лучше понять идею составления таблицы перестановок.

б) Перечисление сочетаний

Сочетания из п элементов по 2 (без повторений и с повторениями) удобнее и проще всего получать с помощью таблицы вариантов:

Таблица 2

	1	2	3	4	…	N
1	11	12	13	14	…	1n
2		22	23	24	…	2n
3			33	34	…	3n
4				44	…	4n
…						…
n						nn

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

Сочетания из п элементов по т ≥ 3 без повторений можно получать с помощью следующего алгоритма.

Пусть исходное множество содержит п различных элементов. Упорядочим их в некоторой исходной записи:

а1 а2 ... ат-1 ат ат ап-1 аn.

Алгоритм состоит из т последовательных шагов.

1 шаг. Берем первые т элементов из исходной записи, записываем их как первое сочетание. Последний в нем элемент ат заменяем последовательно на каждый следующий за ат элемент, то есть сначала на ат+1, затем на ат+2, и т. д. – до ап. Признаком окончания шага является появление на последнем месте в сочетании элемента ап. Получаем первые п – т + 1 сочетаний.

2  шаг. Последовательно изменяем значения предпоследнего в первом сочетании элемента, и для каждого значения повторяем процедуру шага 1. Сначала заменяем предпоследний элемент аm-1 на аm и приписываем к нему последовательно каждый из элементов, следующих за ат; потом ставим на предпоследнее место элемент ат+1 и последовательно приписываем к нему каждый следующий за ат +1 элемент и т. д.

Признаком окончания шага является появление на последних двух местах в сочетании пары элементов аn-1 ап (именно в таком порядке).

3 шаг. Начинаем изменять значения третьего с конца элемента в первом сочетании: вместо стоявшего там ат-2 ставим сначала ат-1, затем ат, ат+1 и т. д., и для каждого из этих значений применяем процедуру шага 2. Признаком окончания третьего шага является появление на последних трех местах в сочетании элементов ап-2 ап-1 ап (в указанном порядке).

m шаг. Это последний шаг алгоритма. Изменяем значения первого элемента в первом сочетании. Ставим на это место вместо а1 последовательно а2, а3 и т. д., и каждый раз повторяем процедуру предыдущего (т – 1)-го шага. Признаком окончания этого шага и всей работы алгоритма будет появление сочетания, состоящего из т последних элементов исходной записи в том же (исходном) порядке, то есть an-m+1 an-m+2 … an-1 an.

В результате выполнения всех шагов будут записаны все С сочетаний без повторений. Чтобы убедиться в том, что ни одно сочетание не пропущено, целесообразно сравнить их количество с С.

Продемонстрируем работу алгоритма на примерах.

Пусть дано 6 элементов (букв); составим из них сочетания по 3, по 4, по 5.

Исходная запись: abcdef (n = 6).

Записываем сочетания по 3 (т = 3).

1 шаг 2 шаг 3 шаг

аbс acd bcd

abd асе bce

abe acf bcf

abf ade bde

adf bdf

aef bef

cde

cdf

cef

def

Всего 20 сочетаний (C63 = 20).

Записываем сочетания по 4 (т = 4).

1 шаг 2 шаг 3 шаг 4 шаг

abcd abde acde bcde

abce abdf aedf bcdf

abcf abef acef bcef

adef bdef cdef

Всего 15 сочетаний (С = 15).

Записываем сочетания по 5 (т = 5).

1 шаг 2 шаг 3 шаг. 4 шаг. 5 шаг.

abede abcef abdef acdef bedef

abedf

Всего 6 сочетаний (С = 6).

Обратите внимание: ни в одном из записанных сочетаний ни одна буква не стоит раньше буквы, предшествующей ей в исходной записи, то есть а может стоять только на первом месте, b – либо на втором, либо на первом, если нет а; с – либо на третьем, либо на втором, если нет b, либо на первом, если нет а и нет b. Буква f никогда не будет стоять нигде, кроме последнего места.

в) Перечисление размещений

Размещения из п элементов по 2 (без повторений и с повторениями) получаем с помощью таблицы вариантов, заполняя ее полностью (в отличие от получения сочетаний по 2).

Все размещения из п элементов по 2 без повторений будут записаны в таблице после вычеркивания пар, стоящих на главной диагонали (всего п2 – п = п∙(п – 1) размещений). Все размещения из n элементов по 2 с повторениями записаны в полной таблице (всего n2 размещений).

Получение размещений из п элементов по т ≥ 3 без повторений – очень громоздкая процедура. При небольших пит размещения проще всего получать в два этапа: сначала составить все сочетания из п элементов по т, а затем в каждом из сочетаний сделать все возможные перестановки.

В качестве примера перечислим все размещения из 5 элементов (букв) по 3. Исходная запись: abcde.

Получаем все сочетания по т = 3: