Переборная задача

@dimacat · Регистрация: 04.10.2008

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

Имеется задача:
Построить алгоритм, выдающий без повторений все перестановки N чисел.
Есть алгоритм её решения:
Этот алгоpитм хорошо известен и достаточно подробно изложен. Опишем его (при N=5), от чего рассуждения не утратят общности. Алгоритм составлен так, что в процессе его исполнения перестановки N чисел располагаются лексикографически (в словарном порядке). Это значит, что перестановки сравниваются слева направо поэлементно. Больше та, у которой раньше встретился элемент, больше соответствующего ему элемента во второй перестановке. (Например, если S=(3,5,4,6,7),а L=(3,5,6,4,7), то S<L). Принцип работы алгоритма разъясним на примере. Допустим, необходимо воспpоизвести все перестановки цифр 3,4,5,6,7. Первой перестановкой считаем перестановку (3,4,5,6,7). Последней воспроизводимой перестановкой будет (7,6,5,4,3). Предположим, что на некотором шаге работы алгоритма получена перестановка P=(5,6,7,4,3). Для того чтобы определить непосредственно следующую за ней перестановку, необходимо, пересматривая данную перестановку справа налево, следить за тем, чтобы каждое следующее число было больше предыдущего, и остановиться сразу же, как только это правило нарушится. Место останова указано стрелкой: (5,6,7,4,3). - Затем вновь просматриваем пройденный путь ( справа налево ) до тех пор, пока не дойдем до первого числа, которое уже больше отмеченного. Ниже место второго останова отмечено двойной стрелкой. (5,6,7,4,3). - Э Поменяем местами отмеченные числа: (5,7,6,4,3). Э - Теперь в зоне, расположенной справа от двойной стрелки, упорядочим все числа в порядке возрастания. Так как до сих пор они были упорядочены по убыванию , то это легко сделать, перевернув указанный отрезок. Получим: Q=(5,7,3,4,6). Q и есть та перестановка, которая должна воспроизводиться непосредственно после P. Действительно, P<Q, так как, пересматривая эти перестановки слева направо, (P(2)=6,Q(2)=7). Пусть существует такая перестановка R, что P<R<Q. Тогда P(1)=R(1)=Q(1). По построению же Q(2) -- это наименьшее во множестве Q\Q(1)={3,4,6,7} число, такое, что Q(2)>P(2). Поэтому для R(2) верно одно из двух равенств: R(2)=Q(2) или R(2)=P(2). Но так как в P элементы, начиная с P(3), убывают, то из P<R следует, что если P(2)=R(2), то и P=R. Аналогично, так как в Q элементы, начиная с Q(3), возрастают, то из R<Q следует, что если R(2)=Q(2), то и R=Q.

Вот что у меня вышло (ниже). Знаю, что выдаёт не все перестановки. Хочу чтобы вы мне с эти помогли. n возьмём равное 4. Заранее спасибо!

PHP
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
const n=4;
var i, x, k, p, m, t:integer;
    a: array [1..n] of integer;
begin
for i:=1 to n do
 begin
writeln('Vvedite ', i, ' chislo: ');
readln(x);
a[i]:=x;
 end;
for i:=1 to n do
write(a[i], ' ');
for m:=1 to n*n do
         begin
k:=0;
for i:=n downto 1 do
  begin
  if a[i]<k then
    begin
  p:=a[i];
  a[i]:=k;
  a[i+1]:=p;
  k:=a[i];
  break;
    end;
if a[i]>k then k:=a[i];
 
 
  end;
  writeln;
  for i:=1 to n do
  write(a[i], ' ');
 
 end;
readln;
 
end.

@dimacat · 08.12.2008, 16:15 **[ТС]**

никто не поможет?

Новые блоги и статьи Все статьи Все блоги /
Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .

@dimacat 1 / 1 / 0 Регистрация: 04.10.2008 Сообщений: 97
	08.12.2008, 16:15 [ТС]
	никто не поможет? 0