Informatika gyűjtemény

Egy szinttel feljebb Langford2.java

2004050607080910

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

<<  Langford permutációk  >>

NézetNyomtat

Langford2.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: 3 KB
package hu.krivan.szakkor;

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

    private int n;
    private int[] perm;
    private int[] idx;
    private int found = 0;
    private int p;
    
    private int[] db;
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Langford l = new Langford( 16 );
        l.generate();
    }

    private Langford(int p) {
        this.p = p;
        n = p*2;
        perm = new int[p*2];
        for( int i=0; i<perm.length; i++ ) {
            perm[i] = 0;
        }
        
        idx = new int[p]; // csak p darabnyi kell!
        db = new int[p];
        
        for( int i=0; i<p; i++ ) {
            db[i] = 0;
        }
    }

    private void generate() {
        int i = 0;
        // elkezdjük feltölteni a perm-et.
        while( i >= 0 && i <= n )
        {
            if( stillGood( i ) )
            {
                if( i == n ) {
                    // jók vagyunk, de már túllógunk a tömbön
                    // ne legyünk mohók, hova akarunk még pakolni, ha már ez egy teljes langford permutáció? :)
                    found++;
                    
                    // visszalépünk
                    i--;
                } else
                if( perm[i] < p ) {
                    // ha még fér ide egy nagyobbik szám akkor rakunk.
                    if( perm[i] != 0 ) db[ perm[i]-1 ]--; // először az ott lévő szám darabszámát csökkentjük
                    do { // elkezdjük növelgetni a számot, ameddig kell (ha 2 van belőle, akkor megyünk tovább)
                        perm[i]++;
                        if( perm[i] > p ) break;
                    } while( db[perm[i]-1] == 2 );
                    // vagy sikerült betenni számot, vagy nem.
                    if( perm[i] > p ) {
                        // nem tudunk az adott helyre tenni semmi újat, akkor visszalépünk
                        perm[i] = 0; // töröljük a permutációból a számot
                        i--; // visszalépünk
                    } else {
                        // sikeresen pakoltunk a helyre
                        db[ perm[i]-1 ]++; // növeljük a darabszámot
                        i++; // továbblépünk
                    }
                } else {
                    // nem tehető ide nagyobb szám, mert ez a maximum.
                    db[ perm[i]-1 ]--; // csökkentjük a darabszámot
                    perm[i] = 0; // töröljük a permutációból a számot
                    i--; // visszalépünk
                }
            } else {
                // nem lehet ebből langfordot összehozni, ne szenvedjünk
                i--; // visszalépünk
            }
        }
        // végig jártuk az utunkat.
        System.out.println(found/2); // mindent 2x számoltunk, ezért csak a felét írjuk ki.
    }

    private boolean stillGood(int b) {
        // kérdés, hogy az első b elem eddig jó-e?
        
        // itt van egy permutációnk amit vizsgálnunk kell.
        boolean cool = true;
        for( int i=0; i<p; i++ ) {
            idx[i] = -1;
        }
        
        for(int i=0; i<b; i++) {
            // megyünk végig a számokon, de csak b-ig, ameddig okés a dolog
            if( idx[ perm[i]-1 ] == -1 ) {
                idx[ perm[i]-1 ] = i;
            } else {
                // olyan számot találunk, ami már volt egyszer.
                // idx különbség:
                if( ( i-idx[ perm[i]-1 ]-1 ) == perm[i] ) {
                    // rendben vagyunk
                } else {
                    cool = false;
                    break;
                }
            }
        }
        
        // mégjobban gyorsítunk
        if( cool ) {
            // ha azt hinnénk, hogy jó, akkor lehet hogy még kéne valamit ellenőrizni:
            for(int i=0; i<b; i++) {
                if( perm[i] == 0 ) break; // ha 0 van, akkor már nincs utána szám, nem szenvedünk
                
                // 1. eset. A szám első példánya olyan helyen van, hogy a második példány már túllogna a tartományon
                if( (i+perm[i]+1 >= n) && (idx[perm[i]-1] == i) ) {
                    // ha találunk egy olyan számot, amitől "szám" távolságnyira nem lehet elem (kilóg a tömbből)
                    // és ő lenne az első szám, akkor az nem jó
                    cool = false;
                    break;
                } else {
                    // 2. eset. Az első szám olyan, hogy számnyi távolság után (a vizsgálandó tartományon belül), már van egy szám, ami nem a szám második példánya
                    if( (i+perm[i]+1 < b) && (idx[perm[i]-1] == i) && (perm[i+perm[i]+1] != 0) && (perm[i+perm[i]+1] != perm[i]) ) {
                        cool = false;
                        break;
                    }
                }
            }
        }
        
        return cool;
    }

}
(Vissza)