Permutacje

/* PermutacjeGT.java */

public class PermutacjeGT
{
  static final int N = 3; // permutacje n-elementowe
  private static int[] p = new int[N];
  
  public static void main(String[] args)
  {
    generuj(0);
  }
  
  static boolean nieMa(int wyraz, int indeks)
  {
    for (int k = 0; k < indeks; k++)
      if (p[k] == wyraz) return false;

    return true;
  }
  
  static void generuj(int i)
  {
    if (i == N)
    {
      for (int k = 0; k < p.length; k++)
        System.out.print(p[k] + " ");

      System.out.println();
    }
    else
    {
      for (int j = 1; j <= N; j++)
      {
        if (nieMa(j,i))
        {
          p[i] = j;
          generuj(i+1);
        }
      }
    }
  }
}

/*
static boolean nieMa(int wyraz, int indeks)

Metoda nieMa sprawdza, czy wsród elementów o numerach mniejszych od
indeks nie ma elementu o wartosci wyraz. Jesli element o wartosci wyraz
wystepuje wsród elementów o numerach mniejszych od indeks, to metod nieMa
zwraca wartosc false. Jesli element o wartosci wyraz nie wystepuje wsród
elementów o numerach mniejszych od indeks, to metoda nieMa zwraca wartosc
true.

Przyklad:

      0  1  2
p -> [3][2][x]

nieMa(1,2) = true
nieMa(2,2) = false
nieMa(3,2) = false


static void generuj(int i)

Metoda generuj okresla dla i-tego wyrazu permutacji wartosc j z przedzialu
od 1 do N, o ile wartosci j nie ma wsród wyrazów o indeksach mniejszych od i,
a nastepnie przeprowadza te operacje dla kolejnego i+1 wyrazu permutacji.
Przy czym, wywolanie metody generuj z parametrem aktualnym i probuje okreslic
dla i-tego wyrazu permutacji wszystkie dozwolone wartosci j po kolei. Jesli
metoda generuj zostanie wywolana z parametrem aktualnym N, to na ekranie
zostanie wypisana wygenerowana permutacja.

Graf permutacji dla N = 3

         __________ empty __________
        /             |             \
       /              |              \
      1               2               3         i = 0
     / \             / \             / \
    /   \           /   \           /   \
 1,2     1,3     2,1     2,3     3,1     3,2    i = 1
  |       |       |       |       |       |
  |       |       |       |       |       |
1,2,3   1,3,2   2,1,3   2,3,1   3,1,2   3,2,1   i = 2


public static void main(String[] args)

Generowanie permutacji rozpoczynamy od wyrazu z indeksem 0.
*/

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Press any key to continue...

Strona główna