→ Для вступления в общество новичков и профессионалов программирования, пожалуйста нажмите здесь ...

Форум программистов: C++, Basic, Delphi, Pascal, JavaScript
Логин: Пароль:
Запомнить?  
@Mail.ru



Начать новую тему Ответить на тему  [ 1 сообщение ] 
Алгоритм генерации перестановок в лексикографическом порядке 
Автор Сообщение
Начинающий

Регистрация: 13.09.2012
Сообщения: 5
Языки:
Специальность:

Репутация: 0 [ ? ]
Сообщение Алгоритм генерации перестановок в лексикографическом порядке
У меня проблема. Нужно перебрать все лексикографически следующие перестановки. Вот мой код. Одна перестановка делается, а дальше я не знаю, как мне повторить все мои действия для этой перестановки и так дали до конечной. Эта программа, что я написал делает одну следующую перестановку. Можно заставить чтоб она с той перестановки делала следующую и так дали до конца???
Если нужно, то вот Алгоритм генерации перестановок в лексикографическом порядке:

1. Просматриваем а1, ..., аn с конца до тех пор, пока не попадется ai<ai+1. Если таковых нет, то генерация закончена.
2. Рассматриваем ai+1, ai+2, ..., an. Найдем первый с конца am больший ai и поменяем их местами.
3. ai+1, ai+2, ..., an переставим в порядке возрастания (для этого достаточно её переписать с конца).
4. Печатаем найденную перестановку.
5. Возвращаемся к пункту 1.
Спасибо!!!

#include <iostream>
#include <iomanip>
#include <sstream>
#include <conio.h>
#include <cmath>
using namespace std;

int main()
{
cout.width(62);
cout<<"Pobudova leksykografichno nastupnoi perestanovky"<<endl<<endl;
int n;
cout<<"Vvedit naturalne chyslo: ";
cin>>n;
cout<<endl;
int *mas=new int[n];
for (int i=1;i<=n;++i)
{
cout<<"Vvedit "<<i<<"-te chyslo perestanovky: ";
cin>>mas[i];
}
for (int i=1;i<=n;++i)
{
cout<<mas[i];
}
cout<<endl;
int b1=0,b2=0,k,k1,i;
for (i=n;(i>=1)&&(b1<=b2);--i)
{
b1=mas[i]%10;
b2=mas[i-1]%10;
k=mas[i-1];
k1=i-1;
}
int temp;
for (int i=n;i>=n;--i)
{
if (mas[i]>k)
{
temp=k;
mas[k1]=mas[i];
mas[i]=temp;
}
}
for (int i=1;i<=n;++i)
cout<<mas[i];
cout<<endl;

for (int i=k1+1,f=0;(i<=(n+k1+1)/2)&&(f<n);++i,++f)
{
swap(mas[i],mas[n-f]);
}
for (int i=1;i<=n;++i)
cout<<mas[i];

getche();
return 0;
}


28.10.2012 20:05
Профиль Отправить email
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ 1 сообщение ] 


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

Зарегистрированные пользователи: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Перейти:  
cron
© 2013 «Форум программистов Украины»