/******************************************************************************
 *  Compilation:  javac Shuffle.java
 *  Execution:    java Shuffle < california-gov.txt
 *  Dependencies: StdIn.java
 *
 *  Reads in all lines of text from standard input, shuffles them,
 *  and print them in random order.
 *  Uses Knuth's shuffling shuffle.
 *
 *  The file california-gov.txt contains a list of the 135
 *  candidates in the October 7, 2003 California governor's runoff
 *  election. The file cards.txt contains a list of 52 playing cards.
 *
 *
 *  % java Shuffle < california-gov.txt
 *  Randall D. Sprague
 *  Cheryl Bly-Chester
 *  Cruz M. Bustamante
 *  Darrin H. Scheidle
 *  Badi Badiozamani
 *  ...
 *
 *  % java Shuffle < cards.txt
 *  Four_of_Spades
 *  Deuce_of_Spades
 *  King_of_Spades
 *  Ace_of_Diamonds
 *  ...
 *
 ******************************************************************************/

public class Shuffle {

    // swaps array elements i and j
    public static void exch(String[] a, int i, int j) {
        String swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    // take as input an array of strings and rearrange them in random order
    public static void shuffle(String[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            int r = i + (int) (Math.random() * (n-i));   // between i and n-1
            exch(a, i, r);
        }
    }

    // take as input an array of strings and print them out to standard output
    public static void show(String[] a) {
        for (int i = 0; i < a.length; i++) {
            StdOut.println(a[i]);
        }
    }


    public static void main(String[] args) {
        // read all lines from standard input
        String[] a = StdIn.readAllLines();

        // shuffle array and print permutation
        shuffle(a);
        show(a);

        StdOut.println();

        // do it again
        shuffle(a);
        show(a);

    }
}