Randomise Array

[gobeirne]

Hello all,

I was wondering if anyone knows the most efficient method of randomising a 1-D array?

I've attached the solution that I came up with, but there has to be a better way, surely!

Download File:post-3796-1145484802.vi

Many thanks,

Dr Greg O'Beirne

Christchurch, NZ

[Yair]

Efficient how? Memory? Speed?

I don't think there is any way to do this without using 2 array buffers (one for the input and one for the output), which is what you're doing.

I think LV might be clever enough in its newer versions to detect that you're not actually doing anything with the top array and will probably reuse its buffer. Other than this method (which should only be a problem when handling large arrays), the only viable method I can think of would be passing the array to a DLL with an efficient C algorithm, but I'm not sure the overhead will justify it.

[Kurt Friday]

Hi Greg

Perhaps a better way may be to shuffle your array.

Download File:post-1058-1145521987.vi

[Kurt Friday]

An even more efficient method of the shuffle, just randomly select two elements and swap their locations.

Download File:post-1058-1145537823.vi

[Yair]

An even more efficient method of the shuffle, just randomly select two elements and swap their locations.

Nice. I actually figured out the shuffle way as well, but the main problem with both methods is that they're only "quasi random" (they have an inherent order) and a cryptographer friend of mine told me once that these kinds of methods are not considered good enough for cryptography. For other purposes, however, they should be good enough (especially if memory allocation is in mind) and I will try to remember the second one.

[crelf]

...the main problem with both methods is that they're only "quasi random"...

<Physicist Hat>

All "random" patterns are quasi-random: there's no such thing as completely random, only degrees of quasi-random...

</Physicist Hat>

[Guenther]

Here is another one:

Bundle your array elements with a random number as first element, sort the resulting cluster array, and then throw away the random number.

[Yair]

<Physicist Hat>

All "random" patterns are quasi-random: there's no such thing as completely random, only degrees of quasi-random...

</Physicist Hat>

I know, only in this case, using the third method in 7.0 with an array of 10,000 elements leaves 1300-1400 of the elements in their original locations, which is a rather large margin of error (13 percent). Since this method is based on the random number generator and the number is around this range every time I run the VI it seems reasonable to assume that this is a property of the random number generation which is reflected through using this method.

The method suggested by Guenther is fast, random and elegant and appears to be the best solution.

Download File:post-1431-1145547234.vi

[crelf]

I know, only in this case, using the third method in 7.0 with an array of 10,000 elements leaves 1300-1400 of the elements in their original locations, which is a rather large margin of error (13 percent).

That because using a quasi-random method to select which ones are going to be moved means that some won't be moved at all, some will be moved once, others will be moved twice, etc... I wouldn't call this a "margin of error" - just because a number remains in its' original location doesn't mean that it's an error at all. It's more of a ratio of the quasi-random nature of the process relative to a true random process, which by its' very nature doesn't exist, and you can't test for it anyway

That said, I like the "cluster random" method of assigning a quasi-random number with each of those in your sample set - at least this means that the position of your samples has less (sort of) effect on where they'll end up - I think this is probably as good as you'll get.

[jpdrolet]

That because using a quasi-random method to select which ones are going to be moved means that some won't be moved at all, some will be moved once, others will be moved twice, etc... I wouldn't call this a "margin of error" - just because a number remains in its' original location doesn't mean that it's an error at all. It's more of a ratio of the quasi-random nature of the process relative to a true random process, which by its' very nature doesn't exist, and you can't test for it anyway

That said, I like the "cluster random" method of assigning a quasi-random number with each of those in your sample set - at least this means that the position of your samples has less (sort of) effect on where they'll end up - I think this is probably as good as you'll get.

Well if I measure the Cosmic Background Radiation and shuflle that with the particle count/s of a radioactive substance and XOR with alfa's posts, I'll get data with no discernable pattern for sure... :laugh:

[Yair]

That because using a quasi-random method to select which ones are going to be moved means that some won't be moved at all, some will be moved once, others will be moved twice, etc...

Yes, but why is it always around 13.5% which aren't moved? I assume this is because of some property of the random number generator which I don't feel like testing at the moment.

I wouldn't call this a "margin of error"

Neither would I.

Oh... I already did...

However, since time is bidirectional (or is it quasi-directional? ), let's pretend I didn't do that yet.

[Guillaume Lessard]

An even more efficient method of the shuffle, just randomly select two elements and swap their locations.

If you randomly select only one of the two elements, everything will be fine.

1. Select first element with the loop counter

2. Select second element randomly

3. Swap them.

Works with no extra buffer allocation!

Download File:post-3022-1145556103.vi

I would think that this is equivalent to the "cluster shuffle", but I don't really want to try and prove it...

Guillaume Lessard

P.S. this tends to be the algorithm you find upon googling "array shuffle"...

[crelf]

I'll get data with no discernable pattern for sure...

Depends on you definition of "descernable"

However, since time is bidirectional (or is it quasi-directional? ), let's pretend I didn't do that yet.

Didn't do what? I didn't see anything

[Chris Davis]

Depends on you definition of "descernable"

Didn't do what? I didn't see anything

Since this post mentions alfa, shouldn't we begin discussing beer? :thumbup:

[crelf]

I would think that this is equivalent to the "cluster shuffle", but I don't really want to try and prove it...

:thumbup: Very nice! Yep - this is an excellent solution, statistically equivalent to the pervious solution, faster and more memory efficient too!

crelf says "Five :star:s - A must see!"

...shouldn't we begin discussing beer? :thumbup:

Well done - you've invoked Kring's Law - you win!

[Guillaume Lessard]

:thumbup: Very nice! Yep - this is an excellent solution, statistically equivalent to the pervious solution, faster and more memory efficient too!

I couldn't help wondering if the two really are statistically equivalent. They happen to be the two shuffling algorithms popularized by Knuth. See this.

I'm perfectly willing to take Knuth's word on algorithm correctness!

Guillaume Lessard

[crelf]

I'm perfectly willing to take Knuth's word on algorithm correctness!

Indeed!

There's some theory that may be of interest here.

[jpdrolet]

If you randomly select only one of the two elements, everything will be fine.

1. Select first element with the loop counter

2. Select second element randomly

3. Swap them.

Works with no extra buffer allocation!

Download File:post-3022-1145556103.vi

I would think that this is equivalent to the "cluster shuffle", but I don't really want to try and prove it...

Guillaume Lessard

P.S. this tends to be the algorithm you find upon googling "array shuffle"...

I think that this shuffling is biased. There is a random number generation between 0 and N-1 but because of rounding the elements 0 and N-1 have half the probability to be picked than other numbers. It should be a random number between 0 and N then floored to integer. The index N won't be picked because the random number function is always lower than 1.0

Edit: it is based on the picture posted, I can't see Guillaume Leassard's VI since it is in 8.0

[Phillip Brooks]

While looking up an old friend, I came across this link.

I'm not sure if it is the same Les Peters, but he did work with LabVIEW and RF communcations.

One of the problems I have been faced with in developing a CM automated test solution has been the creation of an encryption quality random number. This random number is used as a seed for generating a secure ID string which is then programmed into each modem. A colleague of mine having found your web site http://www.aw-el.com, suggested I look into your Radiation Monitors as one of its features was the generation of random numbers. After reading all the information on your website and talking with you about my specific application I purchased one of your model #RM-60 Radiation Monitors. I must say at first my colleagues and I were a little skeptical having little experience with Radiation Monitors. But after some investigation we realized that the decay of radioactive matter being unpredictable actually provided a very good means to generate an extremely random number.

Your original "AW-RAND.EXE" software supplied with the monitor while displaying the data on my PCs monitor did not allow us to port the data to a text file. After having discussed this problem with you, you quickly made a change to your source code sending the generated data to a text file. You then E-mailed the new code to me within several hours, now that's service ! While this solved one issue generation of random numbers was slow using background radiation. Your suggestion of using the AM241 element out of an inexpensive ionization type of smoke alarm solved that problem, now numbers are generated very quickly.

My test software is written in a graphical programming language called LABVIEW and integrating your "AW-RAND.EXE" required the creation of a driver. This driver allows execution of your "AW-RAND.EXE" code using the supported arguments on the same command line. The driver was designed using the LABVIEW 5.0 Full development for WINDOWS 95/NT. I have attached a copy of this driver so that some of your other customers can use it. I feel it is the least I can do with all the help that you have given me.

http://www.aw-el.com/random.htm

[Guillaume Lessard]

I think that this shuffling is biased. There is a random number generation between 0 and N-1 but because of rounding the elements 0 and N-1 have half the probability to be picked than other numbers. It should be a random number between 0 and N then floored to integer. The index N won't be picked because the random number function is always lower than 1.0

Edit: it is based on the picture posted, I can't see Guillaume Leassard's VI since it is in 8.0

Sorry about the lack of picture. I didn't really try to post a screen shot at first.

GL

Is there a really easy way to get a picture of the block diagram from within labview? something easier than printing to HTML, that is...

[jpdrolet]

Sorry about the lack of picture. I didn't really try to post a screen shot at first.

GL

Is there a really easy way to get a picture of the block diagram from within labview? something easier than printing to HTML, that is...

Look at this NI Forum thread. There is a tool to save a picture of the diagram and copy its path to the clipboard, ready to paste in the File Attachment field. Check also for the hack needed to make it work in LV8. :thumbup:

In the VI you could expand Replace Array Subset to two inputs instead of using two nodes.

[gobeirne]

Thanks very much to everyone who has replied in this thread! The proposed solutions (particularly Guillaume's) are superb and particularly elegant - cheers!!

Greg.

[Guillaume Lessard]

Look at this NI Forum thread. There is a tool to save a picture of the diagram and copy its path to the clipboard, ready to paste in the File Attachment field. Check also for the hack needed to make it work in LV8. :thumbup:

Thanks JP!!

Now, at the risk of beating a nearly-dead horse to a shapeless pulp, I realized that the diagram I posted earlier does, in fact, produce a biased result. Upon carefully reading Knuth's shuffling algorithm, I realized that the correct diagram is:

Thou shall shuffle each cell only once.

Now we can all go have :beer:, because the code is both correct and efficient.

GL

[crelf]

Is there a really easy way to get a picture of the block diagram from within labview? something easier than printing to HTML, that is...

Windows: click on the window that you want an image of and press Alt+PrintScrn - this'll put a screen shot of the selected window on to your clipboard and then you can paste it into your favorite image editing / saving tool.

[gobeirne]

Now we can all go have :beer:, because the code is both correct and efficient.

GL

Cheers Guillaume!

G.