//  Copyright 2016 The Sawdust Open Source Project
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//

package array.shuffle;

import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Random;

/*
Write a method, shuffle(A), that rearranges the elements of array A so that every
possible ordering is equally likely. You may rely on the nextInt(n) method of
the java.util.Random class, which returns a random number between 0 and n−1
inclusive.
 */
public class Shuffle {
    static int[] shuffle(int[] a) {
        Random r = new Random();
        LinkedHashSet oldIndexesOrder = new LinkedHashSet(a.length);

        while (oldIndexesOrder.size() < a.length) {
            oldIndexesOrder.add(r.nextInt(a.length));
        }

        int[] re = new int[a.length];
        int index = 0;

        Iterator e = oldIndexesOrder.iterator();
        while (e.hasNext()) {
            re[index++] = a[(int) e.next()];
        }
        return re;
    }

    public static void main(String[] args) {
        int[] a = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.print(Arrays.toString(shuffle(a)));
    }
}

@@ -1017,16 +1017,127 @@
 uffle %7B%0A
+    /**%0A     *%0A     * @param a array%0A     * @return  shuffled array.  the input array is kept no touch%0A     */%0A
     stat
@@ -1602,24 +1602,650 @@
  re;%0A    %7D%0A%0A
+    static private void swap(int%5B%5D arr, int i, int j) %7B%0A        arr%5Bi%5D %5E= arr%5Bj%5D;%0A        arr%5Bj%5D %5E= arr%5Bi%5D;%0A        arr%5Bi%5D %5E= arr%5Bj%5D;%0A    %7D%0A%0A    /**%0A     * In iteration i, get a pseudorandom, uniformly distributed int value between 0 (inclusive)%0A     * and i (exclusive). Swap a%5Bi%5D and a%5Br%5D.%0A     *%0A     * @param a array.%0A     * @return updated array%0A     */%0A    static int%5B%5D shuffle2(int%5B%5D a) %7B%0A        Random r = new Random();%0A        for (int i = 1; i %3C a.length; i++) %7B%0A            int index = r.nextInt(i);%0A            if (index != i) %7B%0A                swap(a, index, i);%0A            %7D%0A        %7D%0A        return a;%0A    %7D%0A%0A
     public s
@@ -2361,16 +2361,18 @@
 ut.print
+ln
 (Arrays.
@@ -2390,20 +2390,78 @@
 uffle(a)));%0A
+        System.out.println(Arrays.toString(shuffle2(a)));%0A
     %7D%0A%7D%0A

Shuffle an array with pseudorandom number