Алгоритм перестановок

 Msg  : 1611 из  3560 -1596 +1615 *1614 
 From : Oleg I.  Khovayko                      2:5020/400       Срд 23  Авг 00 18:02 
 To   : All                                                     Чтв 24 Авг 00 06:21 
 Subj : Re: перебор вариантов перебора 

Задача: Кто знает алгоритм полной перестановки цифр в числе ? Hапример: 123,132,213,231,312,321

Решение

1. Сначала составим список разрешенных цифр, и сколько этих цифр разрешено. Hапример, если надо создать все возможные перестановки цифр 1,3,3,7 то список будет такой:

• 1 - 1 шт
• 3 - 2 шт
• 7 - 1 шт

2. Очевидно, что в первой (самой левой) позиции синтезированного числа последовательно сменятся все разрешенные цифры из списка. Поэтому для позиции 0 пустим цикл по всем разрешенным цифрам. Hо так как текущая цифра изъята для нашей позиции 0, то еенный "счетчик разрешения" уменьшаем на единицу (а после перехода от этой цифры к следующей - восстанавливаем значение счетчика для текушей цифры и уменьшаем значение счетчика для следующей).

3. Для позиции 1 справедливы все те же рассуждения, что и для позиции 0, посему напрашивается рекурсивный алгоритм следующего вида:

char result[5]; 

char enabled[] =" 137"; 
char enabled_cnt[] = {  1, 2, 1 }; 

generate(char *pos) { 
  int n; 
  int printflag =  1; 
  *pos = 0; 

  for(n = 0; enabled[n];  n++) { 
    if(enabled_cnt[n]  > 0) { 
        *pos = enabled[n]; 
        enabled_cnt[n]--; 
        generate(char pos + 1); 
        enabled_cnt[n]++; 
        printflag = 0; 
    } 
  } 

  if(printflag) 
    printf("%s\n",  result); 

} 


main() { 
  generate(result); 
} 

4. WARNING!! Я не проверял этот алгоритм, а просто "с ходу" придумал его и написал в этом письме. Поэтому не факт, что он сразу с ходу заработает. Hо я надеюсь, идея понятна, и до ума этот алгоритм довести особого труда не составит.

1.

Аноним

27 апреля 2006, 08:15:06

А мне пришёл в голову такой рекурсивный алгоритм...

program Perest;
{$M 65520,0,655360}
uses crt;
var mas : array[1..10] of byte;
i,N : 1..10;

procedure recurs(num : byte);
var i,j : integer;

procedure change(var a,b : byte);
var c:byte;
begin
c:=a;
a:=b;
b:=c;
end;

begin
if num = N then
begin
for i:=1 to N do
write(mas,' ');
writeln;
end else
for j:=num+1 to N do
begin
Change(mas[num+1], mas[j]);
recurs(num+1);
Change(mas[num+1], mas[j]);
end;
end;

begin
clrscr;
write('The quantity of array''s elements (1..10): ');
readln(N);

for i:=1 to N do
mas:=i;

recurs(0);
readln;
end.

Этот я проверил, так что он точно работает :)

А вот мне интересен нерекурсивный алгоритм, я где-то видел небольшую программку, что выводила на экран все перестановки С(n, k) (C из n по k), и которая была написана всего-лишь в 5 циклов for. Там, вроде, был перевод в другую систему счисления, для чего он нужен- не помню. Если у кого есть этот алгоритм, please, буду очень признателен.
Спасибо за внимание :)

2.

Аноним

+2 / -0

31 мая 2005, 12:01:49

Смотрите шаблон next_permutation и prev_permutation в STL (#include <algorithm>)