Losowe tasowanie tablicy

Oto prosty sposób użycia ArrayList:

List<Integer> solution = new ArrayList<>();
for (int i = 1; i <= 6; i++) {
    solution.add(i);
}
Collections.shuffle(solution);

Oto działająca i wydajna funkcja tablicy shuffle Fishera–Yatesa:

private static void shuffleArray(int[] array)
{
    int index;
    Random random = new Random();
    for (int i = array.length - 1; i > 0; i--)
    {
        index = random.nextInt(i + 1);
        if (index != i)
        {
            array[index] ^= array[i];
            array[i] ^= array[index];
            array[index] ^= array[i];
        }
    }
}

Lub

private static void shuffleArray(int[] array)
{
    int index, temp;
    Random random = new Random();
    for (int i = array.length - 1; i > 0; i--)
    {
        index = random.nextInt(i + 1);
        temp = array[index];
        array[index] = array[i];
        array[i] = temp;
    }
}

Klasa Collections ma efektywną metodę tasowania, która może być kopiowana, tak aby nie zależała od niej:

/**
 * Usage:
 *    int[] array = {1, 2, 3};
 *    Util.shuffle(array);
 */
public class Util {

    private static Random random;

    /**
     * Code from method java.util.Collections.shuffle();
     */
    public static void shuffle(int[] array) {
        if (random == null) random = new Random();
        int count = array.length;
        for (int i = count; i > 1; i--) {
            swap(array, i - 1, random.nextInt(i));
        }
    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

Spójrz na Collections klasy, a konkretnie shuffle(...).

Oto kompletne rozwiązanie z wykorzystaniem podejścia Collections.shuffle:

public static void shuffleArray(int[] array) {
  List<Integer> list = new ArrayList<>();
  for (int i : array) {
    list.add(i);
  }

  Collections.shuffle(list);

  for (int i = 0; i < list.size(); i++) {
    array[i] = list.get(i);
  }    
}

Zauważ, że Java cierpi z powodu niemożności płynnego tłumaczenia pomiędzy int[] i Integer[] (a więc int[] i List<Integer>).

Masz kilka opcji. Lista jest nieco inna niż tablica, jeśli chodzi o tasowanie.

Jak widać poniżej, tablica jest szybsza niż lista, a prymitywna tablica jest szybsza niż tablica obiektów.

Czas Trwania Próby

List<Integer> Shuffle: 43133ns
    Integer[] Shuffle: 31884ns
        int[] Shuffle: 25377ns

Poniżej znajdują się trzy różne implementacje shuffle. Należy używać tylko kolekcji.Tasuj, jeśli masz do czynienia z kolekcją. Nie ma potrzeby owijania tablicy w kolekcję tylko po to, aby ją posortować. Na poniższe metody są bardzo proste do wdrożenia.

Klasa ShuffleUtil

import java.lang.reflect.Array;
import java.util.*;

public class ShuffleUtil<T> {
    private static final int[] EMPTY_INT_ARRAY = new int[0];
    private static final int SHUFFLE_THRESHOLD = 5;

    private static Random rand;

Główna Metoda

    public static void main(String[] args) {
        List<Integer> list = null;
        Integer[] arr = null;
        int[] iarr = null;

        long start = 0;
        int cycles = 1000;
        int n = 1000;

        // Shuffle List<Integer>
        start = System.nanoTime();
        list = range(n);
        for (int i = 0; i < cycles; i++) {
            ShuffleUtil.shuffle(list);
        }
        System.out.printf("%22s: %dns%n", "List<Integer> Shuffle", (System.nanoTime() - start) / cycles);

        // Shuffle Integer[]
        start = System.nanoTime();
        arr = toArray(list);
        for (int i = 0; i < cycles; i++) {
            ShuffleUtil.shuffle(arr);
        }
        System.out.printf("%22s: %dns%n", "Integer[] Shuffle", (System.nanoTime() - start) / cycles);

        // Shuffle int[]
        start = System.nanoTime();
        iarr = toPrimitive(arr);
        for (int i = 0; i < cycles; i++) {
            ShuffleUtil.shuffle(iarr);
        }
        System.out.printf("%22s: %dns%n", "int[] Shuffle", (System.nanoTime() - start) / cycles);
    }

Tasowanie listy rodzajowej

    // ================================================================
    // Shuffle List<T> (java.lang.Collections)
    // ================================================================
    @SuppressWarnings("unchecked")
    public static <T> void shuffle(List<T> list) {
        if (rand == null) {
            rand = new Random();
        }
        int size = list.size();
        if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
            for (int i = size; i > 1; i--) {
                swap(list, i - 1, rand.nextInt(i));
            }
        } else {
            Object arr[] = list.toArray();

            for (int i = size; i > 1; i--) {
                swap(arr, i - 1, rand.nextInt(i));
            }

            ListIterator<T> it = list.listIterator();
            int i = 0;

            while (it.hasNext()) {
                it.next();
                it.set((T) arr[i++]);
            }
        }
    }

    public static <T> void swap(List<T> list, int i, int j) {
        final List<T> l = list;
        l.set(i, l.set(j, l.get(i)));
    }

    public static <T> List<T> shuffled(List<T> list) {
        List<T> copy = copyList(list);
        shuffle(copy);
        return copy;
    }

Tasowanie tablicy generycznej

    // ================================================================
    // Shuffle T[]
    // ================================================================
    public static <T> void shuffle(T[] arr) {
        if (rand == null) {
            rand = new Random();
        }

        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, i, rand.nextInt(i + 1));
        }
    }

    public static <T> void swap(T[] arr, int i, int j) {
        T tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static <T> T[] shuffled(T[] arr) {
        T[] copy = Arrays.copyOf(arr, arr.length);
        shuffle(copy);
        return copy;
    }

Tasowanie prymitywnej tablicy

    // ================================================================
    // Shuffle int[]
    // ================================================================
    public static <T> void shuffle(int[] arr) {
        if (rand == null) {
            rand = new Random();
        }

        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, i, rand.nextInt(i + 1));
        }
    }

    public static <T> void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static int[] shuffled(int[] arr) {
        int[] copy = Arrays.copyOf(arr, arr.length);
        shuffle(copy);
        return copy;
    }

Metody Użytkowe

Proste narzędzia do kopiowania i konwertowania tablic na listy i odwrotnie.

    // ================================================================
    // Utility methods
    // ================================================================
    protected static <T> List<T> copyList(List<T> list) {
        List<T> copy = new ArrayList<T>(list.size());
        for (T item : list) {
            copy.add(item);
        }
        return copy;
    }

    protected static int[] toPrimitive(Integer[] array) {
        if (array == null) {
            return null;
        } else if (array.length == 0) {
            return EMPTY_INT_ARRAY;
        }
        final int[] result = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            result[i] = array[i].intValue();
        }
        return result;
    }

    protected static Integer[] toArray(List<Integer> list) {
        return toArray(list, Integer.class);
    }

    protected static <T> T[] toArray(List<T> list, Class<T> clazz) {
        @SuppressWarnings("unchecked")
        final T[] arr = list.toArray((T[]) Array.newInstance(clazz, list.size()));
        return arr;
    }

Range Class

Generuje zakres wartości, podobny do funkcji range Pythona.

    // ================================================================
    // Range class for generating a range of values.
    // ================================================================
    protected static List<Integer> range(int n) {
        return toList(new Range(n), new ArrayList<Integer>());
    }

    protected static <T> List<T> toList(Iterable<T> iterable) {
        return toList(iterable, new ArrayList<T>());
    }

    protected static <T> List<T> toList(Iterable<T> iterable, List<T> destination) {
        addAll(destination, iterable.iterator());

        return destination;
    }

    protected static <T> void addAll(Collection<T> collection, Iterator<T> iterator) {
        while (iterator.hasNext()) {
            collection.add(iterator.next());
        }
    }

    private static class Range implements Iterable<Integer> {
        private int start;
        private int stop;
        private int step;

        private Range(int n) {
            this(0, n, 1);
        }

        private Range(int start, int stop) {
            this(start, stop, 1);
        }

        private Range(int start, int stop, int step) {
            this.start = start;
            this.stop = stop;
            this.step = step;
        }

        @Override
        public Iterator<Integer> iterator() {
            final int min = start;
            final int max = stop / step;

            return new Iterator<Integer>() {
                private int current = min;

                @Override
                public boolean hasNext() {
                    return current < max;
                }

                @Override
                public Integer next() {
                    if (hasNext()) {
                        return current++ * step;
                    } else {
                        throw new NoSuchElementException("Range reached the end");
                    }
                }

                @Override
                public void remove() {
                    throw new UnsupportedOperationException("Can't remove values from a Range");
                }
            };
        }
    }
}

Użycie ArrayList<Integer> może pomóc w rozwiązaniu problemu tasowania bez stosowania większej ilości logiki i zużywania mniej czasu. Oto co proponuję:

ArrayList<Integer> x = new ArrayList<Integer>();
for(int i=1; i<=add.length(); i++)
{
    x.add(i);
}
Collections.shuffle(x);

Poniższy kod osiągnie losową kolejność na tablicy.

// Shuffle the elements in the array
Collections.shuffle(Arrays.asList(array));

Od: http://www.programcreek.com/2012/02/java-method-to-shuffle-an-int-array-with-random-order/

Możesz teraz używać Javy 8:

Collections.addAll(list, arr);
Collections.shuffle(list);
cardsList.toArray(arr);

Oto Wersja generyczna dla tablic:

import java.util.Random;

public class Shuffle<T> {

    private final Random rnd;

    public Shuffle() {
        rnd = new Random();
    }

    /**
     * Fisher–Yates shuffle.
     */
    public void shuffle(T[] ar) {
        for (int i = ar.length - 1; i > 0; i--) {
            int index = rnd.nextInt(i + 1);
            T a = ar[index];
            ar[index] = ar[i];
            ar[i] = a;
        }
    }
}

Biorąc pod uwagę, że ArrayList jest w zasadzie tylko tablicą, może być wskazane, aby pracować z ArrayList zamiast jawnej tablicy i używać kolekcji.shuffle (). Testy wydajności nie wykazują jednak żadnej znaczącej różnicy między powyższymi a zbiorami.Sortuj ():

Shuffe<Integer>.shuffle(...) performance: 576084 shuffles per second
Collections.shuffle(ArrayList<Integer>) performance: 629400 shuffles per second
MathArrays.shuffle(int[]) performance: 53062 shuffles per second

Implementacja Apache Commons MathArrays.shuffle jest ograniczone do int [] i kara wydajności jest prawdopodobnie spowodowana generatorem liczb losowych jest używany.

Random rnd = new Random();
for (int i = ar.length - 1; i > 0; i--)
{
  int index = rnd.nextInt(i + 1);
  // Simple swap
  int a = ar[index];
  ar[index] = ar[i];
  ar[i] = a;
}

Przy okazji, zauważyłem, że ten kod zwraca ar.length - 1 liczbę elementów, więc jeśli Twoja tablica ma 5 elementów, nowa tablica tasowana będzie miała 4 elementy. Dzieje się tak, ponieważ pętla for mówi i>0. Jeśli zmienisz na i>=0, wszystkie elementy zostaną przetasowane.

Oto rozwiązanie przy użyciu Apache Commons Math 3.x (tylko dla tablic int []):

MathArrays.shuffle(array);

Http://commons.apache.org/proper/commons-math/javadocs/api-3.6.1/org/apache/commons/math3/util/MathArrays.html#shuffle(int[])

Alternatywnie, Apache Commons Lang 3.6 wprowadził nowe metody shuffle do klasy ArrayUtils (dla obiektów i wszelkich prymitywnych Typ).

ArrayUtils.shuffle(array);

Http://commons.apache.org/proper/commons-lang/javadocs/api-release/org/apache/commons/lang3/ArrayUtils.html#shuffle-int:A-

W niektórych odpowiedziach widziałem trochę informacji, więc postanowiłem dodać nową.

Tablice zbiorów Javy.asList przyjmuje var-arg typu T (T ...). Jeśli przekazujesz prymitywną tablicę (int array), metoda asList wywnioskuje i wygeneruje List<int[]>, która jest listą jednego elementu (jednym elementem jest prymitywna tablica). jeśli przetasujesz tę listę elementów, nic to nie zmieni.

Więc najpierw musisz przekonwertować prymitywną tablicę na tablicę obiektów wrappera. do tego możesz użyć ArrayUtils.toObject metoda z apache.commons.lang. następnie przekaż wygenerowaną tablicę do listy i przetasuj ją.

  int[] intArr = {1,2,3};
  List<Integer> integerList = Arrays.asList(ArrayUtils.toObject(array));
  Collections.shuffle(integerList);
  //now! elements in integerList are shuffled!

1. pole od int[] do Integer[]
2. zawiń tablicę w listę za pomocą metody Arrays.asList

3. Przetasuj metodą Collections.shuffle

   int[] solutionArray = { 1, 2, 3, 4, 5, 6, 6, 5, 4, 3, 2, 1 };
   
   Integer[] boxed = Arrays.stream(solutionArray).boxed().toArray(Integer[]::new);
   Collections.shuffle(Arrays.asList(boxed));
   
   System.out.println(Arrays.toString(boxed));
   // [1, 5, 5, 4, 2, 6, 1, 3, 3, 4, 2, 6]
   

Oto inny sposób na przetasowanie listy

public List<Integer> shuffleArray(List<Integer> a) {
List<Integer> b = new ArrayList<Integer>();
    while (a.size() != 0) {
        int arrayIndex = (int) (Math.random() * (a.size()));
        b.add(a.get(arrayIndex));
        a.remove(a.get(arrayIndex));
    }
    return b;
}

Wybierz losową liczbę z oryginalnej listy i zapisz ją na innej liście.Następnie usuń numer z oryginalnej listy.Rozmiar oryginalnej listy będzie malał o jeden, dopóki wszystkie elementy nie zostaną przeniesione do nowej listy.

Rozważam to bardzo popularne pytanie, ponieważ nikt nie napisał wersji shuffle-copy. Styl jest mocno zapożyczony z Arrays.java, Bo kto nie grabieży w dzisiejszych czasach technologii Java? Implementacje Generic i int włączone.

   /**
    * Shuffles elements from {@code original} into a newly created array.
    *
    * @param original the original array
    * @return the new, shuffled array
    * @throws NullPointerException if {@code original == null}
    */
   @SuppressWarnings("unchecked")
   public static <T> T[] shuffledCopy(T[] original) {
      int originalLength = original.length; // For exception priority compatibility.
      Random random = new Random();
      T[] result = (T[]) Array.newInstance(original.getClass().getComponentType(), originalLength);

      for (int i = 0; i < originalLength; i++) {
         int j = random.nextInt(i+1);
         result[i] = result[j];
         result[j] = original[i];
      }

      return result;
   }


   /**
    * Shuffles elements from {@code original} into a newly created array.
    *
    * @param original the original array
    * @return the new, shuffled array
    * @throws NullPointerException if {@code original == null}
    */
   public static int[] shuffledCopy(int[] original) {
      int originalLength = original.length;
      Random random = new Random();
      int[] result = new int[originalLength];

      for (int i = 0; i < originalLength; i++) {
         int j = random.nextInt(i+1);
         result[i] = result[j];
         result[j] = original[i];
      }

      return result;
   }

To algorytm Knutha shuffle.

public class Knuth { 

    // this class should not be instantiated
    private Knuth() { }

    /**
     * Rearranges an array of objects in uniformly random order
     * (under the assumption that <tt>Math.random()</tt> generates independent
     * and uniformly distributed numbers between 0 and 1).
     * @param a the array to be shuffled
     */
    public static void shuffle(Object[] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            // choose index uniformly in [i, n-1]
            int r = i + (int) (Math.random() * (n - i));
            Object swap = a[r];
            a[r] = a[i];
            a[i] = swap;
        }
    }

    /**
     * Reads in a sequence of strings from standard input, shuffles
     * them, and prints out the results.
     */
    public static void main(String[] args) {

        // read in the data
        String[] a = StdIn.readAllStrings();

        // shuffle the array
        Knuth.shuffle(a);

        // print results.
        for (int i = 0; i < a.length; i++)
            StdOut.println(a[i]);
    }
}

Jest też inny sposób, jeszcze nie post

//that way, send many object types diferentes
public anotherWayToReciveParameter(Object... objects)
{
    //ready with array
    final int length =objects.length;
    System.out.println(length);
    //for ready same list
    Arrays.asList(objects);
}

W ten sposób łatwiej, w zależności od kontekstu

Najprostsze rozwiązanie tego losowego tasowania w tablicy.

String location[] = {"delhi","banglore","mathura","lucknow","chandigarh","mumbai"};
int index;
String temp;
Random random = new Random();
for(int i=1;i<location.length;i++)
{
    index = random.nextInt(i+1);
    temp = location[index];
    location[index] = location[i];
    location[i] = temp;
    System.out.println("Location Based On Random Values :"+location[i]);
}

Proste rozwiązanie dla Groovy:

solutionArray.sort{ new Random().nextInt() }

Spowoduje losowe sortowanie wszystkich elementów listy tablic, które archiwizuje pożądany wynik tasowania wszystkich elementów.

Najprostszy kod do przetasowania:

import java.util.*;
public class ch {
    public static void main(String args[])
    {
        Scanner sc=new Scanner(System.in);
        ArrayList<Integer> l=new ArrayList<Integer>(10);
        for(int i=0;i<10;i++)
            l.add(sc.nextInt());
        Collections.shuffle(l);
        for(int j=0;j<10;j++)
            System.out.println(l.get(j));       
    }
}

public class ShuffleArray {
public static void shuffleArray(int[] a) {
    int n = a.length;
    Random random = new Random();
    random.nextInt();
    for (int i = 0; i < n; i++) {
        int change = i + random.nextInt(n - i);
        swap(a, i, change);
    }
}

private static void swap(int[] a, int i, int change) {
    int helper = a[i];
    a[i] = a[change];
    a[change] = helper;
}

public static void main(String[] args) {
    int[] a = new int[] { 1, 2, 3, 4, 5, 6, 6, 5, 4, 3, 2, 1 };
    shuffleArray(a);
    for (int i : a) {
        System.out.println(i);
    }
}
}

import java.util.ArrayList;
import java.util.Random;
public class shuffle {
    public static void main(String[] args) {
        int a[] =  {1,2,3,4,5,6,7,8,9};
         ArrayList b = new ArrayList();
       int i=0,q=0;
       Random rand = new Random();

       while(a.length!=b.size())
       {
           int l = rand.nextInt(a.length);
//this is one option to that but has a flaw on 0
//           if(a[l] !=0)
//           {
//                b.add(a[l]);
//               a[l]=0;
//               
//           }
//           
// this works for every no. 
                if(!(b.contains(a[l])))
                {
                    b.add(a[l]);
                }



       }

//        for (int j = 0; j <b.size(); j++) {
//            System.out.println(b.get(j));
//            
//        }
System.out.println(b);
    }

}

Kolejny łatwy sposób na przetasowanie:

int LengthArray = solutionArray.lenght();
Random r = new Random();
int randomNumber = r.nextInt(LengthArray);
Integer Chosen = solutionArray.getInteger(randomNumber);