En el món de la programació, manipular matrius és una habilitat fonamental. Es pot barrejar una matriu, que inclou la reordenació aleatòria dels seus elements, com un procés comú. Aquest procediment és essencial per a coses com la creació de taules de joc aleatòries, l'execució de simulacions estadístiques o simplement mostrar dades de manera més aleatòria. Inicialment, hi ha molta lògica que podem aplicar per barrejar una matriu; podem utilitzar diferents tipus de marcs de col·lecció com ara ArrayList, conjunts hash, llistes enllaçades, etc. La barreja d'una matriu es pot fer de manera diferent i
Algorisme per barrejar una matriu:
El següent és l'algorisme per a la barreja d'una matriu,
PAS 1: COMENÇAR
PAS 2: Comenceu des de l'últim element de la matriu i aneu enrere al primer element.
PAS 3: Per a cada element de l'índex i, genereu un índex aleatori j tal que j estigui en el rang [0, i].
PAS 4: Canvia els elements dels índexs i i j.
PAS 5: Repetiu els passos 2 i 3 per a tots els elements de la matriu, retrocedint des de l'últim element fins al primer.
PAS 6: FINAL
Podem barrejar una matriu que contingui diferents tipus d'elements com nombres enters, caràcters, etc.
Algoritme de barreja de Fisher-yates:
El següent programa Java s'utilitza per barrejar una matriu formada per nombres enters.
ArrayShuffle.java
import java.util.Random; public class ArrayShuffler { public static void main(String[] args) { // Sample array of integers int[] array = {1, 2, 3, 4, 5}; // Shuffle the array shuffleArray(array); // Print the shuffled array for (int num : array) { System.out.print(num + ' '); } } public static void shuffleArray(int[] array) { Random rand = new Random(); for (int i = array.length - 1; i > 0; i--) { // Generate a random index between 0 and i (inclusive) int j = rand.nextInt(i + 1); // Swap the elements at indices i and j int temp = array[i]; array[i] = array[j]; array[j] = temp; } } } Sortida:
1 3 2 4 5
La sortida pot ser diferent si l'executeu al vostre sistema perquè organitza els elements de manera aleatòria i genera la matriu barrejada.
Complexitats:
La complexitat espacial de l'algorisme de barreja és O(1) perquè no utilitza cap estructura de dades addicional que depengui de la mida de la matriu. La complexitat temporal de l'algorisme de barreja de Fisher-Yates utilitzat en el mètode shuffleArray() és O(n), on n és el nombre d'elements de la matriu.
Remenatge de matrius mitjançant llistes a Java:
ShuffleArray.java
import java.util.Arrays; import java.util.Collections; import java.util.List; public class ShuffleArray { public static void main(String[] args) { Integer[] intArray = {1, 2, 3, 4, 5, 6, 7}; List intList = Arrays.asList(intArray); Collections.shuffle(intList); intList.toArray(intArray); // This line will not resize the array System.out.println(Arrays.toString(intArray)); } } Sortida:
[4, 1, 7, 3, 6, 5, 2]
La sortida pot ser diferent si l'executeu al vostre sistema perquè organitza els elements de manera aleatòria i genera la matriu barrejada.
Complexitats:
programació dinàmica
La complexitat espacial també és O(n). Això es deu al fet que el mètode Collections.shuffle() modifica la llista original al seu lloc i no utilitza cap estructura de dades addicional. La complexitat temporal d'aquest codi és O(n), on n és el nombre d'elements de la matriu.
Barreja la matriu que conté caràcters:
ShuffleCharacters.java
import java.util.Arrays; import java.util.Random; public class ShuffleCharacters { public static void main(String[] args) { char[] charArray = {'a', 'b', 'c', 'd', 'e', 'f', 'g'}; shuffleArray(charArray); System.out.println('Shuffled Characters: ' + Arrays.toString(charArray)); } public static void shuffleArray(char[] array) { Random rand = new Random(); for (int i = array.length - 1; i > 0; i--) { int j = rand.nextInt(i + 1); // Swap characters at indices i and j char temp = array[i]; array[i] = array[j]; array[j] = temp; } } } Sortida:
Shuffled Characters: [e, f, g, d, a, c, b]
La sortida pot ser diferent si l'executeu al vostre sistema perquè organitza els elements de manera aleatòria i genera la matriu barrejada.
Complexitats:
La complexitat espacial de l'algoritme de barreja és O(1) perquè no utilitza cap estructura de dades addicional que depengui de la mida de la matriu. La complexitat temporal del programa utilitzat en el mètode shuffleArray() és O(n), on n és el nombre de caràcters de la matriu.
Conclusió:
Barrejar una matriu a Java és una habilitat crucial que permet als desenvolupadors crear arranjaments de dades aleatoris i imparcials. Al llarg d'aquesta exploració, hem tractat dos enfocaments efectius: utilitzar el mètode Collections.shuffle() per a matrius no primitives i implementar l'algoritme de barreja de Fisher-Yates per a matrius primitives. El mètode Collections.shuffle() simplifica el procés de barreja d'objectes o matrius no primitives aprofitant les funcionalitats integrades. D'altra banda, l'algorisme de Fisher-Yates proporciona una manera eficaç i imparcial de barrejar matrius primitives, assegurant la uniformitat en les permutacions.