Having an array like this:
var arr1 = ["a", "b", "c", "d"];
How could I change its order randomly ?
It would be nice to answer in a generic way to serve as an implementation example for any language
[Change the order of the array data within the array]
*The question originally asked about js and jQuery.
PS: This question already exists in the English version, but I found it interesting to take it up again and adapt it for Spanish-speaking users. I'll leave some time for people to provide an answer. If there are none, I will translate the most optimal answer and add contributions from the house.
WARNING
There is a very simple way to do it in javascript .
Explanation:
The function
Math.random()
returns a random number between 0 and 0.9999..., what we achieve by subtracting 0.5 is that it generates negative and positive numbers so that the functionsort()
re-orders the array randomly, placing one element in front of another behind.As it is a question that can have a different answer depending on the language, we are going to talk about algorithms, regardless of the language (one could even say that it can be done in a database).
One of the ways that I like the most to mix a vector (or get all its data out of order), and it is not completely performant but it works, is to generate a new mix vector, and combine them.
Let's say we have a vector of numbers (1,2,3...100) and we want to mix it. Each number has an index in the vector (in this case the index would be equal to the same number). We use an array with positions in the following way
And what we're going to do is, for each row of this matrix, generate a random number that goes in the order column. The random number generation must be large enough to cover the number of cases to be mixed.
That way, we could be left with something like this:
After this, we do a sort of this matrix, by the order column:
Note that if two positions have the same order, it doesn't matter, since they would still be mixing. Obviously you can use a random function that returns cases where there would be almost no collisions.
Once this process is finished, depending on the intended use of the original vector, the positions can be regenerated using the new order given by the matrix, or the necessary items can simply be removed in the order given by the new matrix.
I use this code in Android to permute an Array without repetition.
Other solutions provided depend on a call to
sort()
. If the language you are working with has that function implemented, it may be a good solution. However, if you work in languages that do not havesort()
, you would have to implement one yourself, which would unnecessarily complicate the problem. In addition, this solution would have complexity greater than O(N), since a loop of complexity O(N) is first necessary to generate the random numbers and then another of complexity O(N log(N)) to order them (assuming that the QuickSort sorting algorithm, which is one of the most optimal possible and the one that is implemented in most languages)-I have come up with another simple algorithm that does not depend on
sort()
and has O(N) complexity, which is the following:The algorithm starts from the following idea. Imagine you have a real deck of cards. A very simple way to mix them would be to randomly take cards from the deck and leave them on the table, one on top of the other. Once they are all on the table, they will be mixed. With each "iteration" of this loop, you have fewer cards left in your hand.
A literal simulation of this would be to take a random item from the list and move it to another array (the "table" where the cards are placed). Then, to complete the simulation that a card has been drawn, the original array must "shrink", which would be implemented by shifting all the elements of the original array back one position from the chosen element.
The algorithm I propose saves the shift, instead moving the last data in the list into the gap. This changes the original list each time an element is chosen, but it doesn't matter if it is out of order with respect to its initial state. We are shuffling! We also save the second list by using the list itself as the "table", in its final positions. It is therefore efficient in time and memory, by using a single list.
An implementation (for example in Python) would be:
Produces for example:
Edition
After doing some research, I discovered that (obviously) someone else had thought of the algorithm before :-) Specifically, it is the Fisher-Yates algorithm , popularized by Donald Knuth in his book The art of computer programming . It seems that it is a widely used algorithm, because it is optimal in space and execution time.