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

Форум программистов: 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 сообщение ] 


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

Зарегистрированные пользователи: Google [Bot]


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

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