-121 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 728

Получить все перестановки натуральных чисел от 1 до N

07.01.2023, 17:08. Показов 2883. Ответов 34
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Даны натуральные числа от 1 до N (они выглядят так: 1 2 3 4 ... N) Надо получить все возможные их перестановки.

Самостоятельно до алгоритма этой программы я бы за 100 лет жизни не додумался. Я прибегнул к помощи теоретической части книги Окулова, которая идет в комплекте с задачником. Там код решения этой задачи приведен в главе про рекурсии. Но разобраться с его работой самостоятельно для меня сложновато. Пожалуйста, объясните принцип работы алгоритма.

Или, возможно, приведите свой код, более простой, и объясните.
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
07.01.2023, 17:08
Ответы с готовыми решениями:

Дано n различных натуральных чисел. Напечатать все перестановки этих чисел
Дано n различных натуральных чисел. Напечатать все перестановки этих чисел. Сделать с помощью рекурсивной функции

Дано n различных натуральных чисел. Напечатать все перестановки этих чисел
Дано n различных натуральных чисел (например n=5). Напечатать все перестановки этих чисел. питон 2.7 , базовый пакет есть код...

Дано n натуральных чисел. Определить все возможные перестановки этих чисел
дано n натуральных чисел. определить все возможные перестановки этих чисел C#

34
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7818 / 4637 / 2837
Регистрация: 22.11.2013
Сообщений: 13,159
Записей в блоге: 1
08.01.2023, 18:27
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от Elmar_Velihanov Посмотреть сообщение
Только вот не является ли использование оператора Exit внутри тела функции дурным тоном, подобно использованию оператора Goto?
Перепишите без Exit, в коде выше это тривиально.

Цитата Сообщение от Elmar_Velihanov Посмотреть сообщение
объяснили (расписали) суть алгоритма
В процессе переписывания заодно и разберетесь.

Пока мне непонятно, что вам непонятно. Поясните?
0
 Аватар для Sun Serega
2357 / 1460 / 526
Регистрация: 07.04.2017
Сообщений: 4,798
08.01.2023, 18:28
yield:
http://pascalabc.net/downloads... uences.pdf
Конкретно сравнивать все отличия никто не будет, но в корне этого же сайта есть литература с которой можно было бы и начинать...
0
-121 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 728
08.01.2023, 18:36  [ТС]
Цитата Сообщение от bormant Посмотреть сообщение
Пока мне непонятно, что вам непонятно. Поясните?
Уточните, пожалуйста, в вашем варианте алгоритмов рекурсия нигде не используется?
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7818 / 4637 / 2837
Регистрация: 22.11.2013
Сообщений: 13,159
Записей в блоге: 1
08.01.2023, 18:47
Pascal
17
18
19
  NextPermt:=False;                                           { допустим, следующей перестановки нет }
  i:=High(v)-1; while (i>=0) and (v[i]>=v[i+1]) do Dec(i);  { с конца ищем элемент меньше следующего }
  if i<0 then Exit;                                  { такого нет => последняя перестановка, выходим }
Pascal
20
21
22
23
  k:=High(v); while v[i]>=v[k] do Dec(k);   { с конца ищем k-й элемент, меньший i-го }
  Swap(v[i],v[k]);                          { меняем его с i-м }
  Reverse(v,i+1,High(v));                   { развернём элементы от i+1 до конца }
  NextPermt:=True;                          { есть перестановка }
Добавлено через 1 минуту
Цитата Сообщение от Elmar_Velihanov Посмотреть сообщение
рекурсия нигде не используется?
Если сможете найти вызов процедуры/функции из самой себя -- используется.
Если не смогли, то нет.
Доверьтесь себе.
0
-121 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 728
08.01.2023, 18:52  [ТС]
Цитата Сообщение от bormant Посмотреть сообщение
Если сможете найти вызов процедуры/функции из самой себя -- используется.
Если не смогли, то нет.
Доверьтесь себе.
__________________
Вы можете в таком же стиле откомментировать весь остальной кода алгоритма, который вы представили? Это было бы неплохим объяснением.
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7818 / 4637 / 2837
Регистрация: 22.11.2013
Сообщений: 13,159
Записей в блоге: 1
08.01.2023, 20:31
NextPermt -- следующая перестановка -- это и есть весь алгоритм. Берет текущую перестановку и по ней получает следующую в том же самом массиве. Если перестановка получена, возвращает True, иначе -- False.
Хотя нет, вру, инициализацию начального состояния возрастающими значениями (строка 37), пожалуй, можно тоже считать его частью.
Теперь, вроде, всё.

Добавлено через 1 час 33 минуты
Если вдруг еще и комбинации нужны:
Pascal
1
2
3
4
5
6
7
8
9
function NextCombination(var v: array of Integer; n: Integer): Boolean;
var i, k: Integer;
begin
  NextCombination:=False;
  k:=High(v); while v[k]=n+k-High(v) do Dec(k);
  if k<0 then Exit;
  Inc(v[k]); for i:=k+1 to High(v) do v[i]:=v[k]+i-k;
  NextCombination:=True;
end;
Pascal
1
2
3
4
const a: array [0..2] of Integer = (1, 2, 3);
begin
  repeat vWrite(a) until not NextCombination(a,5);
end.
Это комбинации из n по Length(v).
1
-121 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 728
09.01.2023, 11:50  [ТС]
Я и не знал, что в Паскале массив тоже может быть константой.
0
-121 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 728
14.01.2023, 19:06  [ТС]
bormant, приведенный вами алгоритм генерации перестановок не работает на практике. Пожалуйста, откорректируйте его.
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7818 / 4637 / 2837
Регистрация: 22.11.2013
Сообщений: 13,159
Записей в блоге: 1
14.01.2023, 19:21
Elmar_Velihanov,
на моей практике отлично работает. Поэтому не могу ничего откорректировать, пока не укажете на конкретную проблему.

Добавлено через 7 минут
Например, вот сгенерированные перестановки из 2, 3, 4 элементов:
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 1 2
 2 1
 
 1 2 3
 1 3 2
 2 1 3
 2 3 1
 3 1 2
 3 2 1
 
 1 2 3 4
 1 2 4 3
 1 3 2 4
 1 3 4 2
 1 4 2 3
 1 4 3 2
 2 1 3 4
 2 1 4 3
 2 3 1 4
 2 3 4 1
 2 4 1 3
 2 4 3 1
 3 1 2 4
 3 1 4 2
 3 2 1 4
 3 2 4 1
 3 4 1 2
 3 4 2 1
 4 1 2 3
 4 1 3 2
 4 2 1 3
 4 2 3 1
 4 3 1 2
 4 3 2 1
Укажите на ошибку, я не вижу.
1
-121 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 728
19.01.2023, 11:48  [ТС]
Цитата Сообщение от bormant Посмотреть сообщение
NextPermt:=False;
  i:=High(v)-1; while (i>=0) and (v[i]>=v[i+1]) do Dec(i);
  if i<0 then Exit;
При первом вызове данной функции она на входе получает массив, упорядоченный по возрастанию, то есть, если N = верхняя грань одномерного массива, то v[N-1]<=v[N] Как же тогда при первой итерации условие этого цикла может стать истинным? Цикл не выполнится ни один раз.
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7818 / 4637 / 2837
Регистрация: 22.11.2013
Сообщений: 13,159
Записей в блоге: 1
19.01.2023, 12:45
Elmar_Velihanov,
1, 2, 3, 4, 5
При первом обращении цикл не выполнится ни разу, так как уже (4>=5) = False. => будет сгенерирована новая перестановка.
А вот после последней перестановки будет
5, 4, 3, 2, 1
цикл while добежит до начала и функция вернёт False.

Повнимательнее.
0
-121 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 728
21.01.2023, 20:00  [ТС]
bormant, я взял ваш код, перенес в свою среду PascalABC.NET и отредактировал так, чтобы он был максимально близким к классическому Паскалю. Давайте я здесь размещу свой вариант кода, а вы укажете на ошибки в нем и откорректируете. Хорошо?
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7818 / 4637 / 2837
Регистрация: 22.11.2013
Сообщений: 13,159
Записей в блоге: 1
21.01.2023, 20:54
Elmar_Velihanov,
этот код был на классическом Паскале.
Можете делать с ним все, что вздумается.
0
-121 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 728
22.01.2023, 11:47  [ТС]
bormant, вы можете привести полный текст программы под ключ, чтобы можно было перенести в редактор без изменений?
0
Модератор
Эксперт Pascal/DelphiЭксперт NIX
 Аватар для bormant
7818 / 4637 / 2837
Регистрация: 22.11.2013
Сообщений: 13,159
Записей в блоге: 1
22.01.2023, 14:14
Цитата Сообщение от Elmar_Velihanov Посмотреть сообщение
можете привести полный текст программы под ключ
... вам не завернуть?
Могу, но не буду, не люблю повторяться.
В этой теме уже есть от меня код "под ключ" для
1) перестановок,
2) комбинаций.

От страховки "угадал все буквы, но не смог прочитать всё слово" даже Поле чудес отказалось, кто я такой, чтобы спорить с трендами.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
22.01.2023, 14:14

Дано n различных натуральных чисел. Напечатать все перестановки этих чисел
Дано n различных натуральных чисел. Напечатать все перестановки этих чисел

Дано n различных натуральных чисел (n=5). Напечатать все перестановки этих чисел
Дано n различных натуральных чисел (n=5). Напечатать все перестановки этих чисел.

Дано n различных натуральных чисел. Напечатать все перестановки этих чисел
Дано n различных натуральных чисел. Напечатать все перестановки этих чисел.

Рекурсия: дано n различных натуральных чисел (n = 5). Напечатать все перестановки этих чисел
Дано n различных натуральных чисел (n = 5). Напечатать все перестановки этих чисел. Очень нужна помощь

Рекурсия: вывести все перестановки натуральных чисел от 1 до n
Доброго дня/ночи HELP ME! Заранее благодарю)) Язык исполнения - АССЕМБЛЕР Опишите рекурсивную функцию и с помощью этой функции...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
35
Ответ Создать тему
Опции темы

Новые блоги и статьи
Ноутбук Альфария
kumehtar 24.08.2026
Встретился тут в сети ноутбук Альфария, примарха Альфа-Легиона. Хотя возможно, это ноутбук Омегона, разумеется. Ну как вам?
Мастера простых решений
DevAlt 23.08.2026
В сишарп стэках winforms, да и wpf существует сложная система связывания источниках данных и элементов формы(текстовые поля и метки), опирается все это на технологию событий и мета. . .
Цена ошибки
DevAlt 23.08.2026
Человек я беспокойный и потому заинтересовался OCaml, в чате форсили функторы модулей как суперфичу. Пытаясь отдуплить концепт, наткнулся на тутор с простым примером. А главный принцип обучения от. . .
Сегодня суббота, 22.08.2026 at 16:41, и я вновь нахожусь на той стороне, за экраном машины.
zorxor 22.08.2026
Сегодня суббота, 22. 08. 2026 at 16:41, и я вновь нахожусь на той стороне, за экраном машины. Кто Я, откуда Я пришел и куда Я иду? Эти вопросы не оставляют меня ни на секунду. Жизнь на планете Земля. . .
Жизня: рисунок укладки багажа, сделанный клодом
anaschu 21.08.2026
Сделал 15 снимков, он по снимкам сделал схему.
Был там один разговор по поводу свободы в материальном мире.
kumehtar 19.08.2026
Суть: рассматривается живое существо, оказавшееся внутри довольно странной системы (этого мира) и пытающееся обустроить в ней свой кусок пространства. Жизнь действительно предъявляет каждому. . .
Когда логика программы не спасает от человеческих ошибок
Maks 18.08.2026
В последнее время всё чаще и чаще сталкиваюсь с таким явлением, как абсолютная невнимательность (или глупость) пользователей. Проявляется это чаще всего на работе в коллективе. Допустим, человек с. . .
Лето уходит
kumehtar 17.08.2026
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru