Shuffle Method

ruby-talk
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

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"]

···

On Apr 23, 8:59 am, Ari Brown <a...@aribrown.com> wrote:

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

3

Ari Brown <ari@aribrown.com> 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!)

···

--
s=%q( Daniel Martin -- martin@snowplow.org
       puts "s=%q(#{s})",s.map{|i|i}[1] )
       puts "s=%q(#{s})",s.map{|i|i}[1]

4

Or some_array.sort_by { rand }

···

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"]

--
Jesse Merriman
jessemerriman@warpmail.net
http://www.jessemerriman.com/

5

eden li <eden.li@gmail.com> 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.

···

--
s=%q( Daniel Martin -- martin@snowplow.org
       puts "s=%q(#{s})",s.map{|i|i}[1] )
       puts "s=%q(#{s})",s.map{|i|i}[1]

6

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)?

--------------------------------------------------------------|
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

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

···

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

7

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 Martin wrote:

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!)

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

8

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.

···

On Apr 24, 10:16 am, Ari Brown <a...@aribrown.com> wrote:

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)?

>> --------------------------------------------------------------|
>> 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

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