wake-up-neo.com

Zufälliges Mischen eines Arrays

Ich muss das folgende Array zufällig mischen:

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

Gibt es eine Funktion, um das zu tun?

192
Hubert

Die Verwendung von Collections zum Mischen eines Arrays von primitiven Typen ist ein wenig übertrieben ...

Es ist einfach genug, die Funktion selbst zu implementieren, beispielsweise mit Fisher-Yates-Shuffle :

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;
    }
  }
}
237
PhiLho

Hier ist eine einfache Möglichkeit, eine ArrayList zu verwenden:

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

Hier ist eine funktionierende und effiziente Shuffle-Array-Funktion von 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];
        }
    }
}

oder

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;
    }
}
93
Dan Bray

Collections class hat eine effiziente Methode zum Mischen, die kopiert werden kann, um nicht davon abhängig zu sein:

/**
 * 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;
    }
}
22
KitKat

Schauen Sie sich die Collections -Klasse an, insbesondere shuffle(...).

12
Dave

Sie haben hier einige Möglichkeiten. Eine Liste unterscheidet sich etwas von einem Array, wenn es um das Mischen geht.

Wie Sie unten sehen können, ist ein Array schneller als eine Liste, und ein primitives Array ist schneller als ein Objektarray.

Musterdauer

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

Im Folgenden sind drei verschiedene Implementierungen einer Shuffle-Funktion dargestellt. Sie sollten Collections.shuffle nur verwenden, wenn Sie sich mit einer Sammlung beschäftigen. Sie müssen Ihr Array nicht in eine Sammlung packen, nur um es zu sortieren. Die folgenden Methoden sind sehr einfach zu implementieren.

ShuffleUtil-Klasse

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;

Hauptmethode

    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);
    }

Mischen einer generischen Liste

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

Mischen eines generischen Arrays

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

Mischen eines primitiven Arrays

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

Utility-Methoden

Einfache Hilfsmittel zum Kopieren und Konvertieren von Arrays in Listen und umgekehrt.

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

Erzeugt einen Wertebereich, ähnlich der range-Funktion von Python.

    // ================================================================
    // 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");
                }
            };
        }
    }
}
9
Mr. Polywhirl

Hier ist eine Komplettlösung mit dem Collections.shuffle-Ansatz:

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);
  }    
}

Beachten Sie, dass es unter der Unfähigkeit von Java leidet, zwischen int[] und Integer[] (und damit int[] und List<Integer>) problemlos zu übersetzen.

9
Duncan Jones

Mit ArrayList<Integer> können Sie das Problem des Mischens lösen, ohne viel Logik anwenden zu müssen und weniger Zeit zu benötigen. Ich schlage vor:

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

Mit dem folgenden Code wird eine zufällige Reihenfolge für das Array erreicht. 

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

from: http://www.programcreek.com/2012/02/Java-method-to-shuffle-an-intintarray-mit-random-order/

6
Rajib Biswas

Sie können Java 8 jetzt verwenden:

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

Hier ist eine Generics-Version für Arrays:

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

Da ArrayList im Wesentlichen nur ein Array ist, kann es ratsam sein, mit einem ArrayList anstelle des expliziten Arrays zu arbeiten und Collections.shuffle () zu verwenden. Leistungstests zeigen jedoch keinen signifikanten Unterschied zwischen dem obigen und 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

Die Implementierung von MathArrays.shuffle in Apache Commons ist auf int [] beschränkt, und die Leistungseinbußen sind wahrscheinlich auf den Zufallszahlengenerator zurückzuführen.

3
user1050755

Hier ist eine Lösung mit Apache Commons Math 3.x (nur für int [] Arrays):

MathArrays.shuffle(array);

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

Alternativ dazu hat Apache Commons Lang 3.6 neue Shuffle-Methoden für die Klasse ArrayUtils (für Objekte und jeden primitiven Typ) eingeführt.

ArrayUtils.shuffle(array);

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

3
Emmanuel Bourg
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;
}

Ich habe übrigens bemerkt, dass dieser Code eine ar.length - 1 Anzahl von Elementen zurückgibt. Wenn Ihr Array 5 Elemente enthält, enthält das neue gemischte Array 4 Elemente. Dies geschieht, weil die for-Schleife i>0 sagt. Wenn Sie zu i>=0 wechseln, werden alle Elemente neu gemischt.

Ich habe einige fehlende Informationen in einigen Antworten gesehen, also entschied ich mich, eine neue hinzuzufügen.

Java-Sammlungen Arrays.asList verwendet var-arg vom Typ T (T ...). Wenn Sie ein primitives Array (int-Array) übergeben, leitet die asList-Methode einen List<int[]> ab, der eine Ein-Element-Liste ist (das eine Element ist das primitive Array). Wenn Sie diese eine Elementliste mischen, ändert sich dadurch nichts.

Zuerst müssen Sie Ihr primitives Array in ein Wrapper-Objektarray konvertieren. Dazu können Sie die ArrayUtils.toObject-Methode aus Apache.commons.lang verwenden. Übergeben Sie dann das generierte Array an eine Liste und mischen Sie diese schließlich.

  int[] intArr = {1,2,3};
  List<Integer> integerList = Arrays.asList(ArrayUtils.toObject(array));
  Collections.shuffle(integerList);
  //now! elements in integerList are shuffled!
3
Mr.Q
  1. Box von int[] bis Integer[]
  2. Wrapp ein Array in eine Liste mit der Arrays.asList-Methode
  3. Mischen Sie mit der Collections.shuffle-Methode

    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]
    
2
YujiSoftware

Hier ist eine weitere Möglichkeit, eine Liste neu zu mischen

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

Wählen Sie eine Zufallszahl aus der ursprünglichen Liste aus und speichern Sie sie in einer anderen Liste. Entfernen Sie dann die Nummer aus der ursprünglichen Liste. Die Größe der ursprünglichen Liste wird immer weiter verringert, bis alle Elemente in die neue Liste verschoben werden. 

2
PS5

Eine einfache Lösung für Groovy:

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

Dadurch werden alle Elemente der Array-Liste zufällig sortiert, wodurch das gewünschte Ergebnis des Mischens aller Elemente archiviert wird.

1
Hans Kristian

Die einfachste Lösung für dieses zufällige Mischen in einem Array.

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]);
}
1
Archit Goel

Einfachster Code zum Mischen:

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));       
    }
}
1
suraj

Ich denke über diese sehr beliebte Frage nach, da noch niemand eine Shuffle-Copy-Version geschrieben hat. Style ist stark von Arrays.Java Entlehnt, denn wer ist nicht plündert Java Technologie heutzutage? Generische und int Implementierungen enthalten.

   /**
    * 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;
   }
1
QED

Es gibt auch einen anderen Weg, noch nicht zu posten

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

auf diese Weise einfacher, abhängig vom Kontext

1

Dies ist ein Knuth-Shuffle-Algorithmus.

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]);
    }
}
1
BufBills

Eine der Lösungen verwendet die Permutation, um alle Permutationen im Voraus zu berechnen und in der ArrayList zu speichern

In Java 8 wurde die neue Methode ints () in der Klasse Java.util.Random eingeführt. Die ints () -Methode gibt einen unbegrenzten Strom von pseudozufälligen int-Werten zurück. Sie können die Zufallszahlen zwischen einem angegebenen Bereich begrenzen, indem Sie die Mindest- und Höchstwerte angeben.

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

Mit Hilfe der Generierung der Zufallszahl können Sie durch die Schleife iterieren und den aktuellen Index mit der Zufallszahl ... _ austauschen. So können Sie eine Zufallszahl mit O(1) - Leerzeichen erzeugen.

0
Maulik Sakhida

Die Verwendung von Guava Ints.asList() ist so einfach wie:

Collections.shuffle(Ints.asList(array));
0
BeeOnRope
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);
    }
}
}
0
nikhil gupta

ähnlich ohne Verwendung von 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);
0
digitebs
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);
    }

}
0
aurobind singh