Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11631
Последний выпуск: 19.06.2015

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


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о я надеюсь, идея понятна, и до ума этот алгоритм довести особого труда не составит.

Oleg I. KHOVAYKO

Оставить комментарий

Комментарий:
можно использовать BB-коды
Максимальная длина комментария - 4000 символов.
 

Комментарии

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>)
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог