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

@Jane_Jane · Регистрация: 08.03.2019

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

Здравствуйте. Наткнулся на программу генерацию всех перестановок, и есть 2 момента, которые не могу понять. Объясните, пожалуйста.

1) Зачем нужно эта строка в гланой программе?

Pascal

1 2	for j := 1 to n do b[j] := j;

2) Как работает эта строчка после процедуры generate(l+1,r,a) ?

Pascal

1	v := a[l]; a[l] := a[i]; a[i] := v;

С одной стороны я понял, что она возвращает пеерстановку на место
Было RGB, поменяется на RBG, наша строка возвращает RGB. Но также я не могу понять другой ее момент:

Pascal

b[3]= 3
 
l=r?13
before a[1]= 1
before a[1]= 1
 
aftef a[1]= 1
after a[1]= 1
 
 
l=r?23
before a[2]= 2  
before a[2]= 2   
 
aftef a[2]= 2
after a[2]= 2
 
 
l=r?33
1
red 
2
green 
3
blue 
before2 a[2]= 2     {Здесь равняет 2}
before2 a[2]= 2
aftef2 a[2]= 2
after2 a[2]= 2
 
before a[2]= 2
before a[3]= 3
 
aftef a[2]= 3
after a[3]= 2
 
 
l=r?33
1
red 
2
blue 
3
green 
before2 a[2]= 3
before2 a[3]= 2
aftef2 a[2]= 2       {Здесь произошло возвращение}
after2 a[3]= 3
 
before2 a[1]= 1     {Здесь равняет 1...Как???}
before2 a[1]= 1
aftef2 a[1]= 1
after2 a[1]= 1

Pascal

const
  n = 3; 
  fig: array[1..n] of string[10] = ('red', 'green','blue');
 
type
  mas = array[1..n] of byte;
procedure generate(l, r: integer; a: mas);
var
  i, v: integer;
begin
  writeln('l=r?',l, r );
  if (l = r) then
  begin
    for i := 1 to n do begin
      writeln(i);
      write(fig[a[i]], ' ');
    writeln;
  end;
  end
  else
  begin
    for i := l to r do
    begin
      writeln('before a[',l,']= ', a[l]);
      writeln('before a[',i,']= ', a[i]);
      writeln();
      v := a[l]; a[l] := a[i]; a[i] := v;
      writeln('aftef a[',l,']= ', a[l]);
      writeln('after a[',i,']= ', a[i]);
      writeln;
      writeln;
      generate(l + 1, r, a); 
      writeln('before2 a[',l,']= ', a[l]);
      writeln('before2 a[',i,']= ', a[i]);
      v := a[l]; a[l] := a[i]; a[i] := v; 
      writeln('aftef2 a[',l,']= ', a[l]);
      writeln('after2 a[',i,']= ', a[i]);
      writeln;
    end;
  end;
end;
 
var
  j: integer;
  b: mas;
 
begin
 
  for j := 1 to n do
    b[j] := j;
  generate( 1, n, b);
  readln
end.

Спасибо Вам за помощь.

@JuriiMW · 09.03.2019, 14:59

Сообщение от Jane_Jane

Зачем нужно эта строка в гланой программе?

Чтобы заполнить начальную расстановку: 1 2 3.

Сообщение от Jane_Jane

Как работает эта строчка после

Тупо меняет два элемента массива…
Её можно заменить на один оператор Swap(a[L],a[i]);

@Jane_Jane · 09.03.2019, 15:28 **[ТС]**

JuriiMW, Получается, сначала печатает:
1) red, green, blue
А потом меняет на:
2) red, blue, green
Здесь в выводе можно увидеть, что программа возвращает первоначальную строку(1):

Pascal

l=r?13
before a[1]= 1
before a[1]= 1
 
aftef a[1]= 1
after a[1]= 1
 
 
l=r?23
before a[2]= 2
before a[2]= 2
 
aftef a[2]= 2
after a[2]= 2
 
 
l=r?33
1
red 
2
green 
3
blue 
before2 a[2]= 2
before2 a[2]= 2
aftef2 a[2]= 2
after2 a[2]= 2
 
before a[2]= 2
before a[3]= 3
 
aftef a[2]= 3
after a[3]= 2
 
 
l=r?33
1
red 
2
blue 
3
green 
before2 a[2]= 3
before2 a[3]= 2
aftef2 a[2]= 2
after2 a[3]= 3

А почему потом происходит перестановка:
green, red, blue

Pascal

before2 a[1]= 1
before2 a[1]= 1
aftef2 a[1]= 1
after2 a[1]= 1

Там же было 2 и 3, как оно в 1 и 1 превратилось?

@JuriiMW · 09.03.2019, 15:47

Я ни чего не могу увидеть, т.к. ваша программа загажена всякими лишними выводами!
Убирайте все и пользуйтесь отладчиком:

Pascal

const
  n = 3; 
  fig: array[1..n] of string[10] = ('red', 'green','blue');
 
type
  mas = array[1..n] of byte;
 
procedure generate(l, r: integer; a: mas);
begin
  if l = r then
    begin
      for var i := 1 to n do fig[a[i]].print;
      writeln;
    end
  else
    for var i := l to r do
      begin
        Swap(a[L], a[i]);
        generate(l+1, r, a); 
        Swap(a[L], a[i]);
      end;
end;
 
begin
  var a : mas;
  for var i := 1 to n do a[i] := i;
  generate(1, n, a);
end.

Вот теперь программа выводит то, что нужно!

Добавлено через 5 минут
Ну и зачем здесь этот промежуточный „костыль“ fig—a?
И не нужен лишний параметр процедуры!

Pascal

const
  n = 3;
  
var
  a : array of String := ('red', 'green','blue');
 
procedure generate(L : integer; a : array of String);
begin
  if L = n-1 then
    begin
      a.Println;
    end
  else
    for var i := L to n-1 do
      begin
        Swap(a[L], a[i]);
        generate(L+1, a); 
        Swap(a[L], a[i]);
      end;
end;
 
begin
  generate(0, a);
end.

Добавлено через 2 минуты
О! Да! Ещё константа…
Не нужна константа:

Pascal

var
  a : array of String := ('red', 'green', 'blue', 'magenta');
 
procedure generate(L : integer; a : array of String);
begin
  if L = a.Length-1 then
    begin
      a.Println;
    end
  else
    for var i := L to a.Length-1 do
      begin
        Swap(a[L], a[i]);
        generate(L+1, a); 
        Swap(a[L], a[i]);
      end;
end;
 
begin
  generate(0, a);
end.

@Jane_Jane · 09.03.2019, 15:59 **[ТС]**

JuriiMW, лишние выводы мне былы нужны из-за того, что было непонятно, как рекурсивная процедура выполняется...

Pascal

red green blue magenta{Здесь вывод первой строки}
red green magenta blue{Здесь обмен третьей и четвертой переменнами}
red blue green magenta{Не понимаю, почему так...}
red blue magenta green
red magenta blue green
red magenta green blue
green red blue magenta{Здесь тоже не понимаю, почему green встал на первое место}

В ABC.net, можно ли не видеть шаги, которые выполняются в PABCSystem.pas, а то очень долго всё выполняется...

@Sun Serega · 09.03.2019, 16:41

Сообщение от Jane_Jane

можно ли не видеть шаги, которые выполняются в PABCSystem.pas, а то очень долго всё выполняется

Я так понимаю вы про отладку...

В отладке есть 3 способа выполнить программу немного дальше и снова поставить на паузу:

1. Поставить точку останова (тыкните слева, появится красный кружочек) и нажать F9. Программа будет выполнятся пока не дойдёт до первой точки останова.

2. Нажать F7. Если сейчас отладка стоит на вызове подпрограммы - она перейдёт внутрь этого вызова. Если нет - перейдёт на следующую строчку.

3. Нажать F8. В отличии от F7, F8 не попытается перейти внутрь вызова подпрограммы, а всегда только перейдёт на следующую строчку.

@JuriiMW · 09.03.2019, 17:04

Сообщение от Sun Serega

F8 не попытается перейти внутрь вызова подпрограммы,

Не „не попытается“, а „не будет входить“…
Но с оговоркой!
Скажем, если внутри подпрограммы будет точка останова, то программа прервётся внутри подпрограммы.

Т.е., если поставить в последней программе точку останова на шестой строке

Pascal

6	if L = a.Length-1 then

то можно легко отлаживать всё с помощью клавиши F8 не проваливаясь в PABCSystem.

@JuriiMW 5079 / 2651 / 2349 Регистрация: 10.12.2014 Сообщений: 10,028
	09.03.2019, 14:59	2
	Сообщение от Jane_Jane Зачем нужно эта строка в гланой программе? Чтобы заполнить начальную расстановку: 1 2 3. Сообщение от Jane_Jane Как работает эта строчка после Тупо меняет два элемента массива… Её можно заменить на один оператор `Swap(a[L],a[i]);` 1

@Sun Serega 2309 / 1420 / 516 Регистрация: 07.04.2017 Сообщений: 4,723
	09.03.2019, 16:41	6
	Сообщение от Jane_Jane можно ли не видеть шаги, которые выполняются в PABCSystem.pas, а то очень долго всё выполняется Я так понимаю вы про отладку... В отладке есть 3 способа выполнить программу немного дальше и снова поставить на паузу: 1. Поставить точку останова (тыкните слева, появится красный кружочек) и нажать F9. Программа будет выполнятся пока не дойдёт до первой точки останова. 2. Нажать F7. Если сейчас отладка стоит на вызове подпрограммы - она перейдёт внутрь этого вызова. Если нет - перейдёт на следующую строчку. 3. Нажать F8. В отличии от F7, F8 не попытается перейти внутрь вызова подпрограммы, а всегда только перейдёт на следующую строчку. 1