Форум на Исходниках.RU

ПерестаноBки

cooller01 — Sun, 28 Feb 2010 20:43:57 +0000

cooller01: Всем привет!
Ребят, может подскажете мне.... давненько я уже прог не писал, но тут понадобилось...
мне нужно написать на С++ в Билдере:
1) рекурентный способ вывода списка перестановок из n-элементов в лексикографическом порядке;
2) нерекурентный- вводим лексикографический номер, разряд перестановки и исходное множество, нам в ответ- перестановку;
3) нерекурентный- наоборот: вводим перестановку а машина нам даёт её лексикографический номер.

вот програмка котурую тут обсуждали...я не очень понял что она реализует. Её вроде можно использовать в одном пункте

ПерестаноBки

SVK — Fri, 25 May 2007 10:13:23 +0000

SVK: по просьбе трудящихся 8-) дублирую код из предыдущего сообщения..

#include <fstream>

#include <iostream>

#include <string>

#include <algorithm>

#include <iomanip>

using namespace std;

// global variables

unsigned long counter = 0;

bool fl = false;

string StrToFind;

// function defenitions

ostream & operator << (ofstream &str,string &s);

istream & operator >> (ifstream &str,string &s);

void GivePermNum(string a,string b);

int main();

int main()

{

string s;

while(true)

{

cin>>StrToFind;

if((string)"#" == StrToFind) break;

else

{

s = StrToFind;

sort(s.begin(),s.end());

fl = true;

counter = 0;

GivePermNum(s,(string)"");

cout.setf(ios::right);

cout<<setw(10)<<(counter + 1)<<endl;

}

return 0;

}

void GivePermNum(string a,string b)

{

char last = 0;

int i = 0;

string s;

if(0 == a.length())

{

if(StrToFind == b)

fl = false;

else

counter++;

return;

}

else

{

int iLen = a.length();

for(i = 0; i < iLen && fl; i++)

{

if (last != a[i])

{

last = a[i];

s = a;

s.erase(s.begin() + i);

GivePermNum(s,b + last);

}

ostream & operator << (ofstream &str,string &s)

{

int i, iLen = s.length();

for(i = 0; i < iLen; str<<s[i++]);

return str;

}

istream & operator >> (ifstream &str,string &s)

{

char c; bool fl = true;

while(fl)

{

cin>>c;

if(c=='\n') fl = false;

else s+=c;

}

return str;

}

из сообщения №22

#include <fstream>

#include <iostream>

#include <string>

#include <algorithm>

#include <iomanip>

using namespace std;

// global variables

long double counter = 0;

bool fl = false;

string StrToFind;

string StrDistinct;

// function defenitions

ostream & operator << (ofstream &str,string &s);

istream & operator >> (ifstream &str,string &s);

long double GivePermNum (string a,string b);

long double GiveFactorial (string a);

long double Factorial (long double n);

void MakeDistinct(string &s);

int main();

int main()

{

string s;

long double lC;

cout.setf(ios::right);

while(true)

{

cin>>StrToFind;

if((string)"#" == StrToFind) break;

else

{

s = StrToFind;

StrDistinct = StrToFind;

sort(StrDistinct.begin(),StrDistinct.end());

sort(s.begin(),s.end());

MakeDistinct(StrDistinct);

lC = GivePermNum(s,StrToFind);

cout<<setw(10)<<(long int)(lC + 0.5)<<endl;

}

return 0;

}

long double GivePermNum(string a,string b)

{

if((size_t)1 == a.length()) return (long double )1;

if(a == b ) return (long double )1;

int i = 0,j = 0;

long double lCounter = 0;

string c;

while(StrDistinct[i] !=a[0]) i++;

while(StrDistinct[i] < b[0])

{

j = 0;

c = a;

while(c[j]!= StrDistinct[i]) j++;

c.erase(c.begin() + j);

lCounter += GiveFactorial(c);

i++;

}

bool fl = false;

i = 0;

while(a[i]!= b[0]) i++;

a.erase(a.begin() + i);

sort(a.begin(),a.end());

for(i = 0; i < a.length() && !fl; i++)

{

if(a[i] == b[0]) fl = true;

}

if(!fl)

{

i = 0;

while(StrDistinct[i] !=b[0]) i++;

StrDistinct.erase(StrDistinct.begin() + i);

}

return lCounter + GivePermNum(a,b.substr(1,b.length() -1));

}

long double GiveFactorial(string a)

{

int i = 0, iLen = a.length();

long double lResult = Factorial(iLen);

long double lRepeats;

char last;

for(i = 0,lRepeats = 0,last = a[0]; i < iLen; i++)

{

if(last == a[i]) lRepeats++;

else

{

last = a[i];

lResult/=Factorial(lRepeats);

lRepeats = 1;

}

lResult/=Factorial(lRepeats);

return lResult;

}

long double Factorial(long double n)

{

return (0 == n) ? (long double)1 : n*Factorial(n-1);

}

void MakeDistinct(string &s)

{

int i = 1;

while(i < s.length())

{

if(s[i] == s[i-1])

s.erase(s.begin() + i);

else i++;

}

ostream & operator << (ofstream &str,string &s)

{

int i, iLen = s.length();

for(i = 0; i < iLen; str<<s[i++]);

return str;

}

istream & operator >> (ifstream &str,string &s)

{

char c; bool fl = true;

while(fl)

{

cin>>c;

if(c=='\n') fl = false;

else s+=c;

}

return str;

}

ПерестаноBки

experimenter — Mon, 07 Jul 2003 11:28:43 +0000

experimenter: вот ссылка. http://acm.uva.es/problemset/submit.php
номер задачи 153, а ID надо получить,т.е. зарегиться.
насчет алгоритма. я имел ввиду, что если делать, как я изначально предполагал, т.е. генерить все подряд в лексографическом порядке, пока не встретишь нужную, то это занимает очень много времени. а на счет обратимости я не знаю, скорее всего да, но это по-моему смысла не имеет.
вот код такой программы: считает все "на ура", но долго, правда надо, наверное, long int на long double заменить.

зы
т.е. в итоге сопоставить взаимное соответсвие я не смог, но быстро подссчитать номер смог(в предыдущей проге, а не в той, которая в этом посте.)

ПерестаноBки

SVK — Mon, 07 Jul 2003 10:12:02 +0000

SVK: