Shuffling an array?

So I thought I would build an encryption system that can be used to hide value data from the evil hex-code editors... Things are going ok, but I cant find an efficient way to sort an array without using multiple for() loops. Is there a simple way to randomize array values? I initialy used a for() loop to pull a random value out of the initial array and place it in a buffer array that holds temp values. When the buffer fills it is copied onto the origional array and cleared. The problem with the way I did it is that it created duplicates... Is there an easier, more efficient way to randomize an array?

JS please...

 

Perhaps if you can give an example of what you're trying to accomplish there might be a better way.

Simple bit twiddling and separating the displayed from the real value is more than enough to protect against memory editor hacks. What sort of data are you trying to protect that involves expensive tasks such as sorting, randomizing and copying arrays?

 

Personaly I would use it for saving XML data to the client's computer. It realy isn't too expensive, the randomizing will only be executed at game initialization.

I have an array with a length of 94. What I need to do is shuffle the array, without creating duplicates.

 

http://forum.unity3d.com/viewtopic.php?t=31799

Try this. Andeeeee's old posts are like a goldmine.

 

Thanks, that solved it.

Thanks to Andeeeee for sharing his code!

 

Having trouble with this. I have two arrays, array1 and array2. As far as I can tell, this should set array2 = array1, then randomize array2 and leave array1 alone. This is not happening... I'm not sure what is going wrong, the code makes sense to me. :?

Code (csharp):

1. function ShuffleArray()     // Ends up randomizing array1...
2. {
3.     if (doOnce4 == true)
4.     {
5.         array2 = array1;
6.         var temp;      
7.         for (var i = 0; i < array2.length; i++)
8.         {
9.             temp = array2[i];          
10.             var swapIndex = Random.Range(0,(array2.length - 1));
11.             array2[i] = array2[swapIndex];
12.             array2[swapIndex] = temp;
13.         }
14.         Debug.Log(array1);
15.         doOnce4 = false;
16.     }
17. }

 

That makes array2 be a pointer to array1, so anything that happens to array1 also happens to array2, since they are the same thing and not two separate arrays.

--Eric

 

Code (csharp):

1.  
2. var j = 94;
3.     for (i = 0; i < j; i++) {
4.         var rand:int = Random()*j;
5.         shuffled_arr[i] = main_arr.RemoveAt(rand);
6.         j--;
7.     }
8.  
9.  

Off the top of my head I shuffled cards with this but using splice which is not available in Unity. I think RemoveAt accomplishes the same thing.

HTH

 

Just came across this thread. I was too lazy to use the library so I wrote my own (Unity JavaScript) shuffle routine:

Code (csharp):

1. function Shuffle( size : int ) : int[] {
2.     var cards : int[] = new int[size];
3.     var r : int;
4.     var i : int;
5.     var temp : int;
6.    
7.     for( i = 0; i < size; i++ ){
8.         cards[i] = i;
9.     }
10.    
11.     for( i = 0; i < cards.length; i++ ){
12.         r = Random.Range(0, i);
13.         temp = cards[r];
14.         cards[r] = cards[i];
15.         cards[i] = temp;
16.     }
17.    
18.     return cards;
19. }

The idea is to use a shuffled array of ints to refer to some other array.

I can prove the result is correct by induction:

1) Obviously works for array of one element.
2) Assuming it works for arrays of n elements (i.e. you get an array where each element has a 1/n probability of being in each position) consider an array of n+1 elements:

When you get to the nth step the routine is (assumed to be) correct. So the final step has a 1/(n+1) chance of swapping the final element with any other element, so the probability the final element will end up in any position is 1/(n+1)

Now consider any element in the array of size n. The probability of it being in a given position m before the final step was 1/n. In the final step it has a n/(n+1) chance of staying put. So its probability of being at position m after the final step is 1/n * n/(n+1) or 1/(n+1).

QED and no dynamically resizing elements needed.

Yes I wasted way too much time on this, but it could be useful where performance is an issue (e.g. for shuffling big arrays)

 

Not the most efficient way peformance wise, but you could use the linq OrderBy method:

C# code.

Code (csharp):

1.  
2. System.Random randomGenerator = new System.Random();
3. array2 = array1.OrderBy(x => randomGenerator.Next(1, 1000)).ToArray();

Which will leave array1 as it was and set array2 to a new shuffled version. If that is what you want.

Edit: Didn't realise how old the original post was.

 

LOL.

I recently used that method - just be warned that the random number has to be large compared to the length of the array before it begins to appear random [and even then there is probably some statistical bias].

 

There is absolutely no way you'll "hide value data from the evil hex-code editors" without actual encryption. Shuffling arrays is not going to do it. The bad guys are way better than the good guys with this stuff.

 

While I agree, shuffling the data around in memory does knock out the first level of hex hacker.

However, since he doesn't seem to keep track of the different order, I don't see how he can use the data now, either... That, or it's just as useful to the 'hackers'.

 

If I'm searching a file (he mentions hex-code editors, so I'm just assuming) and I know I have 24,500 gold pieces, it doesn't matter where in the file that value is. CMD-F, 24,500, and busted. Forget level one, my dog could do that. But if it's stored as a0293^@*d10134 (pretend that's 24,500 encrypted) then I have a problem.

 

Guys, I'd modify the array shuffle function if I were you. It is not a true Fisher-Yates shuffle which makes it problematic, especially if it was used for card shuffling.

See this wikipedia article to correct it. http://en.wikipedia.org/wiki/Fisher–Yates_shuffle

See the part where it says "The modern algorithm"

Felt nice so here is the code to replace the Shuffle method.

Code (csharp):

1. public static void Shuffle<T>(T[] array)
2.     {
3.         int count = array.Length;
4.         for(int i = count-1; i > 0; --i)
5.         {
6.             int randIndex = Random.Range(0, i);
7.  
8.             T temp = array[i];
9.             array[i] = array[randIndex];
10.             array[randIndex] = temp;
11.         }
12.     }

 

i have wrapped the improved method into an extension method and made it for list as well as array.
note:
for many elements the string gets really long and unwieldy.
the display method uitilizes the tostring method so this should be overwritten by your objects in order to display meaningfull values.
important: the array/list itself is reordered so if you need to keep the original order only call the shuffle method on a copy of your list/array!

have fun.

Code (csharp):

1.  
2. using System.Collections.Generic;
3. using System.Text;
4.  
5. public static class ExtensionMethods_Collection
6. {
7.     public static void Shuffle<T> ( this List<T> list )
8.     {// shuffles the elements in the list randomly with knuth fischer yates shuffle, source: http://forum.unity3d.com/threads/46234-Shuffling-an-array, http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle, http://forum.unity3d.com/threads/29977-Randomising-shuffling-library
9.         int count = list.Count, i, randIndex;
10.         for (i = count - 1; i > 0; --i)
11.         {
12.             randIndex = Random.Range ( 0, i );  // note: shifts random elements to the foward going end so the order is determined in opposite direction, the elements choosen first are the last ones in the resulting list
13.             T temp = list[i];
14.             list[i] = list[randIndex];
15.             list[randIndex] = temp;
16.         }
17.     }
18.  
19.     public static void Shuffle<T> ( this T[] array )
20.     {// shuffles the elements in the list randomly with knuth fischer yates shuffle, source: http://forum.unity3d.com/threads/46234-Shuffling-an-array, http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle, http://forum.unity3d.com/threads/29977-Randomising-shuffling-library
21.         int count = array.Length, i, randIndex;
22.         for (i = count - 1; i > 0; --i)
23.         {
24.             randIndex = Random.Range ( 0, i );
25.             T temp = array[i];
26.             array[i] = array[randIndex];    // note: shifts random elements to the foward going end so the order is determined in opposite direction, the elements choosen first are the last ones in the resulting list
27.             array[randIndex] = temp;
28.         }
29.     }
30.  
31.     public static string ElementsToString<T>(this List<T> list)
32.     {// returns the elements of the list as a string (fe for output or debug)
33.         StringBuilder result = new StringBuilder(1024);
34.         int end = list.Count - 1;
35.         result.Append(string.Format("Elements: {0}  Content: {{ ", list.Count));
36.         for (int i = 0; i < list.Count; ++i)
37.         {
38.             result.Append ( list[i].ToString ( ) );
39.             if (i < end)
40.                 result.Append ( ", " );
41.         }
42.         result.Append("}");
43.         return result.ToString();
44.     }
45.  
46.     public static string ElementsToString<T>(this T[] array )
47.     {// returns the elements of the list as a string (fe for output or debug)
48.         StringBuilder result = new StringBuilder ( 1024 );
49.         int end = array.Length - 1;
50.         result.Append ( string.Format ( "Elements: {0}  Content: {{ ", array.Length ) );
51.         for (int i = 0; i < array.Length; ++i)
52.         {
53.             result.Append ( array[i].ToString ( ) );
54.             if (i < end)
55.                 result.Append ( ", " );
56.         }
57.         result.Append ( "}" );
58.         return result.ToString ( );
59.     }
60. }
61.  

usage:

Code (csharp):

1.  
2.     List<int> indices = new List<int>(10) {1,2,3,4,5,6,7,8,9,10};
3.     indices.Shuffle();
4.     Debug.Log(indices.ElementsToString());
5.  
6.     float[] values = new float[] {1.1f, 2.2f, 3.3f, 4.4f, 5.5f, 6.6f, 7.7f, 8.8f, 9.9f, 10.10f};
7.     values.Shuffle();
8.     Debug.Log(values.ElementsToString());
9.