Informatika gyűjtemény

Egy szinttel feljebb Langford3.java

2004050607080910

<<  2. óra - Permutáció  >>

<<  Langford permutációk  >>

NézetNyomtat

Langford3.java (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 2 KB
package hu.krivan.szakkor;

/**
 *
 * @author balint
 */
public class OptedLangford {

    private int p;
    private int n; // p*2
    
    private int[] perm;
    private int[] pos;
    
    private int found = 0;
    
    public static void main(String[] args) {
        OptedLangford l = new OptedLangford( 16 );
        l.count();
    }

    public OptedLangford(int p) {
        this.p = p;
        n = p*2;
        
        perm = new int[p*2];
        for( int i=0; i<perm.length; i++ ) {
            perm[i] = 0;
        }
        
        // itt tároljuk az adott szám, első előfordulásának idx-ét (a 2. ebből könnyen számolható)
        pos = new int[p];
        for( int i=0; i<p; i++ ) {
            pos[i] = 0;
        }
    }

    private void count() {
        int k = p;
        int i = 0;
        while( k > 0 ) {
            // keresünk egy helyet k-nak
            // akkor jó, a hely, ha a 2. elem is befér a tömbbe, illetve egyik helyen sem áll még szám
            while( (i+k+1) < n && !(perm[i] == 0 && perm[i+k+1] == 0) ) {
                i++;
            }
            if( i+k+1 == n ) {
                // ha túllógunk a tömbön, akkor ezt a számot nem tudjuk betenni.
                // tehát amit utoljára tettünk be k-t, az nem jó helyen van, őt pakoljuk át.
                k++;
                // az utoljára még sikeresen betett k-t, kivesszük, hogy újra betehessük egy kicsit arrébb (ezért i = régi index+1).
                // ha k=p-t, sem tudjuk betenni, akkor vége van.
                if( k <= p ) i = remove(k)+1; else break;
            } else {
                // semmi probléma, k-nak találtunk egy finom kis helyet
                perm[i] = k;
                perm[i+k+1] = k;
                // eltároljuk k előfordulásának 1. idx-ét, hogy könnyen ki tudjuk majd venni.
                pos[k-1] = i;
                
                k--; // kövi jön
                i=0; // előlről menjen a keresés.
                
                // ha az 1-est is betettük, akkor van egy teljes langford permutációnk
                if( k==0 ) {
                    // tükör vizsgálat
                    if( p % 2 == 1 ) {
                        if( pos[p-1] >= (p-1)/2  ) break;
                    } else {
                        if( (pos[p-1] > (p/2)-1) || ((pos[p-1] == (p/2)-1) && (pos[p-2] >= p/2)) ) break;                       
                    }
                    
                    found++;
                    // nyilván az 1-est 1 helyre tudjuk betenni, ha csak őt vesszük ki, akkor nincs újabb lehetőségünk
                    remove(1);
                    // tehát a 2-est is arébb kéne tenni, de neki sem lesz újabb jó helye
                    remove(2);
                    // tehát a 3-ast is kidobjuk, és őt próbáljuk arréb rakni.
                    i = remove(3)+1; // 3. utáni pozíciótól folytatjuk
                    k = 3; // 3-ast akarunk majd betenni
                }
            }
        }
        
        System.out.println(found);
    }

    /**
     * Kivesszük a permutációbol a <i>k</i> párt, és az első elem pozíciójával térünk vissza.
     * 
     * @param k
     * @return kivett pár első elemének indexe
     */
    private int remove(int k) {
        int i = pos[k-1];
        perm[i] = 0;
        perm[i+k+1] = 0;
        
        return i;
    }

}
(Vissza)