Informatika gyűjtemény

Egy szinttel feljebb Langford0.java

2004050607080910

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

<<  Langford permutációk  >>

NézetNyomtat

Langford0.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 BruteLangford {

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

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

    private void generate() {
        int j, m, k;
        
        while( true ) {
            handle();
            
            j = n - 2; // hátulról kolbászolunk előre (azért -2, mert -1 lenne az utolsó elem, de nekünk az utolsó előtti kell.)
            while( perm[j] >= perm[j+1] ) {
                j--;
                if( j == -1 ) break; // különben exception.
            }
            if( j == -1) break; // nem találtunk cserélni valót.
            
            // j. szerepében megvan az első olyan elem, amelynél van nagyobb tőle jobbra.
            
            m = n-1; // megint hátulról kolbászolunk előre és megkeressük az első olyan elemet, amely nagyobb j.-nél
            while( perm[j] >= perm[m] ) {
                m--;
                if( m == -1 ) break; // lehet ilyen?
            }
            
            swap( j, m ); // kicseréljük a két fekete bárányt.
            
            k = j+1;
            m = n-1;
            
            // (j+1; n) intervallumban minden elemet felcserélünk
            while( k < m ) {
                swap( k++, m-- );
            }
        }
        
        System.out.println(found/2);
    }

    private void handle() {
        // 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<n; i++) {
            // megyünk végig a számokon, eltároljuk mindegyik számról, hogy hol találtuk legelőször
            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, mert pont annyi a távolság köztük amennyi a szám
                } else {
                    // nincs rendben, ez nem langford permutáció
                    cool = false;
                    break;
                }
            }
        }
        
        if( cool ) found++; // számláljuk ha megfelelő.
    }

    private void swap(int j, int m) {
        int tmp = perm[j];
        perm[j] = perm[m];
        perm[m] = tmp;
    }

}
(Vissza)