[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

array sorting question

Giles Bowkett

11/6/2006 1:47:00 AM

I have an array of arrays. the interior arrays can be of any arbitrary
length including zero. I want to sort the array of arrays in such a
way that the interior arrays with the most elements are closest to the
middle of the main array.

so if it comes out like this:
main[0] = [1, 2, 3, 4, 5]
main[1] = []
main [2] = []
main [3] = [1, 2]

then that's wrong. but it's good if it looks like this:

main[0] = []
main[1] = [1, 2]
main[2] = [1, 2, 3, 4, 5]
main[3] = []

and of course it should scale with more data to produce pyramids.

wait a minute. is this the Tower of Hanoi?

any and all suggestions welcome. I'm going to look up the Tower of
Hanoi. I think that's what it is.

--
Giles Bowkett
http://www.gilesg...
6 Answers

Giles Bowkett

11/6/2006 2:03:00 AM

0

ok, cancel that, this is not the tower of hanoi, this is splitting an
array in half, sorting both halves, and reversing one before putting
it back together. doh!!

On 11/5/06, Giles Bowkett <gilesb@gmail.com> wrote:
> I have an array of arrays. the interior arrays can be of any arbitrary
> length including zero. I want to sort the array of arrays in such a
> way that the interior arrays with the most elements are closest to the
> middle of the main array.
>
> so if it comes out like this:
> main[0] = [1, 2, 3, 4, 5]
> main[1] = []
> main [2] = []
> main [3] = [1, 2]
>
> then that's wrong. but it's good if it looks like this:
>
> main[0] = []
> main[1] = [1, 2]
> main[2] = [1, 2, 3, 4, 5]
> main[3] = []
>
> and of course it should scale with more data to produce pyramids.
>
> wait a minute. is this the Tower of Hanoi?
>
> any and all suggestions welcome. I'm going to look up the Tower of
> Hanoi. I think that's what it is.
>
> --
> Giles Bowkett
> http://www.gilesg...
>
>


--
Giles Bowkett
http://www.gilesg...

Kevin

11/6/2006 3:03:00 AM

0


Giles Bowkett wrote:
> ok, cancel that, this is not the tower of hanoi, this is splitting an
> array in half, sorting both halves, and reversing one before putting
> it back together. doh!!
>
> On 11/5/06, Giles Bowkett <gilesb@gmail.com> wrote:
> > I have an array of arrays. the interior arrays can be of any arbitrary
> > length including zero. I want to sort the array of arrays in such a
> > way that the interior arrays with the most elements are closest to the
> > middle of the main array.
> >
> > so if it comes out like this:
> > main[0] = [1, 2, 3, 4, 5]
> > main[1] = []
> > main [2] = []
> > main [3] = [1, 2]
> >
> > then that's wrong. but it's good if it looks like this:
> >
> > main[0] = []
> > main[1] = [1, 2]
> > main[2] = [1, 2, 3, 4, 5]
> > main[3] = []
> >
> > and of course it should scale with more data to produce pyramids.
> >
> > wait a minute. is this the Tower of Hanoi?
> >
> > any and all suggestions welcome. I'm going to look up the Tower of
> > Hanoi. I think that's what it is.
> >
> > --
> > Giles Bowkett
> > http://www.gilesg...
> >
> >
>
>
> --
> Giles Bowkett
> http://www.gilesg...

Actually, it's not even that.
If the arrays are populated in an asymetric way, then you could get one
half of the array with much higher values than the other, which might
not be what you want.

A better approach might be like this...

main_array = [
[1,2,3,1,2],
[1,1],
[],
[2],
[5,4,3,2,1,1,3],
[5,5,3,2,1],
[1]]

sorted_array = main_array.sort_by {|x| x.size}

final_array = []
sorted_array.reverse.each_with_index do |item, i|
final_array.insert(-1*(i%2), item)
end

puts final_array.inspect

>> [[], [2], [5, 5, 3, 2, 1], [5, 4, 3, 2, 1, 1, 3], [1, 2, 3, 1, 2], [1, 1], [1]]

Gavin Kistner

11/6/2006 3:51:00 AM

0

Giles Bowkett wrote:
> I have an array of arrays. the interior arrays can be of any arbitrary
> length including zero. I want to sort the array of arrays in such a
> way that the interior arrays with the most elements are closest to the
> middle of the main array.

main = (-4..12).map{ |i| (0..i).to_a }

sorted = main.sort_by{ |sub| sub.length }
i = 0
half1, half2 = sorted.partition{ (i+=1) % 2 == 0 }
pyramid = half1 + half2.reverse

require 'pp'
pp pyramid

#=> [[],
#=> [],
#=> [0, 1],
#=> [0, 1, 2, 3],
#=> [0, 1, 2, 3, 4, 5],
#=> [0, 1, 2, 3, 4, 5, 6, 7],
#=> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
#=> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
#=> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],
#=> [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
#=> [0, 1, 2, 3, 4, 5, 6, 7, 8],
#=> [0, 1, 2, 3, 4, 5, 6],
#=> [0, 1, 2, 3, 4],
#=> [0, 1, 2],
#=> [0],
#=> [],
#=> []]

Gavin Kistner

11/6/2006 3:56:00 AM

0

Giles Bowkett wrote:
> ok, cancel that, this is not the tower of hanoi, this is splitting an
> array in half, sorting both halves, and reversing one before putting
> it back together. doh!!

As shown in my solution, I think the better answer is sorting the full
array by the length of the sub arrays, and then splitting it into two
arrays of every other item, and then (as you say) reversing one of them
before putting it back together.

Giles Bowkett

11/7/2006 5:08:00 AM

0

wow, both these solutions look better than what I have, and I don't
understand either one of them.

so Phrogz your solution is very similar to mine, except you do the
split after the sort instead of before it? I do have to preserve the
nested arrays intact.

I think I should say, this is a real-world thing, the arrays aren't
really of numbers, they're of objects. I'm not sure if that makes a
difference, though.

hmm, bit too brain-fried to follow all this at the moment, but
definitely thanks for the guidance, I'll see what I can learn from
these.

On 11/5/06, Phrogz <gavin@refinery.com> wrote:
> Giles Bowkett wrote:
> > ok, cancel that, this is not the tower of hanoi, this is splitting an
> > array in half, sorting both halves, and reversing one before putting
> > it back together. doh!!
>
> As shown in my solution, I think the better answer is sorting the full
> array by the length of the sub arrays, and then splitting it into two
> arrays of every other item, and then (as you say) reversing one of them
> before putting it back together.
>
>
>


--
Giles Bowkett
http://www.gilesg...

Giles Bowkett

11/10/2006 6:59:00 AM

0

you know, both these solutions, while much prettier than my code,
produced messier results. here's what I used.

stuff = data_objects[thing_name]
if 2 < stuff.length
midpoint = stuff.length / 2
left_side = stuff[0..midpoint]
right_side = stuff[(midpoint + 1)..10000000]
[left_side, right_side].each do |things|
things.sort! {|x,y| x.inner_stuff.length <=> y.inner_stuff.length}
end
stuff = left_side + right_side.reverse
end

there's some graphing of the results, which is why I named the vars
left side and right side. anyway, as I said, the suggestions were much
much prettier than my code. but for some reason the results, in the
graph this thing produces as output, were prettier.

I really don't know why this ugly, hackish code produces prettier
results, but it does. it's kind of weird that way.

--
Giles Bowkett
http://www.gilesg...