Shuffle Method

Ruby
1

Once again, hello

Normally I’d go to my dad for something like this. But since he’s out
and you all are hyperactive posters…

I’ve been writing my own shuffling method, and I end up getting
doubles in it.
For instance, output might say something like:
fun
cat
zoo
zoo

Now, it’s NOT supposed to do that, but it does anyways. I am clueless
as to what the problem is. What I DID notice, however (When using
source 2) was that it seemed to pop off the last item in the array.
Repeatedly. Yes, it’s supposed to do that, but the last item changes
each time. How does it keeping popping off, say, ‘fun’ repeatedly?

Lotsa source code here, but I appreciate the help. Thanks
ridonculously a lot.

--------------------------------------------------------------|
SOURCE 1
--------------------------------------------------------------|
some_array= [‘cat’, ‘dog’, ‘fun’, ‘zoo’]

def shuffle some_array
recurssive_shuffle some_array
end

def recurssive_shuffle some_array
n = some_array.length
helper_array = []
new_array = []
while n != 0
r = rand(n)
while some_array.length != (r + 1)
helper_array.push some_array.pop
end
new_array.push some_array.pop
n = (n - 1)
helper_array.each do |item|
some_array.push item
end
end
puts new_array
end

shuffle some_array
--------------------------------------------------------------|
SOURCE 2
--------------------------------------------------------------|
some_array = [‘cat’, ‘dog’, ‘fun’, ‘zoo’]

def shuffle some_array
recurssive_shuffle some_array
end

def recurssive_shuffle some_array
n = some_array.length
helper_array = []
new_array = []
while n != 0
r = rand(n)
while some_array.length != (r + 1)
helper_array.push some_array.pop
puts ‘Array’
puts helper_array
puts
end
new_array.push some_array.pop
n = (n - 1)
helper_array.each do |item|
some_array.push item
end
end
puts new_array
end

shuffle some_array

---------------------------------------------------------------|
~Ari
“I don’t suffer from insanity. I enjoy every minute of it” --1337est
man alive

2

Why not just do a random sort instead?

some_array = [‘cat’, ‘dog’, ‘fun’, ‘zoo’]
=> [‘cat’, ‘dog’, ‘fun’, ‘zoo’]

some_array.sort { rand(3) - 1 }
=> [“zoo”, “dog”, “fun”, “cat”]

3

On Sunday 22 April 2007 23:15, eden li wrote:

Why not just do a random sort instead?

some_array = [‘cat’, ‘dog’, ‘fun’, ‘zoo’]
=> [‘cat’, ‘dog’, ‘fun’, ‘zoo’]

some_array.sort { rand(3) - 1 }
=> [“zoo”, “dog”, “fun”, “cat”]

Or some_array.sort_by { rand }

4

eden li [email protected] writes:

Why not just do a random sort instead?

some_array = [‘cat’, ‘dog’, ‘fun’, ‘zoo’]
=> [‘cat’, ‘dog’, ‘fun’, ‘zoo’]
some_array.sort { rand(3) - 1 }
=> [“zoo”, “dog”, “fun”, “cat”]

That doesn’t result in a good shuffle. For example, if I shuffle
the array [“a”, “b”, “c”], I expect that “a” will be equally likely to
end up in any given position. However:

irb(main):038:0> a = (‘a’…‘c’).to_a
=> [“a”, “b”, “c”]
irb(main):039:0> d = Hash.new{|h,k|h[k]=0}
=> {}
irb(main):040:0> (1…27_000).each{ d[a.sort { rand(3) - 1 }.index(“a”)]
+= 1}
=> 1…27000
irb(main):041:0> p d
{0=>13940, 1=>2993, 2=>10067}
=> nil

That is, it’s unlikely (only about a 1/9 chance) that “a” ends up in
the middle.

The suggestion to use sort_by { rand }, however, does give a good
shuffle.

5

Ari B. [email protected] writes:

I’ve been writing my own shuffling method, and I end up getting
doubles in it.

The problem is that you don’t clear out helper_array between cycles of
the while loop. It’s still got junk left in it from the previous time
through the loop. Moving one line fixes this problem: (I’ve left the
indentation the same so that you can more easily find the line that I
moved around)

def recurssive_shuffle some_array
n = some_array.length
new_array = []
while n != 0
r = rand(n)
helper_array = []
while some_array.length != (r + 1)
helper_array.push some_array.pop
end
new_array.push some_array.pop
n = (n - 1)
helper_array.each do |item|
some_array.push item
end
end
puts new_array
end

However, it occurs to me that this algorithm is easier to express as:

“recursive” only has one “s”

def recursive_shuffle some_array
new_array = []
while ! some_array.empty?
r = rand(some_array.length)
new_array.push some_array.delete_at(r)
helper_array = some_array.slice!(r…-1)
helper_array.reverse!
some_array.concat helper_array
end
puts new_array
end

It took me a while to realize that you were reversing the bits you’d
pulled off.

I’ll also note that the reversing doesn’t affect the randomness of
your shuffle at all. The last three lines of that while loop
(everything dealing with helper_array) could be dropped without
affecting anything. The sort_by { rand } method is almost certainly
faster, or you could go and implement a standard Fisher-Yates in-place
shuffle:

shuffles some_array in-place

def shuffle some_array
2.upto(some_array.length) do |n|
r = rand(n)
some_array[n-1],some_array[r] = some_array[r],some_array[n-1]
end
some_array
end

(or open up Array, and add this method as shuffle!)

6

On Apr 22, 2007, at 11:15 PM, eden li wrote:

Why not just do a random sort instead?

some_array = [‘cat’, ‘dog’, ‘fun’, ‘zoo’]
=> [‘cat’, ‘dog’, ‘fun’, ‘zoo’]

some_array.sort { rand(3) - 1 }
=> [“zoo”, “dog”, “fun”, “cat”]

I wanted to write my own method to better understand how it works.
Plus because it WAS fun, until it decided it didn’t want to work.

P.S. = why rand(3) - 1? Why not just some other rand(x)?

n = some_array.length
some_array.push item

 while some_array.length != (r + 1)

end

---------------------------------------------------------------|
~Ari
“I don’t suffer from insanity. I enjoy every minute of it” --1337est
man alive

7

rand(3) - 1 always returns -1, 0 or 1 which is what sort() expects.
However, as Daniel points out, this method favors certain positions
for certain elements, so it won’t give you a “true” shuffle.

8

I’m not gonna lie. You’re a genius to me. Not only did you spot my
problem and help me fix it, but you provided not 1, not 3, not 4, but
2 solutions to help me. You rock.

Meh! Too many commands I haven’t learned yet. But thank you SOOOOOO
MUCHHHH

On Apr 23, 2007, at 1:17 AM, Daniel M. wrote:

 n = (n - 1)

def recursive_shuffle some_array

shuffles some_array in-place

def shuffle some_array
2.upto(some_array.length) do |n|
r = rand(n)
some_array[n-1],some_array[r] = some_array[r],some_array[n-1]
end
some_array
end

(or open up Array, and add this method as shuffle!)

-------------------------------------------------------|
~ Ari
crap my sig won’t fit