Necesito barajar aleatoriamente la siguiente matriz:
int[] solutionArray = {1, 2, 3, 4, 5, 6, 6, 5, 4, 3, 2, 1};
¿Hay alguna función para hacer eso?
Usar Colecciones para barajar una variedad de tipos primitivos es un poco exagerado ...
Es bastante simple implementar la función usted mismo, usando, por ejemplo, el shuffle de 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;
}
}
}
println()
lugar de println("")
. Más claro en la intención, creo :)
Collections.shuffle(Arrays.asList(array))
no funciona, porque no Arrays.asList(array)
regresa como pensabas. Collection<int[]>
Collection<Integer>
Aquí hay una manera simple de usar un ArrayList
:
List<Integer> solution = new ArrayList<>();
for (int i = 1; i <= 6; i++) {
solution.add(i);
}
Collections.shuffle(solution);
Collectons.shuffle(Arrays.asList(solutionArray));
Aquí hay una función de matriz aleatoria Fisher – Yates que funciona y es eficiente:
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];
}
}
}
o
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;
}
}
random.nextInt(int bound)
es exclusivo, pero darlo i + 1
como argumento lo permitiría index
y i
podría ser lo mismo.
xor
truco es excelente para intercambiar registros de CPU cuando la CPU no tiene instrucciones de intercambio y no hay registros libres, pero para intercambiar elementos de matriz dentro de un bucle, no veo ningún beneficio. Para las variables locales temporales, no hay razón para declararlas fuera del ciclo.
temp
variable fuera del ciclo. El XOR
truco debería ser más rápido que usar una temp
variable, pero la única forma de asegurarse de que realice una prueba de referencia.
La clase de colecciones tiene un método eficiente para barajar, que se puede copiar para no depender de él:
/**
* 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;
}
}
Arrays.asList
. También debe convertir la lista resultante en una matriz
Arrays.asList()
en una matriz primitiva. Y no necesitaría convertirlo de nuevo porque es solo un contenedor.
Mira la Collections
clase, específicamente shuffle(...)
.
java.util
. Es parte de la biblioteca estándar desde v1.2.
import java.util.Collections; shuffle(solutionArray);
Aquí hay una solución completa usando el Collections.shuffle
enfoque:
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);
}
}
Tenga en cuenta que sufre debido a la incapacidad de Java para traducir sin problemas entre int[]
y Integer[]
(y por lo tanto int[]
y List<Integer>
).
Tienes un par de opciones aquí. Una lista es un poco diferente a una matriz cuando se trata de barajar.
Como puede ver a continuación, una matriz es más rápida que una lista, y una matriz primitiva es más rápida que una matriz de objetos.
List<Integer> Shuffle: 43133ns
Integer[] Shuffle: 31884ns
int[] Shuffle: 25377ns
A continuación, hay tres implementaciones diferentes de un shuffle. Solo debe usar Collections.shuffle si se trata de una colección. No es necesario envolver su matriz en una colección solo para ordenarla. Los siguientes métodos son muy simples de implementar.
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;
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);
}
// ================================================================
// 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;
}
// ================================================================
// 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;
}
// ================================================================
// 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;
}
Métodos de utilidad simples para copiar y convertir matrices en listas y viceversa.
// ================================================================
// 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;
}
Genera un rango de valores, similar a la range
función de 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");
}
};
}
}
}
range
, toArray
y toPrimitive
antes de cualquier sincronización, y realizar un bucle para poder concluir cualquier cosa (pseudocódigo: hacer varias veces {generar lista, arr y iarr; lista de barajado de tiempo; arr barajar de tiempo; arriar de barajado de tiempo}). Mi resultados: primero: list: 36017ns, arr: 28262ns, iarr: 23334ns
. 100a: list: 18445ns, arr: 19995ns, iarr: 18657ns
. Simplemente muestra que int [] está optimizado previamente (por código) pero son casi equivalentes con la optimización de tiempo de ejecución.
Usar ArrayList<Integer>
puede ayudarlo a resolver el problema de barajar sin aplicar mucha lógica y consumir menos tiempo. Esto es lo que sugiero:
ArrayList<Integer> x = new ArrayList<Integer>();
for(int i=1; i<=add.length(); i++)
{
x.add(i);
}
Collections.shuffle(x);
El siguiente código logrará un orden aleatorio en la matriz.
// Shuffle the elements in the array
Collections.shuffle(Arrays.asList(array));
de: http://www.programcreek.com/2012/02/java-method-to-shuffle-an-int-array-with-random-order/
Puedes usar java 8 ahora:
Collections.addAll(list, arr);
Collections.shuffle(list);
cardsList.toArray(arr);
list
y la referencia repentina cardsList
. Pero dado que necesita crear el temporal list
, que ha omitido, no hay ningún beneficio sobre el Collections.shuffle(Arrays.asList(arr));
enfoque que se muestra varias veces aquí. Lo que también funciona desde Java2.
Aquí hay una versión genérica para matrices:
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;
}
}
}
Teniendo en cuenta que ArrayList es básicamente solo una matriz, puede ser aconsejable trabajar con una ArrayList en lugar de la matriz explícita y usar Collections.shuffle (). Sin embargo, las pruebas de rendimiento no muestran ninguna diferencia significativa entre lo anterior y 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
La implementación de Apache Commons MathArrays.shuffle está limitada a int [] y la penalización de rendimiento probablemente se deba al generador de números aleatorios que se está utilizando.
new JDKRandomGenerator()
a MathArrays.shuffle
. Me pregunto cómo afecta eso al rendimiento.
MathArrays#shuffle
tiene una asignación en su bucle principal: int targetIdx = new UniformIntegerDistribution(rng, start, i).sample();
. Extraño.
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;
}
Por cierto, he notado que este código devuelve una ar.length - 1
serie de elementos, por lo que si su matriz tiene 5 elementos, la nueva matriz aleatoria tendrá 4 elementos. Esto sucede porque el bucle for dice i>0
. Si cambia a i>=0
, obtiene todos los elementos barajados.
i>0
a i>=0
, pierde tiempo intercambiando elementos 0
consigo mismo.
Aquí hay una solución que usa Apache Commons Math 3.x (solo para matrices int []):
MathArrays.shuffle(array);
Alternativamente, Apache Commons Lang 3.6 introdujo nuevos métodos aleatorios en la ArrayUtils
clase (para objetos y cualquier tipo primitivo).
ArrayUtils.shuffle(array);
Vi información faltante en algunas respuestas, así que decidí agregar una nueva.
Java colecciones Arrays.asList toma var-arg del tipo T (T ...)
. Si pasa una matriz primitiva (int array), el método asList inferirá y generará unList<int[]>
, que es una lista de un elemento (el elemento es la matriz primitiva). si barajas esta lista de elementos, no cambiará nada.
Entonces, primero debe convertir su matriz primitiva en una matriz de objetos Wrapper. para esto puede usar el ArrayUtils.toObject
método de apache.commons.lang. luego pasa la matriz generada a una Lista y finalmente baraja eso.
int[] intArr = {1,2,3};
List<Integer> integerList = Arrays.asList(ArrayUtils.toObject(array));
Collections.shuffle(integerList);
//now! elements in integerList are shuffled!
Aquí hay otra forma de barajar una lista
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;
}
Elija un número aleatorio de la lista original y guárdelo en otra lista. Luego elimine el número de la lista original. El tamaño de la lista original seguirá disminuyendo en uno hasta que todos los elementos se muevan a la nueva lista.
Una solución simple para Groovy:
solutionArray.sort{ new Random().nextInt() }
Esto ordenará todos los elementos de la lista de la matriz al azar, lo que archiva el resultado deseado de barajar todos los elementos.
Usar guayaba Ints.asList()
es tan simple como:
Collections.shuffle(Ints.asList(array));
Estoy sopesando esta pregunta muy popular porque nadie ha escrito una versión de copia aleatoria. El estilo se toma prestado en gran medida Arrays.java
, porque ¿quién no está saqueando la tecnología Java en estos días? Genéricos e int
implementaciones incluidas.
/**
* 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;
}
Este es el algoritmo de 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]);
}
}
También hay otra forma, no publicar aún
//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);
}
de esa manera más fácil, dependía del contexto
La solución más simple para este Aleatorio aleatorio en una matriz.
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]);
}
int[]
aInteger[]
Arrays.asList
métodoBarajar con Collections.shuffle
método
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]
El código más simple para barajar:
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));
}
}
Usando la clase aleatoria
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
}
}
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);
}
}
similar sin usar 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);
Una de las soluciones es usar la permutación para precalcular todas las permutaciones y almacenarlas en ArrayList
Java 8 introdujo un nuevo método, ints (), en la clase java.util.Random. El método ints () devuelve una secuencia ilimitada de valores int pseudoaleatorios. Puede limitar los números aleatorios entre un rango específico proporcionando los valores mínimo y máximo.
Random genRandom = new Random();
int num = genRandom.nextInt(arr.length);
Con la ayuda de generar el número aleatorio, puede iterar a través del bucle e intercambiar con el índice actual con el número aleatorio. Así es como puede generar un número aleatorio con complejidad de espacio O (1).
Sin solución aleatoria:
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));
}
List<int[]>
entrada que contenga una. Vea mi respuesta para saber cómo lograr esto usandoCollections.shuffle()
.