import stdlib.StdRandom;

public class Permute {

    // permute1() returns a random permutation of the integers
    // 0..N-1, using the algorithm described in Section 1.4 to
    // shuffle a deck of cards

    public static int [] permute1 (int n) {
        int [] a = new int [n];
        for (int i = 0; i < n; i++) {
            a[i] = i;
        }

        for (int i = 0; i < n; i++) {
            int r = i + (int) (Math.random() * (n - i));
            int t = a[i];
            a[i] = a[r];
            a[r] = t;
        }
        return a;
    }

    // permute2() returns a random permutation of the integers
    // 0..N-1, using an algorithm described in another textbook
    // (see code listing in problem statement of Exercise 4.1.17)

    public static int [] permute2 (int n) {
        int [] a = new int [n];
        boolean [] taken = new boolean [n];
        int count = 0;
        while (count < n) {
            int r = StdRandom.uniform(n);
            if (!taken[r]) {
                a[r] = count;
                taken[r] = true;
                count++;
            }
        }
        return a;
    }
}