// Permutation.java SJ

import java.util.Random;
import java.util.Iterator;

/**
  * Apuluokka permutaatioiden generoimiseen
  */
public class Permutation 
    implements Iterable<int[]>
{
    static private Integer seed = 1;
    private int N = 2;
    private Random rnd;

    /**
      * n kokoisten permutaatioiden luominen
      */
    Permutation(int n) {
        N = n;
        seed = n;
        rnd = new Random(seed);
    }

    /**
      * satunnaislukujen alustaminen
      * siemen 0 antaa satunnaisena aina lineaarisen järjestyksen
      */
    Permutation(int n, int s) {
        N = n;
        seed = s;
        rnd = new Random(seed);
    }

    /** 
      * iteraattori kaikkien permutaatioiden läpikäymiseksi
      * next() palauttaa viitteen int[n] taulukkoon
      */
    public Iterator<int[]> iterator() {
        return new PermIter();
    }

    /**
      * satunnainen permutaatio kokoa N (annettu konstruktorissa)
      */
    public int[] randomPermutation() {
        return randomPermutation(N);
    }


    /**
      * satunnainen permutaatio kokoa n, siemen s
      * siemen 0 antaa satunnaisena aina lineaarisen järjestyksen
      */
    public int[] randomPermutation(int n, int s) {
        seed = s;
        rnd = new Random(seed);
        return randomPermutation(n);
    }

    /**
      * satunnainen permutaatio kokoa n
      */
    public int[] randomPermutation(int n) {
        int[] p = new int[n];

        // siemenellä 0 annetaan lineaarinen järjestys
        // tätä voi käyttää testailuhin
        if (seed == 0) {
            for (int i = 0 ; i < n; i++)
                p[i] = i;
            return p;
        }

        // kaikki paikat käyttämättömäksi
        for (int i = 0 ; i < n; i++)
            p[i] = -1;

        // kullekin paikalle satunnainen arvo
        for (int i = 0 ; i < n; i++) {
            // haetaan seuraava vapaa satunnaisesta alkukohdasta alkaen
            int r = rnd.nextInt(n);
            while (true) {  // jotain pitäisi kyllä löytyä
                if (p[r] == -1) {
                    p[r] = i;
                    break;
                }
                r = (r+1) % n;
            }
        }

        return p;

    } // randomPermutation()

    /**
      * iteraattorin toteutus
      */
    private class PermIter implements Iterator<int[]> {

        int[] result;
        int count;
        
        public PermIter() {
            result = null;
            // lasketaan lukumäärä N! lopetusehtoa varten
            count = 1;
            for (int i = 2; i <= N; i++)
                count *= i;
        }

        public boolean hasNext() {
            return count > 0;
        }

        // permutaatio kokeilemalla kullekin paikalle lopusta alkaen uusia
        // arvoja
        // O(N^2)
        public int[] next() {
            count--;
            if (result == null) {
                // ensimmäinen permutaatio erikoistapauksena
                result = new int[N];
                for (int i = 0; i < N; i++)
                    result[i] = i;
                return result;
            }

            int c = N-2;
            startpos:
            while (c >= 0) {
                nextitem:
                // haetaan josko kohtaan c löytyisi uusi alkio
                for (int i = result[c] + 1; i < N; i++) {
                    for (int j = 0; j < c; j++) {
                        if (i == result[j])
                            continue nextitem;
                    }
                    // uusi alkio löytyi paikkaan c
                    result[c] = i;

                    // loput paikalleen minimiarvoisina
                    pos:
                    for (int k = c+1; k < N; k++) {
                        // tämän voi tehdä toisinkin, muttei juuri nopeuta
                        cand:
                        for (int l = 0; l < N; l++) {
                            for (int m = 0; m < k; m++)
                                if (result[m] == l)
                                    continue cand;
                            result[k] = l;
                            continue pos;
                        }
                    }
                    break startpos;
                }
                c--;
            }
            return result;

        }

        public void remove() {
        }


    }   // class PermIter




} // class Permutation