Generiranje permutacij

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Cilj algoritma je, da izpišemo vse permutacije števil (1,2,...,n) s pomočjo tabele in sicer tako, da v tabeli dolžine n generiramo permutacijo in jo izpišemo. Splošna metoda:

  • Kako poiščemo vse permutacije n števil (znakov)?
    1. Izberemo poljuben znak v danem nizu.
    2. Naredimo vse permutacije preostalih znakov v nizu, teh je n-1. To storimo tako, kot smostorili pri n znakih. Izberemo enega, ga "izločimo" in naredimo vse permutacije n-2 znakov.
    3. Vrnemo se k prvi točki.

Naš algoritem

  • Naš algoritem deluje po podobnem principu:
    1. Naš prvi znak je vedno število 1, ki ga fiksiramo na k-tem mestu v tabeli Value.
    2. Nato poiščemo vse permutacije preostalih števil (2,3,...,n), teh je n-1. Te poiščemo tako, kot v splošnem primeru, le da si število ne izberemo poljubno, ampak se ta izbirajo po vrstnem redu od najmanjšega do največjega, indeks fiksiranja števila pa je prvo mesto v tabeli Value, ki je še "prazno", seveda gledamo z začetka tabele.
    3. Torej si na drugem koraku izberemo število 2 in naredimo vse permutacije preostalih elementov, teh je n-2.
    4. Ponavljamo.


Sam algoritem moramo klicati n-krat, da dobimo vse permutacije.

  1. public class Permutacije{
  2. static int n=3;
  3. static int[] Value= new int[n];
  4. static int s=0;
  5.  
  6. public static void main(String[] args) throws Exception{
  7. for(int k=0; k<n; k++){
  8. visit(k);
  9. }
  10. }
  11.  
  12.  
  13. public static void visit(int k){
  14. s = s+1;
  15. Value[k] = s;
  16. if (s == n) {
  17. for(int j=0; j<n; j++){
  18. System.out.print(Value[j]+" ");
  19. }
  20. System.out.println();
  21. }
  22.  
  23. else{
  24. for (int i = 0; i < n; i++){
  25. if (Value[i] == 0)
  26. visit(i);
  27. }
  28. }
  29. s = s-1;
  30. Value[k] = 0;
  31. }
  32. }

V našem primeru imamo n=3, torej permutiramo števila (1,2,3) in imamo 3!=6 permutacij. Poglejmo, kako se po zgornji kodi generirajo permutacije.

k=0;

1 2 3
1 3 2

k=1;

2 1 3
3 1 2

k=2;

2 3 1
3 2 1

Glej tudi

Osebna orodja