Генерация перестановок для Д.Белькова

Интересные алгоритмы, олимпиадные задачи, эффектные и эффективные решения. freepascal, delphi, c, c++, c#, java, javascript, perl, ruby, python, php, bash, wsh и т.д. Компиляторы, интерпретаторы, линкеры, отладчики, системы контроля версий и многое другое.

Модератор: xdsl

Генерация перестановок для Д.Белькова

Сообщение Vladislav_133 26 июн 2011, 16:00

Обещал Денису Белькову набросать алгоритм по генерации перестановок.
Появилось время и не много размялся.


Код: Выделить всё
#include <stdio.h>
#include <string.h>
char line[500],line1[500];
int pr[500];
void fc(int,int,int);
int rtrim(char * );
int main()
{
    int j;
    for(j=0; j<500; j++)
    {
        line1[j]='\0';
        pr[j]=0;
    }
    if(fgets(line,100,stdin)==NULL)
    {
        fprintf(stdout,"No chars!\n");
        return 1;
    }
    rtrim(line);
    int g=strlen(line);
    for(j=0; j<g; j++)fc(j,0,g);
    return 0;
}
//рекурсивная процедура
void fc(int i, int c, int l)
{
    int h;
    line1[c]=line[i]; pr[i]=1; c++;
    if(c==l)
    {
//выводим перестановку....
        fprintf(stdout,"%s \n", line1);
    }
    else
    {
         for(h=0; h<l; h++) if(!pr[h]) fc(h,c,l);
    }
//выход из рекурсии - восстановление параметров....
    c--; pr[i]=0;
}
//удаление правых лишних символов
int rtrim(char * s)
{
    int l=strlen(s);
    if(l==0)return 0;
    while(s[l-1]<=32&&l>0)l--;
    s[l]='\0';
    return 0;
}


Запуск программы соответственно prog <input.txt >output.txt
В первой строке последовательность символов для перестановки.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Генерация перестановок для Д.Белькова

Сообщение xdsl 26 июн 2011, 20:22

Кстати, Владислав Юрьевич, у нас на форуме есть классная, имхо, подсветка: https://shgpi.edu.ru/forum/viewtopic.php?f=20&t=515
Например, Ваш код будет выглядеть так:
Подсветка синтаксиса: (prst.c) [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка c
#include <stdio.h>
#include <string.h>
char line[500],line1[500];
int pr[500];
void fc(int,int,int);
int rtrim(char * );
int main()
{
    int j;
    for(j=0; j<500; j++)
    {
        line1[j]='\0';
        pr[j]=0;
    }
    if(fgets(line,100,stdin)==NULL)
    {
        fprintf(stdout,"No chars!\n");
        return 1;
    }
    rtrim(line);
    int g=strlen(line);
    for(j=0; j<g; j++)fc(j,0,g);
    return 0;
}
//рекурсивная процедура
void fc(int i, int c, int l)
{
    int h;
    line1[c]=line[i]; pr[i]=1; c++;
    if(c==l)
    {
//выводим перестановку....
        fprintf(stdout,"%s \n", line1);
    }
    else
    {
         for(h=0; h<l; h++) if(!pr[h]) fc(h,c,l);
    }
//выход из рекурсии - восстановление параметров....
    c--; pr[i]=0;
}
//удаление правых лишних символов
int rtrim(char * s)
{
    int l=strlen(s);
    if(l==0)return 0;
    while(s[l-1]<=32&&l>0)l--;
    s[l]='\0';
    return 0;
}
 
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Генерация перестановок для Д.Белькова

Сообщение xdsl 26 июн 2011, 22:34

Имхо, не очень эффективный вариант перестановок у Вас, Владислав Юрьевич. Не знаю условия задачи, может там специфика какая, но вот такой вариант поиска всех перестановок работает быстрее, хоть и на фрипаскале сделан:
Подсветка синтаксиса: (prst.pas) [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка pascal
  1. {$mode objfpc}
  2. {$H+}
  3.  procedure swapc(var a,b:char);
  4.    var c:char;
  5.   begin  c:=a; a:=b; b:=c;  end;
  6.  
  7.  procedure prst(var s:string;index:integer);
  8.     var i:integer;
  9.  begin
  10.   if index=length(s) then writeln(s)
  11.   else begin
  12.         prst(s,index+1);
  13.         for i:=index+1 to length(s) do begin
  14.          swapc(s[index],s[i]);
  15.          prst(s,index+1);
  16.          swapc(s[index],s[i]);
  17.         end;
  18.   end;
  19.  end;
  20.  
  21. var s:string;
  22. begin
  23.  readln(s);
  24.  prst(s,1);
  25. end.
  26.  
Ваш вариант на последовательности 0123456789 работал 1.4 секунды, мой на той-же последовательности - 0.5 секунды. Вывод, естественно, перенаправлялся в /dev/null для чистоты эксперимента.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Генерация перестановок для Д.Белькова

Сообщение Vladislav_133 27 июн 2011, 10:46

Наверное. Я не ставил задачи найти самое быстрое решение. Так, набросал вариант.
У меня есть книжка, где все варианты алгоритмов перестановок имеются,
но я ни разу эти алгоритмы не разбирал. Все ленился или руки не доходили.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Генерация перестановок для Д.Белькова

Сообщение Vladislav_133 27 июн 2011, 10:54

Но что касается перестановок, то есть один существенный момент. Начиная с одиннадцати начинает тормозить любой алгоритм.
Время экспоненциально растет.
Последний раз редактировалось Vladislav_133 27 июн 2011, 22:15, всего редактировалось 1 раз.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Генерация перестановок для Д.Белькова

Сообщение Vladislav_133 27 июн 2011, 10:57

Что касается моего алгоритма, то в нем есть ресурс ускорения, только уж пусть Денис поразмыслит над этим.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.


Вернуться в Алгоритмизация и программирование

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1