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

незачто :-)
хоть кому-то пригодилось ЭТО ;D

Вообще нормально бы в рекурсию уйти - мы такую задачу на уроках делали, рекурсия там будет, рекурсия. :-/

Цитата Fieral, 19.06.03, 09:45:50

Вообще нормально бы в рекурсию уйти - мы такую задачу на уроках делали, рекурсия там будет, рекурсия. :-/

ну, понятно. по-моему задачи такого типа в легче всего рекурсией решать. по-крайней мере, я так всегда делаю. вопрос в другом - как организовать рекурсию. вот в чем вопрос!  :

Я так понимаю, что до кода дело так и не дошло, тады вот: (хотел еще неделю назад публикануть, но посмотрел и понял как все запущено; однако может ктоньть разберется)

<br>char GenKey(  HWND  hwndDlg,<br>                   char lkey,//длинна перестановки<br>                   char * keymask,//какойто выходной буфер :)<br>                   char _sys_=0,//признак цикличного вызова<br>                   char * numkey=0,//перестановка на выходе цикличного вызова<br>                   char *start=0//номер перестановки цикличного вызова<br>                )<br> {<br>  static char i,k,mask[3],nu[MaxLenMath+1],nur[MaxLenMath+1],fa[MaxLenMath+1],f;<br><br>  if(!_sys_)SendDlgItemMessage(hwndDlg,IDC_EDIT31,WM_GETTEXT,<br>                               (WPARAM)(MaxLenMath+1),(LPARAM)nur);<br>  if(_sys_){strcpy(nur,start);nu[0]='1';nu[1]=0;add(start,nu);}<br><br>  for(i=0;i<lkey;i++){keymask[i]=0;}<br>  fak(fa,lkey);<br><br>  f=0;<br>  if(strlen(nur)>strlen(fa)+1){nur[strlen(fa)+1]=0;f=1;}<br>  while(sub(nur,fa)) f++;<br><br>  for(i=lkey;i>1;i--)<br>   {<br>    strcpy(nu,nur);<br>    while(sub(nu,fa));k=0;<br>    strcpy(nur,nu);<br>    fak(fa,i-1);<br>    while(sub(nu,fa)) k++;<br>    k=k+1+(lkey-i);<br>    while(keymask[k-1])k=keymask[k-1];<br>    keymask[k-1]=lkey-i+1;<br>    if(!_sys_){sprintf(mask,"\%d",k);<br>               SendDlgItemMessage(hwndDlg,IDC_EDIT1+lkey-i,WM_SETTEXT,0,<br>                                  (LPARAM)mask);<br>              } else numkey[lkey-i+1]=k;<br>   }<br>  k=lkey;<br>  while(keymask[k-1])k=keymask[k-1];<br>  if(!_sys_){sprintf(mask,"\%d",k);<br>             SendDlgItemMessage(hwndDlg,IDC_EDIT0+lkey,WM_SETTEXT,0,<br>                                (LPARAM)mask);<br>            } else numkey[lkey]=k;<br>  return f;<br> }<br><br>void ReGenKey(HWND  hwndDlg,char lkey,char * keymask)<br> {<br>  char i,k,p,mask[3],nu[MaxLenMath+1]="0",fa[MaxLenMath+1];<br><br>  for(i=0;i<lkey;i++){keymask[i]=0;}<br>  for(i=0;i<(lkey-1);i++)<br>   {<br>    SendDlgItemMessage(hwndDlg,IDC_EDIT1+i,WM_GETTEXT,(WPARAM)3,(LPARAM)mask);<br>    k=MyAtoi(mask);<br>    while(keymask[k-1])k=keymask[k-1];<br>    keymask[i]=k;<br>    sprintf(mask,"\%d",k);<br>    fak(fa,lkey-1-i);<br>    p=k-(i+1);<br>    while(p){add(nu,fa);p--;}<br>   }<br>  SendDlgItemMessage(hwndDlg,IDC_EDIT31,WM_SETTEXT,0,(LPARAM)nu);<br> }<br><br>void trstr(char*a)<br> {<br>  int i=0;<br>  while(a[i]=='0')i++;<br>  if(i)strcpy(a,a+i);<br> }<br><br>char sub(char * a,char * b)<br> {<br>  char reza[MaxLenMath+1];<br>  strcpy(reza,a);<br>  int la=strlen(a),lb=strlen(b),i,ii;<br>  for(i=lb;i>0;i--)<br>  {<br>   if(a[la-lb-1+i]>=b[i-1]) a[la-lb-1+i]=a[la-lb-1+i]-b[i-1]+'0';<br>    else{ii=i-1;<br>         while(a[la-lb-1+ii]=='0'&&(la-lb-1+ii)>=0) {a[la-lb-1+ii]='9';ii--;}<br>         if((la-lb-1+ii)<0){strcpy(a,reza);return 0;}<br>         a[la-lb-1+ii]--;<br>         a[la-lb-1+i]=a[la-lb-1+i]-b[i-1]+10+'0';<br>        }<br>  }<br>  trstr(a);<br>  return 1;<br> }<br><br>char add(char * a,char * b)<br> {<br>  int i=0,ii,la=strlen(a),lb=strlen(b);<br>  char reza[MaxLenMath+1];<br>  if(la!=MaxLenMath){for(i=0;i<MaxLenMath;i++)reza[i]='0';reza[MaxLenMath]=0;<br>                     strcpy(reza+MaxLenMath-la,a);<br>                     strcpy(a,reza);<br>                    }<br>  a[MaxLenMath]=0;la=MaxLenMath;<br>  for(i=lb;i>0;i--)<br>   {<br>    if(a[la-lb-1+i]+b[i-1]-'0'<='9') a[la-lb-1+i]=a[la-lb-1+i]+b[i-1]-'0';<br>     else {ii=i-1;<br>           while(a[la-lb-1+ii]=='9'&&(la-lb-1+ii)>=0){a[la-lb-1+ii]='0';ii--;}<br>           if((la-lb-1+ii)<0)return 0;<br>           a[la-lb-1+ii]++;<br>           a[la-lb-1+i]=a[la-lb-1+i]+b[i-1]-10-'0';<br>          }<br>   }<br>  trstr(a);<br>  return 1;<br> }<br><br>void fak(char* a,char f)<br> {<br>  char ff,aa[MaxLenMath+1];<br>  if(f<=1){a[1]=0;a[0]='1';return;}<br>  sprintf(a,"\%d",f);<br>  strcpy(aa,a);<br>  f--;<br>  while(f>1)<br>   {<br>    ff=f;<br>    while(ff>1){add(a,aa);ff--;}<br>    f--;<br>    strcpy(aa,a);<br>   }<br> }<br>

ну, ты бы хоть примерный алгоритм сказал. :-/

Цитата Experimenter, 21.06.03, 18:59:34

ну, ты бы хоть примерный алгоритм сказал. :-/

Дк.. этот код был написан четыре года назад и алгоритм, который я выдумывал сам, уже давно забыт
Так что, Господа Программисты, никогда не ленитесь писать комментарии
Если есть желание, то могу выслать полный проект той прожки в которой использовался этот код, хотя кому-то я ее уже когда-то  высылал...

эту задачу я решил, наконец-то. решил без генерения.
идея такова. есть, например, перестановка aabc (самая первая).
от нее надо добраться до caba. чтобы добраться, надо сначала пройти все перестановки
a???, которых 3! = 6, потом
b???, которых 3!/2! = 3, потом
приходим к перестановке сaab. одну букву подобрали.
таким же макаром движемся от перестановки aab до aba, суммируя перестановки на каждом шаге.
алгоритм и программа рабочие. работает очень быстро.

вот код на С++.

<br>#include <fstream><br>#include <iostream><br>#include <string><br>#include <algorithm><br>#include <iomanip><br><br>using namespace std;<br><br>// global variables<br>long double counter = 0;<br>bool fl      = false;<br>string StrToFind;<br>string StrDistinct;<br><br>// function defenitions<br>ostream & operator << (ofstream &str,string &s);<br>istream & operator >> (ifstream &str,string &s);<br><br>long double GivePermNum   (string a,string b);<br>long double GiveFactorial (string a);<br>long double Factorial     (long double n);<br>void              MakeDistinct(string &s); <br><br>int main();<br><br><br>int main()<br>{<br>string s;<br>long double  lC;<br>cout.setf(ios::right);<br><br>while(true)<br>{<br>cin>>StrToFind;<br>if((string)"#" == StrToFind) break;<br>else<br>{<br>      s = StrToFind;<br>      StrDistinct = StrToFind;<br>      sort(StrDistinct.begin(),StrDistinct.end());<br>      sort(s.begin(),s.end());<br>      MakeDistinct(StrDistinct);<br><br>      lC = GivePermNum(s,StrToFind);<br>      cout<<setw(10)<<(long int)(lC + 0.5)<<endl;<br>}<br><br>}<br><br>return 0;<br>}<br><br>long double GivePermNum(string a,string b)<br>{<br><br>if((size_t)1 == a.length()) return (long double )1;<br>if(a == b ) return (long double )1;<br><br>int i = 0,j = 0;<br>long double lCounter = 0;<br>string c;<br><br>while(StrDistinct[i] !=a[0]) i++;<br><br>while(StrDistinct[i] < b[0])<br>{<br>j = 0;<br>c = a;<br>while(c[j]!= StrDistinct[i]) j++;<br>c.erase(c.begin() + j);<br>lCounter += GiveFactorial(c);<br>i++;<br>}<br><br>bool fl = false;<br><br>i = 0;<br>while(a[i]!= b[0]) i++;<br>a.erase(a.begin() + i);<br>sort(a.begin(),a.end());<br><br>for(i = 0; i < a.length() && !fl; i++)<br>{<br>      if(a[i] == b[0]) fl = true;<br>}<br><br>if(!fl)<br>{<br>      i = 0;<br>      while(StrDistinct[i] !=b[0]) i++;<br>      StrDistinct.erase(StrDistinct.begin() + i);<br>}<br><br><br>return lCounter + GivePermNum(a,b.substr(1,b.length() -1));<br>}<br><br>long double GiveFactorial(string a)<br>{<br>int i = 0, iLen = a.length();<br>long double  lResult = Factorial(iLen);<br>long double  lRepeats;<br>char last;<br><br>      for(i = 0,lRepeats = 0,last = a[0]; i < iLen; i++)<br>      {<br>            if(last == a[i]) lRepeats++;<br>            else<br>            { <br>                  last = a[i];<br>                  lResult/=Factorial(lRepeats);<br>                  lRepeats = 1;<br>            }<br>      }<br>      <br>lResult/=Factorial(lRepeats);<br>return lResult;<br>}<br><br>long double Factorial(long double n)<br>{<br>      return (0 == n) ? (long double)1 : n*Factorial(n-1);<br>}<br><br>void MakeDistinct(string &s)<br>{<br>int i = 1;<br>      while(i < s.length())<br>      {<br>            if(s[i] == s[i-1])<br>                  s.erase(s.begin() + i);<br>            else i++;<br>      }<br>}<br><br>ostream & operator << (ofstream &str,string &s)<br>{<br>int i, iLen = s.length();<br>for(i = 0; i < iLen; str<<s[i++]);<br>return str;<br>}<br><br>istream & operator >> (ifstream &str,string &s)<br>{<br>char c; bool fl = true;<br>while(fl)<br>{<br>cin>>c;<br>if(c=='\n') fl = false;<br>else s+=c;<br>}<br><br>return str;<br>}<br>

Сообщение отредактировано: experimenter - 07.07.03, 05:32

Цитата Experimenter, 07.07.03, 09:31:28

эту задачу я решил, наконец-то. решил без генерения.
идея такова. есть, например, перестановка aabc (самая первая).
от нее надо добраться до caba. чтобы добраться, надо сначала пройти все перестановки
a???, которых 3! = 6, потом
b???, которых 3!/2! = 3, потом
приходим к перестановке сaab. одну букву подобрали.
таким же макаром движемся от перестановки aab до aba, суммируя перестановки на каждом шаге.
алгоритм и программа рабочие. работает очень быстро.

вот код на С++

Ты совершил одну очень большую ошибку о которой я предупреждал Кстати, код какой-то получился до боли знакомый 8D И советую всю математику перевести на работу со строчным представлением цифр, факториал: - вещь страшная

Цитата SVK, 07.07.03, 10:27:15

Ты совершил одну очень большую ошибку о которой я предупреждал Кстати, код какой-то получился до боли знакомый 8D И советую всю математику перевести на работу со строчным представлением цифр, факториал: - вещь страшная

код писал сам. факториал - вещь нормальная. программу, которая подсчитывает перстановками, я написал, но, чтобы получить ответ от нее, тебе придется ждать до пенсии, в то время как выше написанной потребуется сотые доли секунды.
например, чтобы определить номер последней перестановки из 12 разных букв той проге придется проделать 12! = 479'001'600 итераций. чуешь? или еще нет?
так вот обычно проги работают терпимо при кол-ве операций около максимум 10 мил., а тут их почти 500, так что временной тест твоя идея никакой не проходит.
вообще программа написана как олимпиадная задача и оттестирована роботом вот здесь
http://acm.uva.es/board/index.php, так что все вопросы к нему, если тебе кажется что-то неправильно. и потом, как тебе что-то знакомо, если ты 4 года прогу не видел, алгоритм забыл, а тут тебе показывают прогу, да еще не твою, а ты говоришь, что-де она похожа на твою, 4х-годичной давности? только не говори, что ты имел ввиду, что она похожа на прогу, которую твой сосед написал или ты видел её в инете, ну, я думаю, ты понимаешь почему? ;D
зы
блин, я весь пост просмотрел и не нашел ни одного твоего предуприждения на счет какой-либо ошибки.  

Сообщение отредактировано: experimenter - 07.07.03, 09:58

Цитата Experimenter, 07.07.03, 13:45:13

код писал сам.

Никаких притензий

Цитата Experimenter, 07.07.03, 13:45:13

факториал - вещь нормальная.

Я имел в виду, что при больших (даже не очень) перестановках, его значение вылезет за разрядную сетку long double.

Цитата Experimenter, 07.07.03, 13:45:13

программу, которая подсчитывает перстановками, я написал, но, чтобы получить ответ от нее, тебе придется ждать до пенсии, в то время как выше написанной потребуется сотые доли секунды.

Не совсем тебя понял, и вообще, пока ты его еще не забыл - освети подробно, но сжато и формулизировано принцип алгоритма, если не жалко. (Кстати, он обратим?)

Цитата Experimenter, 07.07.03, 13:45:13

вообще программа написана как олимпиадная задача и оттестирована роботом вот здесь http://acm.uva.es/board/index.php

Какая то 'размытая' ссылка, нельзяль по подробнее.

Цитата Experimenter, 07.07.03, 13:45:13

и потом, как тебе что-то знакомо, если ты 4 года прогу не видел, алгоритм забыл, а тут тебе показывают прогу, да еще не твою, а ты говоришь, что-де она похожа на твою, 4х-годичной давности?

У меня феноминальная память на 'лица' 8D Кстати я этого (она похожа на твою) не говорил

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

<br>#include <fstream><br>#include <iostream><br>#include <string><br>#include <algorithm><br>#include <iomanip><br><br>using namespace std;<br><br>// global variables<br>unsigned long  counter = 0;<br>bool fl             = false;<br>string StrToFind;<br><br>// function defenitions<br>ostream & operator << (ofstream &str,string &s);<br>istream & operator >> (ifstream &str,string &s);<br>void GivePermNum(string a,string b);<br>int main();<br><br><br>int main()<br>{<br>string s;<br><br>while(true)<br>{<br>cin>>StrToFind;<br>if((string)"#" == StrToFind) break;<br>else<br>{<br>      s = StrToFind;<br>      sort(s.begin(),s.end());<br><br>      fl = true;<br>      counter = 0;<br>      GivePermNum(s,(string)"");<br>      cout.setf(ios::right);<br>      cout<<setw(10)<<(counter + 1)<<endl;<br>}<br><br>}<br><br>return 0;<br>}<br><br>void GivePermNum(string a,string b)<br>{<br>char last = 0;<br>int  i        = 0;<br>string s;<br><br>      if(0 == a.length())      <br>      {<br>            if(StrToFind == b)<br>                  fl = false;<br>            else<br>                  counter++;<br><br>            return;<br>      }<br><br>      else<br>      {<br>            int iLen = a.length();<br>            for(i = 0; i < iLen && fl; i++)<br>            {<br>                  if (last != a[i])<br>                  {<br>                        last = a[i];<br>                        s       = a;<br>                        s.erase(s.begin() + i);<br>                        GivePermNum(s,b + last);<br>                  }<br><br>            }<br>      }<br>}<br><br>ostream & operator << (ofstream &str,string &s)<br>{<br>int i, iLen = s.length();<br>for(i = 0; i < iLen; str<<s[i++]);<br>return str;<br>}<br><br>istream & operator >> (ifstream &str,string &s)<br>{<br>char c; bool fl = true;<br>while(fl)<br>{<br>cin>>c;<br>if(c=='\n') fl = false;<br>else s+=c;<br>}<br><br>return str;<br>}<br><br>

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

Сообщение отредактировано: experimenter - 07.07.03, 13:48

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

#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;
}

Сообщение отредактировано: SVK - 25.05.07, 10:49

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

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