Паскаль. Задачка с рекурсией!

[Irdis]

Всем доброго времени суток!
Помогите с решением следующени задачки: Дано N различных натуральных чисел. Напечатать все перестановки этих чисел.
Вопрос в следующем: подскажите пожалуйста как осуществить сортировку этих чисел в массиве, да ещё при условии что если эллементы будут одинаковыми, то кол-во перестановок будет меньше???

[alexBlack]

Пожалуйста, выражайтесь яснее. Разбейте свой вопрос на отдельные предложения.

[Irdis]

Вопрос: подскажите алгоритм перестановки чисел в массиве по заданным условиям.
Условия:
1)если эллементы в массиве будут одинаковыми, то количество перестановок будет меньше!
Например: дан массив из чисел 1 2 3
Кол-во перестановок будет равно 6 (факториал), но если будет, например, 1 2 2, то кол-во перестановок будет всего 3.
2) все перестановки должны быть выведены на экран и ни разу не повторяться.

[alexBlack]

Задача с рекурсией, поэтому придется хранить все перестановки.

 
const Cnt = 10;
type
   TArray = array [1..Cnt] of integer;  // одна перестановка
   TPermutation = array [1..1000] of TArray; // список перестановок

Теперь сама рекурсия. Вычисляем все перестановки для N-1 элементов.
Из этих перестановок и элемента N формируем новые перестановки.
Каждую перестановку добавляем в список, если ее еще не было.

procedure Permutation(A:TArray; ACount : integer; var P:TPermutation; var Count:integer);

 function PermutationExists(A:TArray):boolean;
 var i, j:integer;
 begin
    result := false;
    for i:=1 to count do begin
       result := true;
       for j:=1 to ACount do begin
          if P[i][j] <> A[j] then begin
             result := false;
             break;
          end;
       end;
       if result then break;
    end;
 end;

var P1:TPermutation;
    NC, Count1, k, t:integer;
    A1:TArray;
begin
   if ACount = 1 then begin
      // Для одного элемента возможна только одна перестановка
      Count := 1;
      P[Count][1] := A[1];
   end else begin
      // Сначала вычислим все перестановки
      // для массива с меньшим количеством элементов
      Permutation(A, ACount-1, P1, Count1);
      // Теперь для каждой перестановки получаем все варианты
      // с последним числом массива
      count := 0;
      for k:=1 to Count1 do begin
         A1 := P1[k];
         A1[ACount] := A[ACount];
         NC := ACount;
         While NC >= 1 do begin
            if not PermutationExists(A1) then begin
               inc(Count);
               P[Count] := A1;
            end;
            if NC > 1 then begin
               t := A1[NC];
               A1[NC] := A1[NC-1];
               A1[NC-1] := t;
            end;
            dec(NC);
         end;
      end;
   end;
end;

И вызов:

var A : TArray;
    N, CountP : integer;
    P:TPermutation;
begin
   N := 5;
   A[1] := 3;
   A[2] := 2;
   A[3] := 1;
   A[4] := 2;
   A[5] := 2;

   Permutation(A, N, P, CountP);
   for i:=1 to CountP do begin
      S := '';
      for j:=1 to N do S := S + intToStr(P[i][j])+ ' ';
      writeLn(S);
      
   end;

[Irdis]

Спасибо огромное! Это даже больше того что я хотел!
Щас будет разбираться!!!
Вообще круто! СПАСИБО!!!

[Irdis]

Ещё такой вопросик:
что значит в коде вызова строчка:
S := '';
Компилятор ругаецтся!!!
Это двойка (2)???

[Somebody]

Перестановки с рекурсией? Неоптимальный метод.

[Irdis]

Somebody, это у нас лаба, 1 курс. С рекурсией обязательно! Без рекурсии сделал для массива с кол-вом эллементов 3! И все. Даже самые умы нашей группы ничего придумать не могут! :'(
Можешь предложить свой вариант плиз...

[Somebody]

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

Можешь предложить свой вариант плиз...

Вариант без рекурсии

var n,i,j,t:integer;
    a:array [0..20] of word;
begin
write('n='); readln(n);
for i:=1 to n do a[i]:=i;
repeat
for i:=1 to n do write(a[i],' ');
writeln;
i:=n; repeat dec(i) until a[i]<a[i+1];
j:=n; while a[j]<=a[i] do dec(j);
t:=a[i]; a[i]:=a[j]; a[j]:=t; inc(i);
for j:=0 to (n-i+1) div 2-1 do begin
    t:=a[i+j]; a[i+j]:=a[n-j]; a[n-j]:=t;
    end;
until a[0]<>0;
readln;
end.

[Irdis]

Somebody, ну это понятно, только вот у тебя в коде выходит так, что пользователь не вводит числовые значения в массиве, а это как раз нужно!