How to Re-order an Array

[atTheTopOfTheCheese]

What is it you are trying to achieve?
I need to re order an array, and save its randomized values.


What is the problem you are having?
I don?t know how to do that


Describe what you have tried to solve this problem
I?ve googled the problem, and tried using tony?s method to randomize the numbers without repeating.


Post any relevant code (You may choose to attach the file instead of posting the code if it is too long)

[syntax=?turing"]

var numbers : array 1 .. 10 of int := init (1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
var randomNumber : int

for decreasing i : 10 .. 1
randomNumber := Rand.Int (1, i)
put numbers (randomNumber)
numbers (randomNumber) := numbers (i)
end for

%I need to save these values in this order, so that if I call another for loop and type ?put numbers(i)?, it would output the numbers in the same order as ?put numbers(randomNumber)?

[/syntax]

Please specify what version of Turing you are using
4.11

[atTheTopOfTheCheese]

On a side note, why are my quotation marks appearing as question marks?

[Dreadnought]

atTheTopOfTheCheese wrote:

I need to re order an array, and save its randomized values.

I'm not sure I follow, once you have shuffled the array the values stay shuffled.

atTheTopOfTheCheese wrote:

Turing:

var numbers : array 1 .. 10 of int := init (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) var randomNumber : int for decreasing i : 10 .. 1     randomNumber := Rand.Int (1, i)     put numbers (randomNumber)     numbers (randomNumber) := numbers (i) end for %I need to save these values in this order, so that if I call another for loop and type ?put numbers(i)?, it would output the numbers in the same order as ?put numbers(randomNumber)?

Although your program outputs a properly shuffled sequence of numbers you end up with an array that isn't properly shuffled (in fact, it could end up containing only the number 10).
You need to swap the positions of numbers in your array, not just copy values around.

I'm pretty sure that what you refer to as "Tony's method" is the Fisher-Yates shuffle, look back at the description of the algorithm and look carefully at how the values in the array are manipulated.

EDIT: (about the quotation marks)
Did you type your post in a text editor? Text editors usually use curly quotation marks and curly apostrophe instead of the standard ASCII ones, since they aren't standard ASCII characters, they are being replaced by question marks indicating some sort of unknown symbol.

[atTheTopOfTheCheese]

Basically, I would like to shuffle the values in one array, and save the shuffled set/order of values in another array.
e.g. if the original array values were 1,2,3,4,5 [in that order] and I shuffled to make it 3,2,5,1,4, I want to save 3,2,5,1,4 to a new array.

I was trying to show how I attempted to transfer the array values to a new array, but my code didn?t work, so yeah.

The Fisher-Yates shuffle is interesting, I didn?t know that the shuffle had a name, but I called it Tony?s method because I saw it in the source code section, posted by Tony.

Yeah, I did I do that to avoid making errors, so I guess I?ll just type my entries here instead.

[np_123]

I will mention that the very last time the code in the for loop runs, when i=1, the code is kinda redundant as it will perform:

code:

numbers (1) := numbers (1)

This will be because there Rand.Int will result 1, making the only use of that iteration to output the value of numbers (1) to the screen.

As seen in the Fisher-Yates shuffle (in the Wikipedia article linked by Dreadnought) the loop in their exanple runs from the # of elements down to 1, but the key difference is that the array in there is zero-indexed

Extending Dreadnought's example, one could also end up with the exact same values in the same order, if by some small chance Rand.Int keeps resulting i

One way to do it using another array is to realize that in your starting array,you have numbers (i) equal to i
Therefore you could do something (in your for loop) along the lines

code:

new_array (randomNumber) := temp new_array (randomNumber) := new_array (i) new_array (i) := temp

EDIT: you might be best off using a temporary variable because the array would have to be initialized first and then the shuffle algorithm applied to swap positions. And your second array would have to be initialized as well...same as the first would work

(The main reason my posts are edited so much is that I can't for the life of me remember how to type in code tags while I'm doing the post)

[atTheTopOfTheCheese]

Thanks for the input, guys.

I?m not sure I quite understand, np_123.

What is the temporary value, and I still don?t understand the need for a temporary value.

Sorry if I seem confused, its just that this whole business of shuffling arrays is quite annoying, and I?d like to get it over with

[Raknarg]

Let's say you have two variables, and you want to switch their values around:

Turing:

var a : int := 5 var b : int := 7

How can we swap their values? We can start by saying a := b. But, now you lost the value of a, because they're both 7.

What you can do is introduce a temporary variable that you don't care about, all it does it hold a value for a little while. In this case, you can use a temp value to remember the value of a for you while you switch:

Turing:

var a : int := 5 var b : int := 7 var temp : int := a a := b b := temp

Now they are successfully switched.

What np_123 is doing is the same thing. He takes your array and picks two random values, and wants to swap them:

Turing:

var rand1 := Rand.Int(1, upper(numberArray)) var rand2 := Rand.Int(1, upper(numberArray)) var temp := numberArray(rand1) numberArray(rand1) := numberArray(rand2) numberArray(rand2) := temp

If you do this a bunch of times, your array will be shuffled.

[np_123]

The reason I mentioned a temporary value is that based on the Fisher-Yates shuffle, you need to swap positions of the variables.

To swap positions, you have to make sure that you don't overwrite the variables as such.

The code below is the Fisher-Yates shuffle, except you said you wanted a new shuffled array, keeping the initial intact
Try putting this in Turing and running this:

Turing:

var numbers : array 1 .. 10 of int := init (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) var new_array : array 1 .. 10 of int := init (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) var randomNumber : int var temp : int for decreasing i : 10 .. 2     randomNumber := Rand.Int (1, i)     temp := new_array (randomNumber)     new_array (randomNumber) := new_array (i)     new_array (i) := temp end for for i : 1 .. 10     put "Original Array   "..     put numbers (i)..     put "     Shuffled Array   "..     put new_array (i) end for

Make sure you understand what's going on in the code, don't just say it works, copy it, and move on!!

[atTheTopOfTheCheese]

Thanks for your help!

Using your code, I found a more efficient way of doing it, and I thought I?d post it here.

var num : array 1 .. 5 of int := init (1,2,3,4,5)
var randNum : int := 0

var randArr : array 1..5 of int

for decreasing i : 5 .. 1
randNum := Rand.Int (1, i)
put num (randNum)
randArr(i) := num (randNum) % Storing the randomized number into the randArr
num (randNum) := num (i)
end for

[np_123]

Using your code, randArr is shuffled, containing numbers 1-5 in random order (the intended purpose)

However, the array num is neither left intact nor shuffled - in fact it makes that array quite pointless, you could get the same net result for randArr using only one array. The question I have is whether you planned using the array num again of if the whole purpose was to create the shuffled array.

that is one of the things that differentiates the code I posted and yours. Whenever you write code, you should keep an eye out for side effects when you try to take shortcuts

If you needed to use both arrays later on in a program, your method would not work

also, when you post code in the future, use syntax tags, or code tags, for it will make it much easier to follow