Форум программистов, компьютерный форум, киберфорум
Free Pascal
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.73/11: Рейтинг темы: голосов - 11, средняя оценка - 4.73
-121 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 729

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

07.01.2023, 17:08. Показов 2990. Ответов 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
Сообщений: 729
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
Сообщений: 729
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
Сообщений: 729
09.01.2023, 11:50  [ТС]
Я и не знал, что в Паскале массив тоже может быть константой.
0
-121 / 12 / 4
Регистрация: 19.10.2015
Сообщений: 729
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
Сообщений: 729
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
Сообщений: 729
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
Сообщений: 729
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
Ответ Создать тему
Новые блоги и статьи
ИИ не может найти нужный язык в списке
Supersumestria 05.10.2026
Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .
Новая последняя моя музыка в SUNO
zorxor 05.10.2026
Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .
Программный домашний кинотеатр
russiannick 27.09.2026
Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого
zorxor 21.09.2026
Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .
Мобильное приложение ColorStep
pavlinmavlin 17.09.2026
Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .
Запрет дублирования строк в табличной части
Maks 13.09.2026
Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр.
Jin X 06.09.2026
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .
Программа опроса у.з. расходомера SLS-720F
Argus19 02.09.2026
Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru