Új hozzászólás Aktív témák

• #15584 kovisoft őstag pmonitor #15582

  Új Válasz 2021-02-26 15:53:23 #15584

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  kovisoft

  őstag

  válasz pmonitor #15582 üzenetére

  Még régebben írtam egy rövid függvényt, ami kiírja a N szám permutációit rendezett formában. Most sehol sem találom, de emlékeim alapján megpróbáltam újra lekódolni C-ben:

  int a[50];
int n=5;
int i, j, temp;

// az 1 2 3 ... n sorozatbol indulunk ki
for (i=0; i<n; i++)
a[i] = i+1;

for (;;)
{
// kiirjuk az aktualis permutaciot
for (i=0; i<n; i++)
printf("%d ", a[i]);
printf("\n");

// megkeressuk, hol kezdodik az utolso monoton csokkeno reszsorozat
for (i=n-2; i>=0 && a[i]>a[i+1]; i--);

// ha a teljes sorozat monoton csokkeno, akkor vegeztunk
if (i < 0)
break;

// a csokkeno reszsorozat elotti elemet ki kell cserelnunk a reszsorozatban nagysag szerint rakovetkezovel
for (j=n-1; a[j]<a[i]; j--);
temp=a[i]; a[i]=a[j]; a[j]=temp;

// tovabbra is monoton csokkeno a reszsorozatunk, forditsuk meg, hogy monoton novekedo legyen
for (j=i+1; j<n+i-j; j++)
{
temp=a[j]; a[j]=a[n+i-j]; a[n+i-j]=temp;
}
}

  Nem teszteltem a sebességét, nem állítom, hogy ez a létező leggyorsabb módszer, de viszonylag rövid és egyszerű. Egyébként most, hogy jobban megnézem, ez majdnem az a módszer, mint amiben a quicksort van. Az igazat megvallva soha nem értettem, hogy miért kell itt meghívni egy quicksortot, hiszen amikor ide érünk, akkor a sorozat vége már rendezve van, csak éppen csökkenő sorrendben, tehát elég szimplán megfordítani.

Új hozzászólás Aktív témák