[C++] Permutacje

[adambak]

Witam!
Mam takie zadanie:
Napisz program, który dla zbioru n-elementowego podanego z zewnątrz wypisze wszystkie jego permutacje. Funkcji rekurencyjnej przekazujemy jako argumenty tablicę oraz indeks elementu, tak ma wyglądać prototyp funkcji:

void permutacje (int T[4], int index);
W odwołaniu rekurencyjnym funkcja wywołuje się z indeksem o 1 większym. To cała treść z podręcznika.

i właśnie z tym jest problem, bo znam algorytm iteracyjny na wypisywanie wszystkich permutacji zbioru (oczywiście w kolejności leksykograficznej), ale mam narzucony tutaj sposób w jaki to mam zrobić, a ja koniecznie chcę to tak zrobić. Mimo że zadanie nie obowiązywało mnie w szkole (jest w podręczniku ale nauczyciel pominął - są podejrzenia że dlatego że za trudne). Bardzo mi zależy na tym, aby lepiej pojąć rekurencję. Pomoże ktoś?

[Fibik]

Tam ma być chyba nie 4, ale N - liczba elementów.

Kod: Zaznacz cały

#define N  4
inline void swap(int &a, int &b)
{ int c = a; a = b; b = c; }

void out(int T[])
{ 
   for(int i = 0; i < N; i++) cout << T[i]; // 1234 bez rozdzielania...
   cout < endl; // nowa linia;
}

void permutacje (int T[N], int ix) // ix = 0..N-1
{
  if( ix < N-1 ) 
  { 
    for(int i = ix; i < N; i++)
    {
      swap(T[ix], T[i]); // zamienia dwa elementy miejscami
      permutacje(T, ix+1);
      swap(T[ix], T[i]); // przywracamy
    }
  }
  else out(T); // drukujemy wszystkie elementy

}

wypełniamy tablicę, np.: T = {1,2,3,4};
i ciach:
permutacje(T, 0);

Nie sprawdzałem czy to działa...

[adambak]

Działa i to jak! Jest przepięknie, dokładnie o to mi chodziło Zabieram się za analizowanie. Bardzo, ale to bardzo dziękuję!-- 16 lut 2011, o 23:44 --Jednak jeszcze pomęczę... Koniec końców napisałem coś takiego:

Kod: Zaznacz cały

#include <iostream>

using namespace std;

inline void swap(int &a, int &b)
{ int c = a; a = b; b = c; }

void out(char T[], int N)
{
   for(int i = 0; i < N; i++) printf("%c", T[i]); 
   printf("
"); 
}

void permutacje (char T[], int ix, int N) 
{
  if( ix < N-1 )
  {
    for(int i = ix; i < N; i++)
    {
      swap(T[ix], T[i]); 
      permutacje(T, ix+1, N);
      swap(T[ix], T[i]); 
    }
  }
  else out(T, N); 
}

int main()
{
  int N,t;
  scanf("%d", &t);
  while(t--)
  {
    scanf("%d", &N);
    char T[N];
    
    //tworze tablice pierwszych N liczb alfabetu, to dla nich bede wypisywal permutacje
    for(int i=0; i<N; i++)
    {
      T[i]=97+i;
    }
    permutacje(T, 0, N);
  }
  
  cout<<endl;  
  system("pause");
  return 0;
}

jednak dla N=3 odpowiednio tworzy tablicę T={a,b,c}, ale wynikiem jest:
abc
acb
bac
bca
cba
cab

czyli końcówka (cba, cab) nie jest w kolejności leksykograficznej.. Jak to naprawić?

[Fibik]

A dla 4 jak wychodzi?
Pewnie trzeba jechać od tyłu po tej tablicy, to znaczy zamieniać najpierw ostatni z przedostatnim, itd.

[adambak]

Z 4 było tak samo.. Wypisywał np 1432, 1423. Czyli czy to jest alfabet czy nie, efekt ten sam. Pozostanę już przy alfabecie (bo tak mam w specyfikacji zadanka). Widocznie drobny błąd jest gdzie indziej.

Zamieniłem:

Kod: Zaznacz cały

void permutacje (char T[], int ix, int N) 
{
  if( ix < N-1 )
  {
    for(int i = ix; i < N; i++)
    {
      swap(T[ix], T[i]); 
      permutacje(T, ix+1, N);
      swap(T[ix], T[i]); 
    }
  }
  else out(T, N); 
}

na:

Kod: Zaznacz cały

void permutacje (char T[], int ix, int N) 
{
  if( ix < N-1 )
  {
    for(int i = N-1; i >= ix; i--)
    {
      swap(T[ix], T[i]); 
      permutacje(T, ix+1, N);
      swap(T[ix], T[i]); 
    }
  }
  else 
  {
    out(T, N);
  } 
}

i teraz dla N=3 (tworzy tablicę T={a,b,c}) wypisuje:
cab
cba
bca
bac
acb
abc

czyli dokładnie to o co mi chodzi... tylko na odwrót Czyli teraz jakoś pokombinować aby on ten stos tworzył na odwrót? Tędy droga? Bo kolejność jest jaka być powinna, tylko od tyłu. Wystarczy zamienić kolejność i będzie leksykograficznie..

[EDIT]: co ja wygaduję, też jest źle..

[Xitami]

sprawdzone

Kod: Zaznacz cały

void init(){  //by zacząć od pierwszej Value[i]<Value[i+1]
        int i;
        for(i=0; i<N; i++)
                Value[i]=i;
}

void swap(int a, int b){
        unsigned char t;
        t=Value[a]; Value[a]=Value[b]; Value[b]=t;
}
 
void getNext() {
  int i = N - 1;
  while (Value[i-1] >= Value[i]) i = i-1;
  int j = N;
  while (Value[j-1] <= Value[i-1]) j = j-1;
  swap(i-1, j-1);    
  i++; j = N;
  while (i < j)  {
    swap(i-1, j-1);
    i++;
    j--;
  }
}

[adambak]

Tak, dziękuję, ale znam ten algorytm Moim problemem jest to że koniecznie chcę to zrobić rekurencyjnie(patrz początek tematu). W dodatku mam narzucony prototyp funkcji: void permutacje (int T[4], int index);

Może i jestem nudny i powinna mi wystarczyć iteracja, ale skoro takie zadanko znalazłem w podręczniku a mam wciąż problemy z rekurencją to chcę to zrobić rekurencyjnie dla przećwiczenia

[Fibik]

Tam chodzi o to, że musimy przekazywać do permutacja() 'posortowane' od tego ix do końca.

ix = 0; potem wywołuje w tej pętli i = ix do N-1:
i = 0: a|bcd, dobrze, bo bcd jest posortowane;
i = 1: b|acd, tu też ok - acd jest w dobrej kolejności,
i = 2: c|bad, źle, powinno być c|abd
i = 3: d|bca - też źle...

dla i > 1 jest nieprawidłowa kolejność, bo ta jedynka ma być zawsze druga, a nie gdzieś dalej.

zatem trzeba zmienić fragment w pętli:

Kod: Zaznacz cały

void permutacje (char T[], int ix, int n)
{
  if( ix < n-1 )
  {
    for(int i = ix; i < n; i++)
    {
      swap(T[ix], T[i]);
      permutacje(T, ix+1, n);    
    }

   // przywracamy porządek;sytuacja jest taka: n|123...n-1, a ma być 1234...n,
   // czyli przesuwamy wszystko o 1 do przodu, a ten pierwszy na koniec

    char c = T[ix]; 
    for(int i = ix; i < n-1; i++) T[i] = T[i+1];
    T[n-1] = c; // można to przerobić na funkcję, a tu tylko ciach: move(T, ix, n)
  }
  else out(T, N);
}

ten swap też chyba musisz poprawić - char nie int, bo używasz teraz tablicy char *T, czyli zwyczajny ciąg znaków, a nie liczby int.

[adambak]

Super! Teraz wszystko idealnie działa i w dodatku zaczynam rozumieć ideę. Bardzo dziękuję