Generacja permutacji w porządku antyleksykograficznym

0

Witam,

Mam za zadanie napisać program generujący wszystkie permutacje zbioru {1,2,3,4,5} oraz wypisać ich łączną liczbę. Znalazłem w książce algorytm na ten problem zapisany w pseudokodzie i przepisałem go do C++, ale nie działa poprawnie, nie potrafię doszukać się błędu.

Kod celowo rozpisany dla zbioru {1,2,3}, żeby łatwiej było sprawdzać poprawność działania.

#include <iostream>


using namespace std;

int Tablica[3] = {1,2,3};
int i,j,x;


void odwroc(int m)
{
    i = 1;
    j = m;
    while(i < j) 
    {
        Tablica[i] = Tablica[j];
        i++;
        j--;
    };
}
void antylex(int m)
{
    if (m = 1){
        for (x=0;x<=2;x++){
        cout <<Tablica[x];
        };
        cout<<endl;
    }
    else{
        for (i=1;i<=m;i++){
            antylex(m-1);
                if(i < m){
                    Tablica [i] = Tablica [m];
                    odwroc(m-1);
                }
        }
    }
}

int main()
{
    int m=3;
    for(i=0;i<=2;i++){
        Tablica[i] = i;
        antylex(m);
    };
    getchar();
    return 0;    
};

Z góry dziękuje za pomoc.

0

Tak na pierwszy rzut oka:

 if (m = 1){
0

Ale niby tak ma być według algorytmu, chyba że ja źle go rozumiem.

Algorytm jest z książki "Kombinatoryka dla Informatyków" W. Lipski

Link do wycinka: http://tinypic.com/r/2qtlo29/6

0

= to:
a) w Pascalu/pseudokodzie operator porównania
b) w C++ operator przypisania

== to w C++ operator porównania.

0

Sprawdziłem jeszcze raz, poprawiłem co zauważyłem, żeby było dokładnie jak w pseudokodzie, ale dalej nie działa poprawnie. W czym problem?

#include <iostream>

using namespace std;

int Tablica[3] = {1,2,3};
int i,j,x;
int n=2;
int m=3;

void odwroc(int m)
{
	i = 1;
	j = m;
	while(i < j) 
	{
		Tablica[i] = Tablica[j];		
		i++;
		j--;
	};
}

void antylex(int m)
{
	if (m == 1){
		for (x=0;x<=n;x++){
		cout <<Tablica[n];
		};
		cout<<endl;
	}
	else{
		for (i=1;i<=m;i++){
			antylex(m-1);
				if(i < m){
					Tablica[i] = Tablica[m];					
					odwroc(m-1);
				}
		}
	}
}

int main()
{	
	for(i=1;i<=n;i++){
		Tablica[i] = i;
		antylex(n);
	};
	getchar();
	return 0;	
};
0
                for (x=0;x<=n;x++){
                cout <<Tablica[n];
                };

Hint: porównaj zmienną w pętli oraz fragment Tablica[n]

0

Zauważyłem to ułamek sekundy po tym jak napisałeś posta. Kombinowałem w kodzie i nie zmieniłem zmiennych. To jednak nie jest ostateczny problem, bo dalej nie działa jak powinno.

0

Problem może być też w tym, że tablice w C++ są numerowane od zera, nie jedynki.

0

Nie daje rady doszukać się, gdzie jest błąd. Mógłby mi je ktoś rozpisać? Poprawiłem numerację tablic i dalej nic z tego.

0

Masz przecież gotowca prev_permutation() http://www.cplusplus.com/reference/algorithm/prev_permutation/

0

Mam posłużyć się tą procedurą. Taki wymóg zadania.

1 użytkowników online, w tym zalogowanych: 0, gości: 1