Losowe tasowanie tablicy

232

Muszę losowo przetasować następującą tablicę:

int[] solutionArray = {1, 2, 3, 4, 5, 6, 6, 5, 4, 3, 2, 1};

Czy jest jakaś funkcja, aby to zrobić?

Hubert
źródło
5
Jest to metoda zestawu SDK, której szukasz: Collect.shuffle (Arrays.asList (tablica));
Louis Hong
2
@Louie Nie, to nie działa. To stworzyłoby List<int[]>jeden wpis. Zobacz moją odpowiedź dotyczącą sposobu osiągnięcia tego celu za pomocą Collections.shuffle().
Duncan Jones
2
Naprawdę nie jest to odpowiedź na pierwotne pytanie, ale MathArrays.shuffle z biblioteki commons-math3 spełnia swoje zadanie.
sandris
1
Nie jest to wystarczająco tematyczne, aby uzasadnić odpowiedź, ale pamiętam naprawdę fajny artykuł z książki „Graphics Gems”, który mówił o przemierzaniu tablicy w pseudolosowej kolejności. Moim zdaniem to przede wszystkim bicie musiało tasować dane. Implementacja C znajduje się tutaj github.com/erich666/GraphicsGems/blob/master/gems/Dissolve.c
Lennart Rolland
Zobacz także ściśle powiązane pytanie: stackoverflow.com/questions/2450954/...
Pierz

Odpowiedzi:

263

Używanie kolekcji do przetasowania szeregu prymitywnych typów to trochę przesada ...

Wystarczy samodzielnie zaimplementować tę funkcję, używając na przykład tasowania Fisher – Yates :

import java.util.*;
import java.util.concurrent.ThreadLocalRandom;

class Test
{
  public static void main(String args[])
  {
    int[] solutionArray = { 1, 2, 3, 4, 5, 6, 16, 15, 14, 13, 12, 11 };

    shuffleArray(solutionArray);
    for (int i = 0; i < solutionArray.length; i++)
    {
      System.out.print(solutionArray[i] + " ");
    }
    System.out.println();
  }

  // Implementing Fisher–Yates shuffle
  static void shuffleArray(int[] ar)
  {
    // If running on Java 6 or older, use `new Random()` on RHS here
    Random rnd = ThreadLocalRandom.current();
    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;
    }
  }
}
PhiLho
źródło
26
Niezwykle trywialny nitpick, ale możesz go użyć println()zamiast println(""). Myślę, że jaśniejsze w intencji :)
Cowan
55
O wiele lepiej byłoby użyć Collections.shuffle (Arrays.asList (array)); a następnie tasować siebie.
Louis Hong
21
@Louie Collections.shuffle(Arrays.asList(array))nie działa, ponieważ Arrays.asList(array)zwraca Collection<int[]>nie Collection<Integer>tak, jak myślałeś.
Adam Stelmaszczyk,
15
@exhuma Ponieważ jeśli masz tablicę tysięcy lub milionów prymitywnych wartości do sortowania, zawijanie każdego z nich w celu wykonania sortowania jest nieco kosztowne, zarówno w pamięci, jak i procesorze.
PhiLho,
14
To nie jest tasowanie Fisher-Yates. Nazywa się to tasowaniem Durstenfelda . Oryginalny losowy losowanie rybaków trwa w czasie O (n ^ 2), który jest bardzo wolny.
Pacerier
164

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);
Methodin
źródło
1
Możesz po prostuCollectons.shuffle(Arrays.asList(solutionArray));
FindOutIslamNow
@Timmos Mylisz się. Arrays.asList otacza oryginalną tablicę, a jej modyfikacja modyfikuje oryginalną tablicę. Dlatego nie można dodawać ani usuwać, ponieważ tablice mają stały rozmiar.
Nand
@Nie jestem pewien, o czym myślałem, ale patrząc na kod źródłowy, w rzeczywistości metoda Arrays.asList tworzy ArrayList wspierany przez podaną tablicę. Dzięki za zwrócenie na to uwagi. Usunąłem mój poprzedni komentarz (nie mogłem go edytować).
Timmos
100

Oto działająca i wydajna funkcja losowania tablicy Fisher-Yates:

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;
    }
}
Dan Bray
źródło
1
Głosowałem, ponieważ potrzebowałem rozwiązania, które nie wymagałoby dużego nakładu pracy przy tworzeniu zbioru liczb całkowitych
mwk 30.09.13
2
Czy druga implementacja nie ma możliwości wymiany z własnym indeksem? random.nextInt(int bound)jest wyłączny, ale podanie go i + 1jako argumentu pozwoliłoby indexi ipotencjalnie byłoby takie samo.
bmcentee148
21
@ bmcentee148 Zamiana elementu z sobą jest dozwolona w przypadkowej kolejności. Niezrozumienie tego osłabiło Enigmę i pomogło Alanowi Turingowi go złamać. en.wikipedia.org/wiki/…
Ellen Spertus
4
xorSztuką jest dobre dla wymiany rejestrów procesora, gdy procesor nie ma instrukcji wymiany i nie ma wolnych rejestrów, ale do ciężkich elementów tablicy wewnątrz pętli, nie widzę żadnych korzyści. W przypadku tymczasowych zmiennych lokalnych nie ma powodu, aby deklarować je poza pętlą.
Holger
1
Nieco bardziej efektywne jest zadeklarowanie tempzmiennej poza pętlą. XORTrik powinien być szybszy niż przy użyciu tempzmiennej ale jedynym sposobem, aby upewnić się, że aby wykonać test porównawczy.
Dan Bray
25

Klasa Kolekcje ma wydajną metodę tasowania, którą można kopiować, aby na nią nie polegać:

/**
 * 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;
    }
}
KitKat
źródło
żeby na tym nie polegać ? Wolałbym na tym polegać, gdyby to tylko możliwe.
shmosel
@shmosel Następnie możesz go użyć. Pamiętaj, aby zaimportować wymaganą klasę i przekonwertować tablicę na listę za pomocą Arrays.asList. Trzeba również przekonwertować wynikową listę na tablicę
KitKat
Nie możesz używać Arrays.asList()prymitywnej tablicy. I nie musisz go konwertować, ponieważ jest to tylko opakowanie.
shmosel
13

Spójrz na Collectionsklasę shuffle(...).

Dave
źródło
8
Jak korzystać z tej klasy Kolekcje w systemie Android? Aby go użyć, musisz wykonać specjalny import (CRTL SHIFT O nie działa)?
Hubert
@Hubert powinien być częścią pakietu java.util. Jest częścią standardowej biblioteki od wersji 1.2.
MauganRa
3
Aby twoja odpowiedź była bardziej samodzielna, powinna zawierać przykładowy kod. IE:import java.util.Collections; shuffle(solutionArray);
Stevoisiak,
10

Oto kompletne rozwiązanie wykorzystujące Collections.shufflepodejście:

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 cierpi z powodu niezdolności Javy do płynnego tłumaczenia między int[]i Integer[](a więc int[]i List<Integer>).

Duncan Jones
źródło
10

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

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

Przykładowe czasy trwania

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

Poniżej znajdują się trzy różne implementacje losowania. Z kolekcji można korzystać tylko w przypadku kolekcji. Nie ma potrzeby zawijania tablicy w kolekcję, aby ją posortować. 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);
    }

Przetasowanie listy ogólnej

    // ================================================================
    // 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;
    }

Przetasowanie tablicy ogólnej

    // ================================================================
    // 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;
    }

Przetasowanie pierwotnej 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 metody narzędzi 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;
    }

Klasa zasięgu

Generuje zakres wartości, podobny do rangefunkcji 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");
                }
            };
        }
    }
}
Pan Polywhirl
źródło
1
Nie mierzysz tych samych rzeczy i mierzysz je tylko raz (wtedy liczy się ich kolejność i zapominasz o optymalizacji środowiska wykonawczego). Powinieneś zadzwonić range, toArraya toPrimitiveprzed jakimkolwiek czasem, i zapętlić, aby móc cokolwiek zawrzeć (pseudo-kod: zrób kilka razy {generuj listę, arr i iarr; lista tasowania czasu; arr tasowanie czasu; tasowanie czasu iarr}). Moje wyniki: 1. miejsce list: 36017ns, arr: 28262ns, iarr: 23334ns. 100 list: 18445ns, arr: 19995ns, iarr: 18657ns. : Pokazuje tylko, że int [] jest wstępnie zoptymalizowany (według kodu), ale jest prawie równoważny z optymalizacją środowiska wykonawczego.
syme
9

Używanie ArrayList<Integer>może pomóc w rozwiązaniu problemu tasowania bez stosowania dużej logiki i pochłaniania mniej czasu. Oto, co sugeruję:

ArrayList<Integer> x = new ArrayList<Integer>();
for(int i=1; i<=add.length(); i++)
{
    x.add(i);
}
Collections.shuffle(x);
SalmaanKhan
źródło
Prawdopodobnie nie to drugie - pochłaniające mniej czasu . W rzeczywistości jest to z pewnością wolniejsze niż prymitywne implementacje powyżej.
Boris the Spider
1
Dla kogoś, kto skopiuje kod, zobacz „dla cyklu” i = 1 może potrzebujesz i = 0
Boris Karloff
5

Możesz teraz używać Java 8:

Collections.addAll(list, arr);
Collections.shuffle(list);
cardsList.toArray(arr);
Иван Николайчук
źródło
2
W tym kodzie nie ma nic specyficznego dla Java8. Działa to od Java2. Cóż, zadziałałoby, gdy naprawisz niespójność między pierwszym użyciem lista nagłym nawiązaniem do cardsList. Ale ponieważ musisz utworzyć tymczasowy list, który pominąłeś, nie ma korzyści w porównaniu z Collections.shuffle(Arrays.asList(arr));podejściem pokazanym tutaj kilka razy. Co działa również od wersji Java2.
Holger
3

Oto wersja ogólna 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 z jawną tablicą i użyć Collections.shuffle (). Testy wydajności nie wykazują jednak żadnej istotnej różnicy między powyższym a Collections.sort ():

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 ograniczona do int [], a spadek wydajności prawdopodobnie wynika z użycia generatora liczb losowych.

użytkownik1050755
źródło
1
Wygląda na to, można przejść new JDKRandomGenerator()do MathArrays.shuffle. Zastanawiam się, jak to wpływa na wydajność?
Brandon
Właściwie ... to wygląda jak MathArrays#shufflema podziału w swojej podstawowej pętli: int targetIdx = new UniformIntegerDistribution(rng, start, i).sample();. Dziwaczny.
Brandon
3
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;
}

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

Cristiane Dos Santos Costa
źródło
Tylko jedna głowa do góry, możesz przenieść to do sekcji komentarza w swoim pytaniu, ponieważ prawdopodobnie zostanie ono oznaczone, jeśli pozostawi jako własną odpowiedź.
Jason D
1
Wydaje się, że to odpowiada na pytanie, więc nie jestem pewien, o czym mówisz @JasonD
Sumurai8,
1
Kod jest poprawny, komentarz jest niepoprawny. Jeśli zmienisz i>0na i>=0, tracisz czas, zamieniając element 0samym sobą.
jcsahnwaldt Reinstate Monica
3

Oto rozwiązanie wykorzystujące 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 losowania do ArrayUtilsklasy (dla obiektów i dowolnego typu pierwotnego).

ArrayUtils.shuffle(array);

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

Emmanuel Bourg
źródło
3

W niektórych odpowiedziach zauważyłem brakujące informacje, więc postanowiłem dodać nową.

Java kolekcje Arrays.asList trwa var-Arg typu T (T ...). Jeśli przekażesz prymitywną tablicę (tablicę int), metoda asList będzie wnioskować i wygenerować listę List<int[]>, która jest listą jednego elementu (jeden element jest tablicą pierwotną). jeśli przetasujesz tę listę jednego elementu, nic to nie zmieni.

Najpierw musisz przekonwertować prymitywną tablicę na tablicę obiektów Wrapper. w tym celu możesz użyć ArrayUtils.toObjectmetody z apache.commons.lang. następnie przekaż wygenerowaną tablicę do Listy i na koniec tasuj.

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

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, a następnie usuń numer z oryginalnej listy. Rozmiar oryginalnej listy będzie się zmniejszał o jeden, dopóki wszystkie elementy nie zostaną przeniesione na nową listę.

PS5
źródło
2

Proste rozwiązanie dla Groovy:

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

Spowoduje to losowe posortowanie wszystkich elementów listy tablic, co zarchiwizuje pożądany wynik przetasowania wszystkich elementów.

Hans Kristian
źródło
2

Korzystanie z Guava Ints.asList()jest tak proste, jak:

Collections.shuffle(Ints.asList(array));
BeeOnRope
źródło
1

Zastanawiam się nad tym bardzo popularnym pytaniem, ponieważ nikt nie napisał wersji z tasowaniem. Styl jest mocno zapożyczony Arrays.java, bo kto obecnie nie gra w technologię Java? intZawiera ogólne i implementacje.

   /**
    * 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;
   }
CO BYŁO DO OKAZANIA
źródło
1

Jest to algorytm knuth 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]);
    }
}
BufBills
źródło
1

Jest też inny sposób, jeszcze nie wysyłanie

//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, zależnie od kontekstu

Marcelo Ferreira
źródło
1

Najprostsze rozwiązanie tego losowego tasowania w szyku.

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]);
}
Architekt Goel
źródło
1
  1. Box od int[]doInteger[]
  2. Zawiń tablicę za pomocą Arrays.asListmetody
  3. Przetasuj Collections.shufflemetodą

    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]
YujiSoftware
źródło
1

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));       
    }
}
suraj
źródło
1

Korzystanie z losowej klasy

  public static void randomizeArray(int[] arr) {

      Random rGenerator = new Random(); // Create an instance of the random class 
      for (int i =0; i< arr.length;i++ ) {
          //Swap the positions...

          int rPosition = rGenerator.nextInt(arr.length); // Generates an integer within the range (Any number from 0 - arr.length)
          int temp = arr[i]; // variable temp saves the value of the current array index;
          arr[i] = arr[rPosition];  // array at the current position (i) get the value of the random generated 
          arr[rPosition] = temp; // the array at the position of random generated gets the value of temp

      }

      for(int i = 0; i<arr.length; i++) {
          System.out.print(arr[i]); //Prints out the array
      } 

  }
Fiel Muhongo
źródło
0
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);
    }
}
}
nikhil gupta
źródło
Dodaj pokrewny opis swojej odpowiedzi.
ankit suthar
0
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);
    }

}
aurobind singh
źródło
0

podobnie bez użycia swap b

        Random r = new Random();
    int n = solutionArray.length;
    List<Integer> arr =  Arrays.stream(solutionArray).boxed().collect(Collectors.toList());
    for (int i = 0; i < n-1; i++) {
        solutionArray[i] = arr.remove( r.nextInt(arr.size())); // randomize base on size
    }
    solutionArray[n-1] = arr.get(0);
digitebs
źródło
0

Jednym z rozwiązań jest użycie permutacji do wstępnego obliczenia wszystkich permutacji i zapisanych w ArrayList

Java 8 wprowadziła nową metodę ints () w klasie java.util.Random. Metoda ints () zwraca nieograniczony strumień pseudolosowych wartości int. Możesz ograniczyć liczby losowe między określonym zakresem, podając wartości minimalne i maksymalne.

Random genRandom = new Random();
int num = genRandom.nextInt(arr.length);

Za pomocą generowania liczby losowej możesz iterować przez pętlę i zamieniać się bieżącym indeksem na liczbę losową. W ten sposób możesz wygenerować liczbę losową ze złożonością przestrzeni O (1).


źródło
0

Bez losowego rozwiązania:

   static void randomArrTimest(int[] some){
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < some.length; i++) {
            long indexToSwap = startTime%(i+1);
            long tmp = some[(int) indexToSwap];
            some[(int) indexToSwap] = some[i];
            some[i] = (int) tmp;
        }
        System.out.println(Arrays.toString(some));
    }
izum286
źródło