B. Heapov algoritem

Iz MaFiRaWiki

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

Kaj pomeni to opozorilo?

B.Heapov algoritem (generiranje permutacij)

B.Heapov algoritem:

    1. Zgeneriramo vse permutacije elementov P(1),P(2),...,P(n-1).
    2. Zamenjamo P(n)-ti element z enim izmed elementov
      P(1),P(2),...,P(n-1).
    3. Zamenjavo izvršimo po sledečem kriteriju:
      • če je n liho število, potem menjamo števili P(1) in P(n)
      • če je n sodo število, potem menjamo števili P(k) in P(n), kjer k teče od 1 do n.
    4. Vrnemo se k prvi točki in stvar n-krat ponovimo.

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

V našem primeru imamo podano vhodno tabelo v obliki

1 2 3

Poglejmo, kaj se zgodi na k-tem koraku.

k=2;

1 2 3
2 1 3

k=1;

3 1 2
1 3 2

k=0;

2 3 1
3 2 1

Glej tudi

Osebna orodja