Напечатать все перестановки чисел

@kkk008009kkk · Регистрация: 24.03.2011

Студворк — интернет-сервис помощи студентам

Добрый день. Имеется задача:

Напечатать все перестановки чисел 1..n так, чтобы каждая следующая получалась из предыдущей перестановкой (транспозицией) двух соседних чисел. Например, при n=3 допустим такой порядок: 3.2 1 -> 2 3.1 -> 2.1 3 -> 1 2.3 -> 1.3 2 -> 3 1 2

Пытался решить, внизу представлен вариант, который работает только для чисел 2 и 3.

Pascal
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
var
x:array [1..100] of integer;
a,s,d,f,n,i,j,k:integer;
rt:integer;
begin
writeln('введите n');
readln(n);
for i:=1 to n do
x[i]:=n-i+1;
 
k:=1;
repeat
rt:=0;
a:=x[k];
x[k]:=x[k+1];
x[k+1]:=a;
 
for  j:=1 to n do
write(x[j], ' ');
writeln;
inc(k);
if k=n then k:=1;
for i:=1 to n do
if x[i]=n-i+1 then rt:=rt+1
until rt=n;
 
 
end.

Была мысль использовать такой алгоритм перебора:

4321
4312
4132
4123
4213
4231
2431
2413
2143
2134
2314
2341
3241
3214
3124
3142
3412
3421
4321

Но, как видно, 1 никогда не встает в начало последовательности.

Подскажите, пожалуйста, с алгоритмом.

@sheldon-yura · 12.05.2012, 21:52

попробуй этот вариант:

Pascal
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
Program Lr15_1;
{Генерация всех перестановок в антилексикографическом режиме}
uses
 Crt;
var
 P:array[1..100] of integer;
 i,n:integer;
 fout:text;
procedure Reverse(m:integer);
{Обращение последовательности}
var
 k,i,j:integer;
begin
 i:=1;
 j:=m;
 while i<j do
 begin
  k:=P[i];
  P[i]:=P[j];
  P[j]:=k;
  inc(i);
  dec(j);
 end;
end;
 
procedure Antilex(m:integer);
{Массив Р - глобальный}
var
 l,i:integer;
begin
 if m=1 then {Нерекурсивная ветвь}
 begin
  for i:=1 to n do
   Write(fout,P[i]:4);
  Writeln(fout);
 end
 else {Рекурсивная ветвь}
  for i:=1 to m do
  begin
   Antilex(m-1);
   if i<m then
   begin
    l:=P[i];
    P[i]:=P[m];
    P[m]:=l;
    Reverse(m-1);
   end;
  end;
end;
{Головная программа}
begin
 assign(fout,'lr15_1.txt');
 rewrite(fout);
 clrscr;
 Write('Введите N=');
 Readln(n);
 writeln(fout,'Все перестановки из ',n,' в антилексико-графическом порядке');
 for i:=1 to n do
  P[i]:=i;
 Antilex(n);
 close(fout);
end.

Добавлено через 26 секунд
или этот:

Pascal
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
program Lr15_2;
{Генерирование всех перестановок за минимальное число транспозиций}
uses
 Crt;
var
 P:array[1..100] of integer;
 i,n:integer;
 fout:text;
 
function B(m,i:integer):integer;
{Определяет номер элемента, участвующего в транспозиции}
begin
 if ((m mod 2)=0) and (m>2) then
  if i<m-1 then
   B:=i
  else
   B:=m-2
 else
  B:=m-1;
end;
 
procedure Perm(m:integer);
{Основная процедура генерирования и вывода очередной перестановки}
var
 k,k1,i:integer;
begin
 if m=1 then {Нерекурсивная ветвь}
 begin
  for i:=1 to n do
   Write(fout,P[i]:4);
   Writeln(fout);
  end
 else {Рекурсивная ветвь}
  for i:=1 to m do
  begin
   Perm(m-1);
   if i<m then
   begin
    k1:=b(m,i);
    k:=P[k1];
    P[k1]:=P[m];
    P[m]:=k;
   end;
  end;
end;
{Головная программа}
begin
 assign(fout,'lr15_2.txt');
 rewrite(fout);
 clrscr;
 Write('Введите количество чисел N= ');
 Readln(n);
 writeln(fout,'Все перестановки из ',n,' за минимальное число транспозиций');
 for i:=1 to n do
  P[i]:=i;
 Perm(n);
 close(fout);
end.

@kkk008009kkk · 13.05.2012, 02:42 **[ТС]**

Не работает. Ни тот, ни этот.

@Michael_Atak · 13.05.2012, 04:43

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

Добавлено через 2 минуты

Pascal
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
program Lr15_2;
{Ãåíåðèðîâàíèå âñåõ ïåðåñòàíîâîê çà ìèíèìàëüíîå ÷èñëî òðàíñïîçèöèé}
uses
 Crt;
var
 P:array[1..100] of integer;
 i,n:integer;
 fout:text;
 
function B(m,i:integer):integer;
{Îïðåäåëÿåò íîìåð ýëåìåíòà, ó÷àñòâóþùåãî â òðàíñïîçèöèè}
begin
 if ((m mod 2)=0) and (m>2) then
  if i<m-1 then
   B:=i
  else
   B:=m-2
 else
  B:=m-1;
end;
 
procedure Perm(m:integer);
{Îñíîâíàÿ ïðîöåäóðà ãåíåðèðîâàíèÿ è âûâîäà î÷åðåäíîé ïåðåñòàíîâêè}
var
 k,k1,i:integer;
begin
 if m=1 then {Íåðåêóðñèâíàÿ âåòâü}
 begin
  for i:=1 to n do
   Write(P[i]:4);
   Writeln;
  end
 else {Ðåêóðñèâíàÿ âåòâü}
  for i:=1 to m do
  begin
   Perm(m-1);
   if i<m then
   begin
    k1:=b(m,i);
    k:=P[k1];
    P[k1]:=P[m];
    P[m]:=k;
   end;
  end;
end;
{Ãîëîâíàÿ ïðîãðàììà}
begin
 clrscr;
 Write('Ââåäèòå êîëè÷åñòâî ÷èñåë N= ');
 Readln(n);
 writeln('Âñå ïåðåñòàíîâêè èç ',n,' çà ìèíèìàëüíîå ÷èñëî òðàíñïîçèöèé');
 for i:=1 to n do
  P[i]:=i;
 Perm(n);
 end.

все тоже самое, только вывод в самом окне программы, а не в файл, если так удобней

@kkk008009kkk · 13.05.2012, 07:13 **[ТС]**

Michael_Atak, sheldon-yura Спасибо, все работает. Однако не могли бы вы более подробно прокомментировать функцию и процедуру. Честно говорят, мало что понял.

Pascal
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
35
36
function B(m,i:integer):integer;
{Определяет номер элемента, участвующего в транспозиции}
begin
 if ((m mod 2)=0) and (m>2) then
  if i<m-1 then
   B:=i
  else
   B:=m-2
 else
  B:=m-1;
end;
 
procedure Perm(m:integer);
{Основная процедура генерирования и вывода очередной перестановки}
var
 k,k1,i:integer;
begin
 if m=1 then {Нерекурсивная ветвь}
 begin
  for i:=1 to n do
   Write(P[i]:4);
   Writeln;
  end
 else {Рекурсивная ветвь}
  for i:=1 to m do
  begin
   Perm(m-1);
   if i<m then
   begin
    k1:=b(m,i);
    k:=P[k1];
    P[k1]:=P[m];
    P[m]:=k;
   end;
  end;
end;

@Michael_Atak · 13.05.2012, 07:16

Я же просто упростил задачу, убрав подключение файла.
Пожалуйста, конечно, но спасибо надо не мне говорить, а sheldon-yura

@kkk008009kkk · 13.05.2012, 07:28 **[ТС]**

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

@Michael_Atak · 13.05.2012, 08:04

Согласен с вами. Удачи)

Новые блоги и статьи Все статьи Все блоги /
Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .
Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .

@kkk008009kkk 46 / 46 / 5 Регистрация: 24.03.2011 Сообщений: 315
	13.05.2012, 02:42 [ТС]
	Не работает. Ни тот, ни этот. 0

@Michael_Atak 54 / 57 / 26 Регистрация: 26.10.2011 Сообщений: 186
	13.05.2012, 07:16
	Я же просто упростил задачу, убрав подключение файла. Пожалуйста, конечно, но спасибо надо не мне говорить, а sheldon-yura 1

@kkk008009kkk 46 / 46 / 5 Регистрация: 24.03.2011 Сообщений: 315
	13.05.2012, 07:28 [ТС]
	Michael_Atak, Я и ему сказал спасибо. Сейчас разбираюсь в задаче. Один умный человек сказал:" проще составить свою программу, чем разобраться в чужом коде, в котором нет подробных комментариев". 0

@Michael_Atak 54 / 57 / 26 Регистрация: 26.10.2011 Сообщений: 186
	13.05.2012, 08:04
	Согласен с вами. Удачи) 0

Напечатать все перестановки чисел

Решение