Алгоритм перестановок


Содержание

Алгоритм перестановок

Задача: Кто знает алгоритм полной перестановки цифр в числе ? Hапример: 123,132,213,231,312,321

Решение

1. Сначала составим список разрешенных цифр, и сколько этих цифр разрешено. Hапример, если надо создать все возможные перестановки цифр 1,3,3,7 то список будет такой:

2. Очевидно, что в первой (самой левой) позиции синтезированного числа последовательно сменятся все разрешенные цифры из списка. Поэтому для позиции 0 пустим цикл по всем разрешенным цифрам. Hо так как текущая цифра изъята для нашей позиции 0, то еенный «счетчик разрешения» уменьшаем на единицу (а после перехода от этой цифры к следующей — восстанавливаем значение счетчика для текушей цифры и уменьшаем значение счетчика для следующей).

3. Для позиции 1 справедливы все те же рассуждения, что и для позиции 0, посему напрашивается рекурсивный алгоритм следующего вида:

4. WARNING!! Я не проверял этот алгоритм, а просто «с ходу» придумал его и написал в этом письме. Поэтому не факт, что он сразу с ходу заработает. Hо я надеюсь, идея понятна, и до ума этот алгоритм довести особого труда не составит.

Оставить комментарий

Комментарии

А мне пришёл в голову такой рекурсивный алгоритм.

program Perest;
<$M 65520,0,655360>
uses crt;
var mas : array[1..10] of byte;
i,N : 1..10;

procedure recurs(num : byte);
var i,j : integer;

procedure change(var a,b : byte);
var c:byte;
begin
c:=a;
a:=b;
b:=c;
end;

begin
if num = N then
begin
for i:=1 to N do
write(mas,’ ‘);
writeln;
end else
for j:=num+1 to N do
begin
Change(mas[num+1], mas[j]);
recurs(num+1);
Change(mas[num+1], mas[j]);
end;
end;

begin
clrscr;
write(‘The quantity of array»s elements (1..10): ‘);
readln(N);

for i:=1 to N do
mas:=i;

Этот я проверил, так что он точно работает :)

А вот мне интересен нерекурсивный алгоритм, я где-то видел небольшую программку, что выводила на экран все перестановки С(n, k) (C из n по k), и которая была написана всего-лишь в 5 циклов for. Там, вроде, был перевод в другую систему счисления, для чего он нужен- не помню. Если у кого есть этот алгоритм, please, буду очень признателен.
Спасибо за внимание :)

Генерация перестановок.

30.05.2010, 19:55

Генерация n перестановок n элементного множества
Здравствуйте! Помогите пожалуйста написать программу, генерирующую n перестановок n элементного.

Генерация перестановок
Привет, я написал прогу для вывода в файл всех перестановок ряда чисел 1,2, . ,n. Число n можно.

Генерация всех перестановок элементов множества
Где можно взять алгоритм генерации всех перестановок элемента множества? Например, если M =

Рекурсивный алгоритм поиска перестановок
Реализуйте рекурсивный алгоритм поиска перестановок

Процедура печати всех перестановок из n символов — перевод с C++
Есть программа работает как мне надо, только она на С++. А переделать не получается. Может кто.

Метод генерации случайной перестановки, алгоритм Фишера-Йетса

Тасование Фишера-Йетса (названо в честь Рональда Фишера (Ronald Fisher) и Франка Йетса (Frank Yates)) — алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества. Основная процедура тасования Фишера-Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат. Время работы алгоритма [math] O(n)[/math] .

Содержание

Применение алгоритма [ править ]

Задача:
Необходимо сгенерировать случайную перестановку из [math] n [/math] чисел с равномерным распределением вероятности, если в наличии есть функция для генерации случайного числа в заданном интервале.

Решение: [ править ]

  • [math]\mathtt[/math] генерирует случайное число в отрезке [math] [1;\; i] [/math]


Следующий алгоритм решает задачу:

Обоснование [ править ]

На каждой итерации цикла мы выбираем случайный элемент из всех оставшихся, то есть у нас есть [math] n[/math] способов выбрать [math]1[/math] элемент, [math] n — 1[/math] способов выбрать [math]2[/math] элемент. [math] 1[/math] способ выбрать последний элемент. Ни на одной итерации нам не попадется ни один элемент, который уже был выбран ранее, ведь на каждом шаге выбираемые числа мы переносим в конец массива путём перестановки с последним невыбранным числом. Таким образом, последовательность длины [math] n[/math] мы можем получить [math] n \times (n — 1) \times \ldots \times 1 = n! [/math] способами, что совпадает с числом различных перестановок длины [math] n[/math] . Это означает, что вероятность выбрать любую перестановку длины [math] n[/math] равна [math] \dfrac<1>[/math] , то есть все перестановки равновероятны.

Неправильные способы реализации [ править ]

Небольшая модификация этого алгоритма, может резко сказаться на его корректности.

Пример неправильной реализации: [ править ]

В данном случае число способов сгенерировать последовательность равно [math]n^n[/math] , в то время как существует всего [math] n![/math] возможных перестановок из [math] n[/math] элементов. Поскольку [math] n^n[/math] никогда не может делиться на [math] n![/math] без остатка при [math] n \gt 2[/math] (так как [math] n![/math] делится на число [math] n — 1[/math] , которое не имеет с [math] n[/math] общих простых делителей), то некоторые перестановки должны появляться чаще, чем другие.

Другой пример неправильной реализации: [ править ]

Теперь уже число способов сгенерировать последовательность равно [math](n^2)^n[/math] . По той же причине, что и раньше [math] (n^2)^n[/math] не делится на [math] n![/math] без остатка при [math] n \gt 2[/math] , следовательно некоторые перестановки будут появляться еще чаще.

Программный алгоритм составления перестановок, размещений и сочетаний

Секция: Информатика, вычислительная техника и управление

XV Международная научно-практическая конференция «Научный форум: технические и физико-математические науки»

Программный алгоритм составления перестановок, размещений и сочетаний

The software algorithm of compiling permutations, placements and combinations

Ilvira Zibirova

Candidate of pedagogical Sciences, senior lecturer North Ossetian state University. K. L. Khetagurova, Russia, Vladikavkaz

Аннотация. В статье приведен компьютерный алгоритм авто­матического формирования перестановок, размещений и сочетаний элементов исходного набора.

Abstract. The paper presents a computer algorithm for automatic formation of permutations, placements and combinations of elements of the original set.

Ключевые слова: алгоритм; формирование размещений; формирование сочетаний; формирование перестановок.

Keywords: algorithm; the formation of placements; the formation of combinations; generation of permutations.

Формулы расчета количества перестановок, размещений и сочетаний изучаются в начальных курсах комбинаторики и теории вероятностей. Существует класс задач, которые решаются с их помощью. В большинстве случаев их решение основано на расчете лишь общего количества возможных комбинаций и не рассматривает качественных показателей отдельных комбинаций. Это связано с тем, что ручной подбор является долгим и трудоемким процессом. Например, дано 6 букв русского алфавита. Сколько слов, состоящих из 5 знаков, можно составить из этого набора? По формуле количества размещений несложно рассчитать, что всего можно составить 720 комбинаций. Но сколько из них будет слов? В данной статье приводится компью­терный алгоритм, позволяющий автоматически формировать комбинации перестановок, размещений и сочетаний элементов исходного набора.

Важно отметить, что в специализированной литературе, в частности [1], есть примеры алгоритмов подобного назначения, но наш вариант коренным образом отличается от них большей простотой, скоростью работы, надежностью и использованием рекурсии. Алгоритм представлен в виде готовой процедуры и подробно описан, что значительно облегчает его интеграцию в прикладные программы.

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

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

Рабочие формулы

1. Формула расчета количества перестановок. Перестановками называются комбинации, состоящие из одних и тех же n различных исходных элементов и отличающиеся только порядком расположения элементов [2].

Число возможных перестановок

где: n – число переставляемых элементов, n! – факториал числа n.

2. Формула расчета количества размещений. Размещениями назы­вают комбинации, составленные из n различных исходных элементов по m элементов в каждой комбинации, отличающихся либо составом элементов, либо их порядком. В дальнейшем, число элементов в каждой комбинации мы будем называть количеством позиций.

Число возможных размещений


Формула расчета количества сочетаний. Сочетаниями называют комбинации, составленные из n различных исходных элементов по m позиций, отличающиеся хотя бы одним элементом. (Порядок элементов не учитывают 12 и 21 считаются одним сочетанием).

Число возможных сочетаний

Важно отметить, что данные формулы справедливы только для выборок с неповторяющимися исходными элементами. Если элементы в выборке повторяются, то расчет проводят по другим формулам.

Выше были названы задачи, в которых необходимо найти не только количество возможных комбинаций, но и сами комбинации. Для этих целей мы разработали на языке программирования MS Visual Basic 6.0 алгоритм, который формирует комбинации перестановок, размещений и сочетаний из заданных последовательностей чисел, букв, символов или любых других объектов, отличающихся между собой по какому-либо признаку.

Описание алгоритма

Алгоритм представляет собой рекурсивную процедуру [3] (т. е. процедуру, вызывающую саму себя с изменяющимися параметрами).

Из блока программы в процедуру обязательно должны пере­даваться следующие переменные и массивы (рекомендуется сделать их глобальными, т. е. видимыми в любой части программы):

· переменная N целочисленного типа. Предназначена для хранения общего количества элементов. Она всегда больше 0;

· переменная M целочисленного типа. Предназначена для хранения количества позиций. Всегда больше 0. Если расчеты проводятся по первой формуле M = N;

· одномерный массив b строкового типа, содержащий N элементов. Перед вызовом процедуры массив заполняется значениями исходных элементов, из которых и составляются комбинации;

· одномерный массив с тоже строкового типа, содержащий N элементов. Перед вызовом процедуры все элементы массива должны иметь значение, равное Empty. Массив предназначен для формирования комбинаций из исходных значений элементов в процессе работы алгоритма;

· одномерный массив znach – строкового типа, содержащий количество элементов, равное количеству комбинаций, вычисленному по рабочей формуле. Перед вызовом процедуры все элементы массива должны иметь значение, равное Empty. Массив предназначен для хранения полученных комбинаций;

· переменная z с типом Long (длинное целое число) – счетчик массива, при вызове процедуры в первый раз, должна иметь значение, равное нулю;

· переменная proverka – логического типа. Если расчеты проводятся по первой или второй формуле, то proverka равна False. Если по третьей формуле –proverka равна True.

Текст алгоритма

Sub CalcCombin(I As Integer, u As Integer)

Dim s As String, k As Integer, j As Integer

If b(k) <> Empty Then

If proverka = True Then

Call CalcCombin(i + 1, k + 1)

Call CalcCombin(i + 1, 1)

Параметры, передаваемые в процедуру при вызове:

· переменная i целочисленного типа. При вызове процедуры из текста программы i всегда равна 1. При рекурсивном вызове перемен­ная i увеличивает своё значение на единицу;

· переменная u целочисленного типа. При вызове процедуры из текста программы u = 1. При рекурсивном вызове переменная u либо не изменяет значение (proverka = False), либо увеличивается на единицу (proverka = True).

Построчное описание алгоритма

1. Работа алгоритма начинается при первом запуске процедуры с параметрами i и u.

2. Вторым шагом является объявление локальных переменных s, k и j, которые мы будем использовать только внутри текущей процедуры. Переменная s накапливает очередную комбинацию из заданных эле­ментов массива B. Переменные k и j используются в качестве счетчиков циклов. В ходе работы процедура вновь и вновь вызывает саму себя. Это приводит к тому, что данная строка повторяется, следо­вательно, значения k и j обнуляются согласно формату оператора Dim.

3. Открываем цикл со счетчиком k, изменяющимся от u до N. Если расчет проводится по первой или второй формулам, то начальное значение переменной-счетчика k при каждом новом входе в процедуру будет изменяться от 1 до N. Цикл служит для определения номера элемента массива b, передаваемого в массив с.

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

4. Условие 1: Если k-й элемент массива b не равен Empty, т. е. еще не передан в массив c, начинаем проверять условие 2. Если же k-й элемент равен Empty, то рассматриваем следующий элемент массива b.

5. Условие 2: Если i = M, т. е. мы рассматриваем последний элемент составляемой комбинации, начинаем выводить очередную составленную комбинацию. Если рассматриваемый элемент не последний – переходим к пункту 12 и продолжаем дальше собирать комбинацию.


Если оба условия выполняются, то это означает, что очередная ком­бинация собрана и программа выполняет алгоритм вывода комбинации. В приведенном алгоритме комбинации записываются в массив znach. Этот блок реализован в строках 6–11. Если условие 2 не выполняется, то это говорит о том, что комбинация еще не составлена и система производит действия, описанные в строках 12–15.

Для того чтобы вывести комбинацию:

6. Присваиваем k-ое значение массива b i-му значению массива с. Такое решение приводит к тому, что после вывода комбинации в мас­сиве b всегда остается один элемент, значение которого не равно Empty.

7. Обнуляем текстовую переменную s, в которой будет накапли­ваться (собираться) комбинация.

8. Открываем цикл со счетчиком j, изменяющимся от 1 до M.

9. Составляем комбинацию из элементов массива c, путем после­довательного накапливания значений всех элементов массива в одной строковой переменной s.

10. Сформированные комбинации необходимо считать. Эту задачу выполняет счетчик полученных комбинаций z. С каждой итерацией, а точнее шагом рекурсии он увеличивается на единицу.

11. Значение счетчика используется для формирования текстового массива znach, в котором хранятся полученные комбинации. Счетчик служит номером очередного элемента, которому присваивается очередное значение переменной s. После этого управление выходит из конструкции IF и переходит к оператору Next k (16). Значение k увеличивается на 1. Для решения прикладных задач между строкой 11 и оператором Else можно поместить блок анализа каждой комбинации.

12. В строку 12 управление приходит в том случае, если не выполняется условие i = M (5), т. е. пока комбинация не полностью сформирована. Составление комбинации происходит следующим образом: мы передаем значение из k-ой ячейки массива b в i-ую ячейку массива с. Обнуляем b(k) и в зависимости от выбранной формулы (1, 2 или 3) вызываем процедуру CalcCombin. При вызове процедуры счетчик i увеличивается на 1 для любой формулы, а k – только для формулы (3), при работе по формулам (1) и (2) значение этого счетчика при вызове CalcCombin приравнивается к единице.

13. После передачи k-й элемент массива b становится равным Empty.

14. Для нахождения нужного элемента массива b нам нужно переменную i увеличить на единицу. Для этих целей мы используем рекурсию, она выступит в качестве цикла, счетчиком которого является переменная i.

При рекурсивном вызове процедуры, система обязательно выполняет три действия:

а) сохраняет те данные, которые ей понадобятся для продолжения работы после выхода из рекурсии;

б) проводит подготовку к вызову процедуры и передает ей управление;

в) когда вызываемая процедура завершается, система восстанав­ливает данные, сохраненные на первом шаге, и передает управление первому оператору, расположенному за вызовом процедуры CalcCombin (в нашем случае в строку 15).

15. Возвращаем значение i-ой ячейки массива с в k-ую ячейку массива b. Мы воспользовались элементом – вывели комбинацию, а теперь возвращаем элемент на прежнее место.

16. Проверяем значение переменной-счетчика k. Если k = N, то переходим к строке 17, иначе – к строке 3, увеличив значение k на единицу.

17. Точка выхода из процедуры.

Пример использования алгоритма

С помощью описанного алгоритма были получены следующие комбинации перестановок чисел “2”, “4”, “6”, “8” (4!=24):

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

АЛГОРИТМЫ КОМБИНАТОРИКИ

(лекции 2001 фрагменты)

ТЕМА 2. ГЕНЕРАЦИЯ ПЕРЕСТАНОВОК

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

При решении некоторых задач возникает необходимость генерирования перестановок n-го порядка. Чаще всего генерирование перестановок связано с задачами перебора, в которых решение данной представляет собой некоторую перестановку, обладающую конкретным заданным свойством. Для поиска искомой перестановки мы перебираем все возможные перестановки и проверяем для каждой из них выполнение этого конкретного свойства. Последовательное генерирование перестановок определяет на множестве всех перестановок некоторый порядок, а именно: пусть f и g перестановки, тогда f , g= , будем говорить, что f 7. 13. 19. 2. 8. 14. 20. 3. 9. 15. 21. 4. 10. 16. 22. 5. 11. 17. 23. 6. 12. 18. 24.

Лексикографический порядок может быть интерпретирован так. Пусть каждая перестановка интерпретируется как целое число, записанное в n-ричной позиционной системе (с цифрами ‘0’«’1’. ’n-1’«’n’). Тогда генерация их в лексикографическом порядке — это перечисление в порядке возрастания чисел, состоящих из n разных цифр.

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

Л1) В первой перестановке элементы располагаются в возрастающей последовательности, в последней — в убывающей (докажите это свойство для произвольного n).

Л2) Последовательность всех перестановок можно разбить на n блоков длины (n-1)!, соответствующих возрастающим значениям элемента в первой позиции. Остальные n-1 позиций блока, содержащего элемент p в первой позиции, определяют последовательность перестановок множества <1. n>/ <р>в лексикографическом порядке.

Это свойство легко иллюстрируется приведенным примером генерации перестановок 4-порядка. Нетрудно видеть, что все перестановки 4-порядка разбиты на четыре столбца, при этом у перестановок первого столбца на 1-ой позиции расположен элемент 1, у второго — элемент 2 и так далее. Кроме того, в каждом столбце элементы, расположенные в перестановках со 2-ой по 4-ую позиции, образуют перестановки этих элементов в лексикографическом порядке. Для первого столбца перестановки элементов 2,3,4; для второго — 1,3,4; третьего — 1,2,4; для четвертого 1,2,3. Отметим также, что в каждом столбце элементы, расположенные со 2-ой по 4-ую позиции в первой перестановке, образуют возрастающую последовательность, а в последней перестановке эти же элементы расположены в убывающей последовательности (свойство Л1 лексикографического порядка).


Таким образом, если мы рассмотрим перестановки каждого столбца, то для элементов, расположенных со 2-ой по 4-у позиции, полностью выполняются свойства Л1 и Л2. Это замечание приводит к следующему обобщению свойства Л2 для перестановок произвольного порядка:

Л3) Последовательность всех перестановок можно разбить на n*(n-1)*. *(n-k+1) блоков выбором значений р1. pk элементов, расположенных на первых k позициях. При этом блок p1. pk предшествует блоку q1. qk, если р1. pk меньше q1. qk в лексикографическом порядке. Кроме того, для перестановок каждого такого обобщенного блока элементы, расположенные с k+1-ой по n-ую позиции, представляют собой генерацию перестановок этих элементов в лексикографическом порядке.

Теперь мы готовы сформулировать самое важное свойство лексикографического порядка, на основе которого легко преобразовать текущую перестановку в следующую. Это свойство можно записать так:

Л4) Любая текущая перестановка является заключительной для некоторого обобщенного блока. Этот блок определяется элементами текущей перестановки, расположенными на позициях в конце перестановки и представляющими собой максимально возможную убывающую последовательность значений элементов перестановки. Справедливость последнего замечания следует из свойства Л1 лексикографического порядка.

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

Примеры. Рассмотрим приведенную выше генерацию перестановок 4-го порядка, тогда:

Перестановка является заключительной для блока, состоящего из перестановок 7. и 8. , элементы 4,3 образуют ее хвост;

Перестановка является заключительной для блока, состоящего из одной перестановки 13. , ее хвост состоит из одного элемента — 4;

Перестановка является заключительной для второго столбца приведенной генерации, ее хвост — 4,3,1;

Перестановка является заключительной для всей генерации перестановок 4-го порядка, ее хвост совпадает со всей перестановкой.

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

1. Выделяем хвост текущей перестановки;

2. Если он не совпадает со всей перестановкой, то ищем в хвосте первый с конца перестановки элемент, больший элемента перестановки, расположенного непосредственно перед ее хвостом (если перестановка совпадает со своим хвостом, то она является заключительной во всей генерации);

3. Меняем местами элемент, найденный в предыдущем пункте, с элементом, расположенным непосредственно перед хвостом перестановки;

4. Располагаем все элементы, преобразованного в пункте 3 хвоста перестановки, в обратном порядке (инвертирование преобразованного хвоста перестановки).

Примеры. Перестановка преобразуется по вышеприведенному алгоритму в перестановку , а перестановка в . Рассмотрим перестановку 15-порядка , она преобразуется в перестановку .

Упражнение. В какие перестановки преобразуются следующие перестановки: а) n=3, ; б) n=5, ;

Замечание 1. Можно провести формальное доказательство того факта, что преобразованная по данному алгоритму перестановка действительно совпадает со следующей после текущей перестановки в лексикографическом порядке. Однако мы такое доказательство опустим.

Замечание 2. Приведенный выше алгоритм преобразования текущей перестановки в следующую формально можно записать так:

Пусть p= ,где

(если p= , то k=0),

j>k и pj>pk и для q:j 0 do

Begin

for k:=1 to n do write(p[k]); writeln;

j:=n; m:= k+1;

begin r:=p[j]; p[j]:=p[m]; p[m]:=r; j:=j-1; m:=m+1 end

End

End.

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

Упражнение. Протестируйте приведенную выше программу при n=3.

Оценим временную вычислительную сложность приведенной программы. Обычно временная вычислительная сложность программ, представленных на языке высокого уровня, оценивается как порядок роста числа исполняемых операторов программы в зависимости от некоторого параметра исходных данных [3]. Однако, в алгоритмах генерации перестановок такой подход малоэффективен, так как в процессе работы любого алгоритма генерации всех перестановок порождается n!перестановок, т. е. временная вычислительная сложность всегда будет, по крайней мере, O(n!) — величина слишком быстро растущая. Любая ‘экономия’ в реализации будет сказываться только на коэффициенте пропорциональности при n!. Поэтому для того, чтобы удобнее было сравнивать различные алгоритмы генерации перестановок, обычно вводят другие критерии оценки вычислительной сложности. Здесь разумно ввести два критерия — количество транспозиций элементов перестановки, выполняемых в среднем при генерации одной перестановки, и аналогичное среднее числа сравнений элементов перестановки в операторах <поиск k>и <поиск j>.


Оценим их число. Пусть Tk — число транспозиций, выполняемых при вызове оператора LEC(n-k+1), т. е. Tk –число транспозиций, которые необходимо выполнить при генерации перестановок k-го порядка. Имеем

k*Tk-1+(k-1)*ë(k+1)/2û,где ëaû = ‘целой части числа a.

Первое слагаемое определяет число транспозиций при вызовах оператора LEC(n-k), а второе — число транспозиций, выполняемых в операторах <3>и <4>. Заметим, что T1=0.

Для решения этого рекуррентного уравнения сделаем замену переменной. Пусть Sk=Tk+ë(k+1)/2û, тогда

где dk=0, если k нечетно, и dk=1, если k четно.

Решение этого рекуррентного соотношения легко получается по индукции:

Tk= — ë(k+1)/2û.

Учитывая, что »ch(1)»1.543 и ë(k+1)/2û=o(k!). получаем

т. е. на генерирование одной перестановки в лексикографическом порядке требуется в среднем ch(1)»1.543 транспозиций.

Перейдем теперь к оценке числа сравнений элементов перестановки в операторах и ; обозначим это число Сn.

Определим Сn как функцию от Сn-1. Отметим, что при генерации каждого из n блоков, определенных в Л2, требуется Cn-1 сравнений, а таких блоков n. Далее, при переходе от одного блока к другому оператор <поиск k>выполняется n-1 раз, а оператор <поиск J>при переходе от блока p к блоку p+1 (1£p k then

Алгоритм построения таблицы перестановок методом последовательных приращений Текст научной статьи по специальности « Математика»

Аннотация научной статьи по математике, автор научной работы — Пегова Елена Петровна

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

Похожие темы научных работ по математике , автор научной работы — Пегова Елена Петровна,

THE BUILDING ALGORITHM OF THE TABLE OF THE TRANSPOSITIONS BY THE CONSEQUENT INCREMENTATIONS METHOD

Algorithm of the building of the table of the transpositions is оffered without repetitions from N element in the manner of numeric row.

Текст научной работы на тему «Алгоритм построения таблицы перестановок методом последовательных приращений»

НАУЧНЫЙ ВЕСТНИК МГТУ ГА

АЛГОРИТМ ПОСТРОЕНИЯ ТАБЛИЦЫ ПЕРЕСТАНОВОК МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ ПРИРАЩЕНИЙ

Статья представлена доктором физико-математических наук, профессором Козловым А.И.

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

Ключевые слова: перестановки, алгоритм.

Перестановкой порядка N называется расположение N различных объектов в ряд в некотором порядке. Например, для трех объектов а, b и с существует шесть перестановок: abc, acb, bac, Ьса, cab, cba. Д ля множества из N элементов можно построить N! различных перестановок.

Необходимость построения таблицы перестановок возникает при решении задач, требующих перебора: задачи составления расписаний; задачи нахождения оптимального маршрута (задача коммивояжера); решение логических задач; решение ряда задач оптимизации; задачи шифрования.

Для составления таблицы перестановок из n элементов есть много алгоритмов (первым, вероятно, был Пандит Нарайана, Индия, XIV в.): построение перестановки по таблице инверсий [1] методом лесенки с беспорядками [3], алгоритм Дейкстры — алгоритм на графах, который находит кратчайшее расстояние от одной из вершин графа до всех остальных [4], методы Кнута [2].

Эти методы основаны на манипуляции с цифрами как с символами, входящими в определенное множество, и не представляют таблицу перестановок как упорядоченный ряд чисел.

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

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

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

Ко второму уровню отнесем все нечетные члены ряда, находящиеся внутри третьего уровня. Приращения каждого последующего члена во втором уровне равно числам 90 и 99, умноженным на некоторый множитель.


Структура построения перестановок из трех элементов

№ пп Перестановки Разности Множитель

2 132 132-123=9 1 (3-2=1)

3 213 213-123=90 1 (2-1=1)

4 231 231-21[3=9*2 2 (3-1=2)

5 312 312-203=99 1 (1-2 i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

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

Соответственно числа третьего уровня имеют приращения 900, 990 и 999, помноженные на число множителя. В следующих таблицах приведены схемы расчета перестановок для п=3 (табл. 1) и п=4 (табл. 2).

Количество уровней в таблице равно (п-1). Следовательно, в табл. 1 количество уровней 2, а в табл. 2 количество уровней 3. Минимальное, первое число относится к высшему уровню.

Структура построения перестановок из четырех элементов

Перестановки Разности Множитель Перестановки Разности Множитель

1 ур. 2 ур. 3 ур. 1 ур. 2 ур. 3 ур.

1 1234 13 3124 3124-2134=990 1 (1-2 i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

9 2314 2314-21 34=90*2 2 (3-1=2) 21 4213 4213-41 23=90 1 (2-1=1)

10 2341 2341-231(4=9*3 3 (4-1=3) 22 4231 4231-421|3=9*2 2 (3-1=2)

11 2413 2413-2304=99 1 (1-3 1, след. =1

12 2431 2431-2413=9*2 2 (3-1=2) 24 4321 4321-4312=9 1 (2-1=1)

В строке 17 табл. 2 множитель равен 2, потому что число 3214 находится на втором уровне, разность 1-2 отрицательная, и слева от единицы расположены две цифры, последовательно большие, чем 1.

Задача усложняется, если количество перебираемых чисел n больше 9. В этом случае вычисления нужно выполнять в системе счисления, большей, чем n.

Нетрудно заметить, что ряд множителей один и тот же для всех перестановок:

1, 1, 2, 1, 1, 1, 1, 2, 3, 1, 2, 1 , 2, 1, 3 , 2, 1, 1, 1, 1, 2, 1, 1.

Максимальный множитель таблицы перестановок из n равен n-1.

Предложенный алгоритм построения таблицы перестановок имеет по сравнению с существующими следующие преимущества: 1) представляет таблицу как возрастающий ряд чисел, в котором каждый последующий член вычисляется из предыдущего (в своем уровне) путем прибавления некоторого значения, вычисляемого по определенным правилам; 2) позволяет составлять перестановки из количества элементов, большего 10; 3) достаточно прост с точки зрения написания компьютерной программы.

1. Стенли Р. Перечислительная комбинаторика. — М.: Мир, 1990.

2. Дональд Э. Кнут. Искусство программирования. Т. 1. Основные алгоритмы. — М.: Вильямс, 2010.

3. Мельников C. Delphi и Turbo Pascal на занимательных примерах. — СПб.: БХВ-Петербург, 2006.

4. Дейкстра Э. Дисциплина программирования. — М.: Мир, 1978.

Алгоритм построения таблицы перестановок методом последовательных приращений

THE BUILDING ALGORITHM OF THE TABLE OF THE TRANSPOSITIONS BY THE CONSEQUENT INCREMENTATIONS METHOD

Algorithm of the building of the table of the transpositions is offered without repetitions from N element in the manner of numeric row.

Keywords: transpositions, algorithm.


Сведения об авторе

Пегова Елена Петровна, окончила МАИ (1979), старший преподаватель, заведующая лабораторией компьютерной графики МГТУ ГА, автор 2 научных работ, область научных интересов -программирование, компьютерное моделирование, инженерная графика.

Алгоритм перестановок

[Все темы по перестановкам]

Теория:
1) Липский. Комбинаторика для программистов. 1988
2) Меньшиков. Олимпиадные задачи по программированию. 2006.

Рассмотрим две задачи:
1) Рекурсивный способ генерации всех перестановок в лексикографическом порядке.
2) Рекурсивный способ генерации всех перестановок в антилексикографическом порядке.

Для начала разберемся, что такое лексико- и антилексико-графические порядки.
Начальная перестановка: <1, 2, 3>

Лексикографический

Антилексикографический

1 2 3 1 2 3
1 1 3 2 2 1 3
2 2 1 3 1 3 2
3 2 3 1 3 1 2
4 3 1 2 2 3 1
5 3 2 1 3 2 1

Напомним, что лексикографический порядок – это порядок слов, который используется в словарях.
Слово A меньше слова B, если первые i символов слов равны, а символ A[i+1] Антилексикографический порядок отличается от лексикографического только тем, что сравнение символов идет справа налево.
Слово A меньше слова B, если последние i символов равны, а символ A[i-1] Практика:
Решим задачу 2B-Перестановки из задачника Федора Меньшикова двумя рассматриваемыми способами.
Как можно было заметить, оба порядка начинаются с минимальной перестановки <1, 2, 3>и заканчивается максимальной <3, 2, 1>.

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

  1. int n;
  2. vector int > p;
  3. vector bool > used;
  4. string str;
  5. .
  6. void lex( int pos)
  7. <
  8. if (pos == n) <
  9. for ( int i=0;i return ;
  10. >
  11. for ( int i=0;i if (!used[i]) <
  12. used[i] = true ;
  13. p[pos] = i;
  14. lex(pos+1);
  15. p[pos] = 0; // debug only
  16. used[i] = false ;
  17. >
  18. >
  19. >

* This source code was highlighted with Source Code Highlighter .

Рекурсивная функция lex(n) генерируется все перестановки из алфавита <0,1. n-1>длиной n и хранит текущую перестановку в массиве p. Если номер текущей позиции pos == n, тогда сгенерирована следующая перестановка.
[Решение]

2) Генерация всех перестановок в антилексикографическом порядке
Решение полностью идентично, за исключением того, что перестановка формируется с конца
[Решение]

Алгоритм перестановок

Извините,писать негде было.Нужно,чтобы программа,написанная на си++,выводила на экран все перестановки от 1 до n,причем только такие перестановки,которые начинаются с 1.

3 ответа 3

Видимо под найти подразумевается «распечатать»? Ну тогда у меня для Вас плохие новости. Для 15 элементных перестановок их кол-во будет равно 1307674368000 — даже если по одному байту на перестановку (чего явно не хватит), то это уже больше терабайта. А если это на печать выводить, то это будет по 16 байт на перестановку (15 символов + перевод строки).

Я потестил у себя скорость вывода на терминал — получилось порядка 450000 символов в секунду (хотя некоторые источники утверждают, что она порядка 33к символов в секунду. Я просто сделал time cat файл и посмотрел, сколько выводит). Из этого получается

15! * 16 / 447121 / 60/60/24 = 541 день = почти 2 года.

Вывод, никакой алгоритм тут не поможет.

Если в Вашей задаче написано «посчитать кол-во перестановок, которые удоволетворяют определенному условию, то тут нужно обычно придумывать специальный алгоритм». Этим любят увлекаться разные олимпиадные задачи (сам решал, знаю).

Алгоритм построения таблицы перестановок методом последовательных приращений Текст научной статьи по специальности « Математика»

Аннотация научной статьи по математике, автор научной работы — Пегова Елена Петровна

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

Похожие темы научных работ по математике , автор научной работы — Пегова Елена Петровна,

THE BUILDING ALGORITHM OF THE TABLE OF THE TRANSPOSITIONS BY THE CONSEQUENT INCREMENTATIONS METHOD

Algorithm of the building of the table of the transpositions is оffered without repetitions from N element in the manner of numeric row.

Текст научной работы на тему «Алгоритм построения таблицы перестановок методом последовательных приращений»


НАУЧНЫЙ ВЕСТНИК МГТУ ГА

АЛГОРИТМ ПОСТРОЕНИЯ ТАБЛИЦЫ ПЕРЕСТАНОВОК МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ ПРИРАЩЕНИЙ

Статья представлена доктором физико-математических наук, профессором Козловым А.И.

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

Ключевые слова: перестановки, алгоритм.

Перестановкой порядка N называется расположение N различных объектов в ряд в некотором порядке. Например, для трех объектов а, b и с существует шесть перестановок: abc, acb, bac, Ьса, cab, cba. Д ля множества из N элементов можно построить N! различных перестановок.

Необходимость построения таблицы перестановок возникает при решении задач, требующих перебора: задачи составления расписаний; задачи нахождения оптимального маршрута (задача коммивояжера); решение логических задач; решение ряда задач оптимизации; задачи шифрования.

Для составления таблицы перестановок из n элементов есть много алгоритмов (первым, вероятно, был Пандит Нарайана, Индия, XIV в.): построение перестановки по таблице инверсий [1] методом лесенки с беспорядками [3], алгоритм Дейкстры — алгоритм на графах, который находит кратчайшее расстояние от одной из вершин графа до всех остальных [4], методы Кнута [2].

Эти методы основаны на манипуляции с цифрами как с символами, входящими в определенное множество, и не представляют таблицу перестановок как упорядоченный ряд чисел.

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

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

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

Ко второму уровню отнесем все нечетные члены ряда, находящиеся внутри третьего уровня. Приращения каждого последующего члена во втором уровне равно числам 90 и 99, умноженным на некоторый множитель.

Структура построения перестановок из трех элементов

№ пп Перестановки Разности Множитель

2 132 132-123=9 1 (3-2=1)

3 213 213-123=90 1 (2-1=1)

4 231 231-21[3=9*2 2 (3-1=2)

5 312 312-203=99 1 (1-2 i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

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

Соответственно числа третьего уровня имеют приращения 900, 990 и 999, помноженные на число множителя. В следующих таблицах приведены схемы расчета перестановок для п=3 (табл. 1) и п=4 (табл. 2).

Количество уровней в таблице равно (п-1). Следовательно, в табл. 1 количество уровней 2, а в табл. 2 количество уровней 3. Минимальное, первое число относится к высшему уровню.

Структура построения перестановок из четырех элементов

Перестановки Разности Множитель Перестановки Разности Множитель

1 ур. 2 ур. 3 ур. 1 ур. 2 ур. 3 ур.

1 1234 13 3124 3124-2134=990 1 (1-2 i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

9 2314 2314-21 34=90*2 2 (3-1=2) 21 4213 4213-41 23=90 1 (2-1=1)

10 2341 2341-231(4=9*3 3 (4-1=3) 22 4231 4231-421|3=9*2 2 (3-1=2)

11 2413 2413-2304=99 1 (1-3 1, след. =1

12 2431 2431-2413=9*2 2 (3-1=2) 24 4321 4321-4312=9 1 (2-1=1)

В строке 17 табл. 2 множитель равен 2, потому что число 3214 находится на втором уровне, разность 1-2 отрицательная, и слева от единицы расположены две цифры, последовательно большие, чем 1.


Задача усложняется, если количество перебираемых чисел n больше 9. В этом случае вычисления нужно выполнять в системе счисления, большей, чем n.

Нетрудно заметить, что ряд множителей один и тот же для всех перестановок:

1, 1, 2, 1, 1, 1, 1, 2, 3, 1, 2, 1 , 2, 1, 3 , 2, 1, 1, 1, 1, 2, 1, 1.

Максимальный множитель таблицы перестановок из n равен n-1.

Предложенный алгоритм построения таблицы перестановок имеет по сравнению с существующими следующие преимущества: 1) представляет таблицу как возрастающий ряд чисел, в котором каждый последующий член вычисляется из предыдущего (в своем уровне) путем прибавления некоторого значения, вычисляемого по определенным правилам; 2) позволяет составлять перестановки из количества элементов, большего 10; 3) достаточно прост с точки зрения написания компьютерной программы.

1. Стенли Р. Перечислительная комбинаторика. — М.: Мир, 1990.

2. Дональд Э. Кнут. Искусство программирования. Т. 1. Основные алгоритмы. — М.: Вильямс, 2010.

3. Мельников C. Delphi и Turbo Pascal на занимательных примерах. — СПб.: БХВ-Петербург, 2006.

4. Дейкстра Э. Дисциплина программирования. — М.: Мир, 1978.

Алгоритм построения таблицы перестановок методом последовательных приращений

THE BUILDING ALGORITHM OF THE TABLE OF THE TRANSPOSITIONS BY THE CONSEQUENT INCREMENTATIONS METHOD

Algorithm of the building of the table of the transpositions is offered without repetitions from N element in the manner of numeric row.

Keywords: transpositions, algorithm.

Сведения об авторе

Пегова Елена Петровна, окончила МАИ (1979), старший преподаватель, заведующая лабораторией компьютерной графики МГТУ ГА, автор 2 научных работ, область научных интересов -программирование, компьютерное моделирование, инженерная графика.

Алгоритм перестановок

Прямое применение алгоритма поиска с возвращением к перестановкам порождает их в лексикографическом порядке, т.е. получаемая последовательность для имеет вид (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1). Их также можно порождать следующим алгоритмом.

Начинаем с перестановки , а переход от текущей перестановки к перестановке, следующей за текущей в смысле лексикографического порядка, осуществляем последовательным выполнением следующих действий:

1) просмотр справа налево в поисках самой правой позиции , в которой (если такой позиции нет, то текущая перестановка является последней и следует закончить порождение);

2) просмотр от слева направо в поисках наименьшего из таких элементов , что и ;

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

Например, для и после выполнения первых двух шагов имеем и , а результат транспозиции и и обращения отрезка переводит в (2,6,7,1,3,4,5,8).

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

Важность лексикографического порядка определяется его простотой и естественностью. Существенным недостатком его следует признать сравнительно большой объем той работы, которую необходимо выполнить для преобразования текущего объекта в объект, являющийся следующим в смысле лексикографического упорядочения. Например, при соседними являются перестановки (2,3,1) и (3,1,2), различающиеся во всех позициях. При порождении комбинаторных объектов (в частности, перестановок) стремятся использовать такое их упорядочение, при котором следующий объект строится по предыдущему наиболее просто. Для многих классов комбинаторных объектов удается найти так называемый порядок минимального изменения, минимизирующий объемы работы по переходу от текущего элемента к соседнему и, таким образом, приводящий к наилучшим временным характеристикам алгоритма порождения комбинаторных объектов данного класса.

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

Можно дать простое рекурсивное описание для процесса построения перестановок в таком порядке. Для единственная перестановка (1) удовлетворяет нашим требованиям. Если 1$» BORDER=0 height=33 w >, то из последовательности перестановок для множества строится последовательность перестановок для элементов за счет расширения каждой из перестановок вставкой элемента на каждое из возможных мест («промежутков» между элементами ), справа налево при нечетном или слева направо при четном .

Однако с точки зрения объема памяти, необходимого для выполнения описанного процесса, порождать всю последовательность целиком нецелесообразно. В этом смысле более предпочтительным оказывается итеративное порождение элементов той последовательности, когда каждая следующая перестановка получается из предыдущей с использованием дополнительно хранимой и небольшой по объему вспомогательной информации. В приведенном ниже алгоритме, который порождает перестановки в порядке минимального изменения, такой вспомогательной информацией служит перестановка обратная к текущей (т.е. такая, что для всех ), а также «вектор направлений» , в каждом элементе которого хранится направление сдвига числа .

while # 1 do
Вывести текущее значение ; ;
while m$ m$» BORDER=0 height=33 w >do end;
Осуществить транспозицию элементов и в ;
Осуществить транспозицию элементов и в Q
end.

При этом -1 означает сдвиг влево, +1 — вправо и 0 — отсутствие сдвига. В этом алгоритме каждая следующая перестановка получается из предыдущей за счет перемещения одного единственного элемента . Этот элемент сдвигается до тех пор, пока не достигнет границы или элемента, большего, чем он сам. В этом случае его сдвиг прекращается, направление сдвига меняется на противоположное, в дальнейшем сдвигается следующий меньший его элемент, который можно сдвинуть.

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

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

Илон Маск рекомендует:  Watcom cc faq
Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL