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

• #15630 pmonitor aktív tag sztanozs #15629

  Új Válasz 2021-03-01 10:50:24 #15630

  Ú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

  

  pmonitor

  aktív tag

  válasz sztanozs #15629 üzenetére

  Ez a kód:
  static void Teszt_5(char[] arr)
{
char[] arr2 = (char[])arr.Clone();
int size = arr.Length;
QuickSort(arr2, 0, size - 1);
//Array.Sort(arr2);
int n = arr2.Length;
int i, j;
char temp;
//for (i = 0; i < n; ++i) arr2[i] = i + 1;
while (true)
{
// kiirjuk az aktualis permutaciot
/*for (i = 0; i < n; ++i) Console.Write("{0} ", arr2[i]);
Console.WriteLine("");*/

// megkeressuk, hol kezdodik az utolso monoton csokkeno reszsorozat
for (i = n - 2; i >= 0 && arr2[i] >= arr2[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; arr2[j] <= arr2[i]; --j) ;

temp = arr2[i]; arr2[i] = arr2[j]; arr2[j] = temp;

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

  Ennek a kódnak:
  static void IsmPermutacio(char[] tomb2, int[] N, int n, int[] W1, int s, int i)
{
int[] V = new int[n];
int[] W = new int[n];
CopyMemory(W, W1, (uint)(n * intSize));
//Array.Copy(W1, W, n);
if (i == 0)
{
for (int l = 0; l < s; ++l) W[l] = -1;
}
if (s != 0)
{
bool ind = true;
do
{
Kombinacio(V, s, N[i], ref ind);
if (!ind)
{
Betesz(N[i], n, V, W, i);
IsmPermutacio(tomb2, N, n, W, s - N[i], i + 1);
Kivesz(W, n, i);
}
} while (!ind);
}
else
{
Betesz(N[i], n, V, W, i);
//*****************************************************
/*for (int q = 0; q < n; ++q) Console.Write(tomb2[W[q]]);
Console.WriteLine("");*/
//*****************************************************
for (int l = 0; l < n; ++l) W[l] = -1;
}
}

static void Kombinacio(int[] V, int n, int k, ref bool ind)
{
if (ind)
{
for (int i = 0; i < k; ++i) V[i] = i;
ind = false;
return;
}
for (int i = k - 1; i > -1; --i)
{
if (V[i] < n - k + i)
{
++V[i];
for (int j = i + 1; j < k; ++j) V[j] = V[j - 1] + 1;
return;
}
}
ind = true;
}

static void Betesz(int ni, int n, int[] V, int[] W, int i)
{
int j = -1, l = 0;
for (int p = 0; p < ni; ++p)
{
while (l < n)
{
if (W[l] == -1) ++j;
if (j == V[p])
{
W[l] = i;
break;
}
++l;
}
}
}
static void Kivesz(int[] W, int n, int i)
{
for (int l = 0; l < n; ++l) if (W[l] == i) W[l] = -1;
}

  Nem az optimalizálása, hanem teljesen más(egyszerűbb) algoritmus.

  És sztem az első algoritmus érthetőbb is.

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