Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Shuffle an array
501 views
Skip to first unread message
Kali
Dec 4, 2012, 7:48:13 AM12/4/12
to
Hi there
There is a vector
Real::A(100)
needs to be shuffled.
is there any subroutine that I can shuffle it for 1000 time?
Hadi
There is a vector
Real::A(100)
needs to be shuffled.
is there any subroutine that I can shuffle it for 1000 time?
Hadi
e p chandler
Dec 4, 2012, 8:18:22 AM12/4/12
to
> "Kali" wrote
select K from 1..J
swap A[K] & A[J]
next J
> Hi there There is a vector Real::A(100) needs to be shuffled.
for J=N down to 2
select K from 1..J
swap A[K] & A[J]
next J
Arjen Markus
Dec 4, 2012, 8:18:47 AM12/4/12
to
1. It is not that difficult - presuming you have an idea on how to shuffle
the data
2. What have you tried so far?
3. Is this a homework assignment? It has the smell of one and if not, it
should not be that difficult to come with something. But you will have
to show interest in solving the problem yourself - we can help but we
do not want to do the job for you.
Regards,
Arjen
Kali
Dec 4, 2012, 8:31:00 AM12/4/12
to
thanks for response but the answer is not clear for me.
Kali
Dec 4, 2012, 8:55:26 AM12/4/12
to
You are right in a sense that I need to solve the problem myself but I am involved in other problems of my project and for this part putting effort won't be beneficial to spend a time on solving it. I am biology student and programming is not our main concern and what I need is just a shuffled vector! So please provide me with the answer and let me to focus on hundreds of problems that I have in other parts of my project! Otherwise I will do it in R!
Best!
gmail-unlp
Dec 4, 2012, 9:05:31 AM12/4/12
to
> Dear e p chandler
> thanks for response but the answer is not clear for me.
Fernando.
Arjen Markus
Dec 4, 2012, 9:22:14 AM12/4/12
to
what you want.
As e p chandler already wrote very concisely:
- Pick two integers (I and J) within the range 1 to 100 (the size of your array)
- You can use the random_number subroutine to get a random number between
0 and 1.
- Then interchange the array elements A(I) and A(J)
- Repeat this a fair number of times
- The result is a random array
I do not provide the code - I too have many things to do. And you will
have to know how to compile and link a program, not to mention to pick up
the data you want to shuffle and to pass them on to the next step.
Maybe R is more convenient for you. Even though that does not free you
from programming tasks either.
Regards,
Arjen
Nasser M. Abbasi
Dec 4, 2012, 9:36:14 AM12/4/12
to
On 12/4/2012 8:22 AM, Arjen Markus wrote:
> Maybe R is more convenient for you. Even though that does not free you
> from programming tasks either.
Hi,
> Maybe R is more convenient for you. Even though that does not free you
> from programming tasks either.
I do not know R very well myself, but in octave/matlab this
is trivial. Just use randperm(N) which generates a random
permutation of numbers from 1 to N. (Fortran does not have
this build-in?) then one can use these as an index into
the vector to shuffle it.
------------
V = rand(100,1);
V = V(randperm(100));
-------------
To do this 100 times is easy. (Another one line)
--Nasser
e p chandler
Dec 4, 2012, 10:25:44 AM12/4/12
to
On Tuesday, December 4, 2012 8:31:00 AM UTC-5, Kali wrote:
> On Tuesday, December 4, 2012 2:18:22 PM UTC+1, e p chandler wrote:
> > > "Kali" wrote
> > > Hi there There is a vector Real::A(100) needs to be shuffled.
> > for J=N down to 2
> > select K from 1..J
> > swap A[K] & A[J]
> > next J
> On Tuesday, December 4, 2012 2:18:22 PM UTC+1, e p chandler wrote:
> > > "Kali" wrote
> > > Hi there There is a vector Real::A(100) needs to be shuffled.
> > for J=N down to 2
> > select K from 1..J
> > swap A[K] & A[J]
> > next J
> thanks for response but the answer is not clear for me.
It's "pseudo-code", not Fortran.
-- e
Robin Vowels
Dec 4, 2012, 6:53:27 PM12/4/12
to
On Dec 5, 12:55 am, Kali <kaviani.sa...@gmail.com> wrote:
> You are right in a sense that I need to solve the problem myself but I am involved in other problems of my project and for this part putting effort won't be beneficial to spend a time on solving it.
It will be beneficial, because you will solve your problem.
> You are right in a sense that I need to solve the problem myself but I am involved in other problems of my project and for this part putting effort won't be beneficial to spend a time on solving it.
> I am biology student and programming is not our main concern and what I need is just a shuffled vector! So please provide me with the answer and let me to focus on hundreds of problems that I have in other parts of my project! Otherwise I will do it in R!
Michel Olagnon
Dec 5, 2012, 6:00:23 AM12/5/12
to
Kali �crivit :
For instance, generate 100 random values, rank them, and take the values
of A in the order that comes out of the ranking. Not optimal, but fun.
of A in the order that comes out of the ranking. Not optimal, but fun.
Ron Shepard
Dec 5, 2012, 12:31:11 PM12/5/12
to
In article <ai8nq8...@mid.individual.net>,
Michel Olagnon <mola...@ifremer-a-oter.fr> wrote:
> Kali écrivit :
This would require N*log(N) or N^2 effort, depending on how the sort
is done. That is too much work. This is outside of my field, but I
think the previous algorithm based in pairwise swaps is probably the
right approach. It requires only N effort. However, I think you
need to be careful with boundaries so that every element has an
equal chance of being swapped. The first approach I thought about
would have resulted in smaller probabilities for the two end values
than for the internal values.
$.02 -Ron Shepard
Michel Olagnon <mola...@ifremer-a-oter.fr> wrote:
> Kali écrivit :
is done. That is too much work. This is outside of my field, but I
think the previous algorithm based in pairwise swaps is probably the
right approach. It requires only N effort. However, I think you
need to be careful with boundaries so that every element has an
equal chance of being swapped. The first approach I thought about
would have resulted in smaller probabilities for the two end values
than for the internal values.
$.02 -Ron Shepard
dpb
Dec 5, 2012, 12:56:32 PM12/5/12
to
function p = randperm(n);
%RANDPERM Random permutation.
% RANDPERM(n) is a random permutation of the integers from 1 to n.
% For example, RANDPERM(6) might be [2 4 5 6 1 3].
%
% Note that RANDPERM calls RAND and therefore changes RAND's state.
%
% See also PERMUTE.
% Copyright 1984-2000 The MathWorks, Inc.
% $Revision: 5.8 $ $Date: 2000/06/02 17:59:27 $
[ignore,p] = sort(rand(1,n));
>>
Unless the array is very large or the call is nested very deep the
overhead is probably not a killer.
I haven't looked for an optimal implementation at NETLIB, etc., but
expect there's something there...
--
e p chandler
Dec 5, 2012, 5:48:16 PM12/5/12
to
> "Ron Shepard" wrote
>> Michel Olagnon wrote:
the TOP of the pile that is being shuffled moves downward by 1 at each step.
What this does is to select one item from those remaining with equal
probability and put it on the top of the pile. The swap is just an elegant
way to select an item and fill the hole vacated by its selection at the same
time. The remaining items are now in a different order (almost all of the
time) but that does not matter because each of them will be chosen at the
next step with equal probability.
-- e
>> Michel Olagnon wrote:
>>> Kali wrote:
>>> vector Real::A(100) needs to be shuffled.
>>> is there any subroutine that I can shuffle it for 1000 time?
>>> vector Real::A(100) needs to be shuffled.
>>> is there any subroutine that I can shuffle it for 1000 time?
>> For instance, generate 100 random values, rank them, and take the values
>>of A in the order that comes out of the ranking. Not optimal, but fun.
> This would require N*log(N) or N^2 effort, depending on how the sort
> is done. That is too much work. This is outside of my field, but I
> think the previous algorithm based in pairwise swaps is probably the
> right approach. It requires only N effort. However, I think you
> need to be careful with boundaries so that every element has an
> equal chance of being swapped. The first approach I thought about
> would have resulted in smaller probabilities for the two end values
> than for the internal values.
If you look at the pseudo-code that I originally posted, you will see that
>>of A in the order that comes out of the ranking. Not optimal, but fun.
> This would require N*log(N) or N^2 effort, depending on how the sort
> is done. That is too much work. This is outside of my field, but I
> think the previous algorithm based in pairwise swaps is probably the
> right approach. It requires only N effort. However, I think you
> need to be careful with boundaries so that every element has an
> equal chance of being swapped. The first approach I thought about
> would have resulted in smaller probabilities for the two end values
> than for the internal values.
the TOP of the pile that is being shuffled moves downward by 1 at each step.
What this does is to select one item from those remaining with equal
probability and put it on the top of the pile. The swap is just an elegant
way to select an item and fill the hole vacated by its selection at the same
time. The remaining items are now in a different order (almost all of the
time) but that does not matter because each of them will be chosen at the
next step with equal probability.
-- e
Terence
Dec 5, 2012, 6:45:02 PM12/5/12
to
Look for the Donald E. Knuth "Fundamental Algortithms", volume three, on
'sorting and searching techniques'. He covers most of the optimum methods.
Three of which are the heap sort; the partition sort; and the sort-merge
class of operations, my favorite of which class has elegance in the
repeated merging of already-sorted power-of-two blocks which double in size
with each merge pass . I use this for very large sorts (e.g. census data),
using multiple temporary work files.
'sorting and searching techniques'. He covers most of the optimum methods.
Three of which are the heap sort; the partition sort; and the sort-merge
class of operations, my favorite of which class has elegance in the
repeated merging of already-sorted power-of-two blocks which double in size
with each merge pass . I use this for very large sorts (e.g. census data),
using multiple temporary work files.
glen herrmannsfeldt
Dec 5, 2012, 9:08:13 PM12/5/12
to
Ron Shepard <ron-s...@nospam.comcast.net> wrote:
(snip)
> Michel Olagnon <mola...@ifremer-a-oter.fr> wrote:
(snip)
actually is. For small N it shouldn't be bad, and even
for medium or large N, not so bad.
> This is outside of my field, but I think the previous
> algorithm based in pairwise swaps is probably the right approach.
> It requires only N effort.
Hmm. Seems to me that it should be more than O(N) to get
a good amount of randomness. There are O(N**2) pairs, but
I might believe that O(N logN) swaps are enough.
> However, I think you need to be careful with boundaries so that
> every element has an equal chance of being swapped.
> The first approach I thought about would have resulted in
> smaller probabilities for the two end values than for the
> internal values.
It isn't bad to be sure that every element has an equal chance to
be swapped, but I don't believe that is necessary. All that is
needed is for each to have an equal probaility of ending up in
any position.
Well, equal probability of ending in each position isn't all,
but it isn't necessary that the swap rates be equal. Some
swap patterns could generate correlations in positions that
would not be very random.
-- glen
(snip)
> Michel Olagnon <mola...@ifremer-a-oter.fr> wrote:
(snip)
>> For instance, generate 100 random values, rank them, and take the values
>> of A in the order that comes out of the ranking. Not optimal, but fun.
> This would require N*log(N) or N^2 effort, depending on how the sort
> is done. That is too much work.
Since N isn't given, it is hard to say how much work it
>> of A in the order that comes out of the ranking. Not optimal, but fun.
> This would require N*log(N) or N^2 effort, depending on how the sort
> is done. That is too much work.
actually is. For small N it shouldn't be bad, and even
for medium or large N, not so bad.
> This is outside of my field, but I think the previous
> algorithm based in pairwise swaps is probably the right approach.
> It requires only N effort.
a good amount of randomness. There are O(N**2) pairs, but
I might believe that O(N logN) swaps are enough.
> However, I think you need to be careful with boundaries so that
> every element has an equal chance of being swapped.
> The first approach I thought about would have resulted in
> smaller probabilities for the two end values than for the
> internal values.
be swapped, but I don't believe that is necessary. All that is
needed is for each to have an equal probaility of ending up in
any position.
Well, equal probability of ending in each position isn't all,
but it isn't necessary that the swap rates be equal. Some
swap patterns could generate correlations in positions that
would not be very random.
-- glen
michael...@compuserve.com
Dec 6, 2012, 3:18:26 AM12/6/12
to
http://coding.derkeiler.com/Archive/Fortran/comp.lang.fortran/2006-03/msg00748.html might be of interest in this context.
Regards,
Mike Metcalf
Regards,
Mike Metcalf
michael...@compuserve.com
Dec 6, 2012, 4:54:37 AM12/6/12
to
For small N, I use:
call random_number(numbers)
do ii = 1, rank2
index = minloc(numbers, dim=1)
one_nine(ii) = index
numbers(index) = 2.0
end do
where numbers is size rank2 and real, and one_nine is size rank2 and integer. It packs the heavy lifting into an intrinsic function.
Regards,
Mike Metcalf
call random_number(numbers)
do ii = 1, rank2
index = minloc(numbers, dim=1)
one_nine(ii) = index
numbers(index) = 2.0
end do
where numbers is size rank2 and real, and one_nine is size rank2 and integer. It packs the heavy lifting into an intrinsic function.
Regards,
Mike Metcalf
0 new messages