CODEWITHSUNDEEP
ruby-on-railsrubyalgorithmsorting
SomeSchmo
SomeSchmo

Reputation: 665

Sorting Difficulty

I have a bunch of objects, lets call them Items, each Item has, among other things, a weight and a publisher. I want to sort them by weight (decreasing), but, and here's the tricky bit, ensure that no Items with the same publisher appear twice (or more) in a row.

I was thinking about using a sort_by loop and keeping track of the publisher indexes along the way (with a hash using the publishers as the keys and arrays of indexes as values), but I'm not sure if that's the best way to go about this or how to take care of that in practice if it is the best way. Any suggestions?

EX:

say all theses items were in an array called items and ordered randomly. I would like to sort them so the weight=2 items appear first and the items with 'foo' as the publisher don't appear next to each other if possible (if there were no other publishers in that weight class then they would appear next to each other)

items = [(id: 1, name: "item1", publisher: "foo", weight: 2),
    (id: 2, name: "item2", publisher: "foo", weight: 2),
    (id: 3, name: "item3", publisher: "baz", weight: 1),
    (id: 4, name: "item4", publisher: "bar", weight: 2)]

puts custom_sorting_method(items)

would return 

   [(id: 1, name: "item1", publisher: "foo", weight: 2),
    (id: 4, name: "item4", publisher: "bar", weight: 2),
    (id: 2, name: "item2", publisher: "foo", weight: 2),
    (id: 3, name: "item3", publisher: "baz", weight: 1)]

Upvotes: 0

Views: 109

Answers (3)

theo
theo

Reputation: 46

You could try grouping by weight and sort each grouped list by publisher, followed by alternatively taking the first and last element of each sorted list. Very roughly:

results = []
alt_methods = [:shift, :pop]

grouped = items.group_by{ |item| item[:weight] }
grouped_and_sorted = grouped.each do |k,v|
  v.sort_by { |item| item[:publisher] }
end

grouped_and_sorted.each do |k,v|
  v.length.times{ |i| results << v.send(alt_methods[i%2]) }
end

Upvotes: 2

Halil &#214;zg&#252;r
Halil &#214;zg&#252;r

Reputation: 15945

# Sorts by weight, and then distributes by publisher within each weight.
#
# @param [Array<Hash>] items
# @return [Array<Hash>]
def special_sort(items)
  by_weight_nested = Hash[
    items
      .group_by { |item| item[:weight] }
      .map { |weight, arr| [weight, arr.group_by { |item| item[:publisher] }] }
  ]

  sorted = []

  by_weight_nested.keys.sort.reverse.each do |weight|
    publishers = by_weight_nested[weight].keys
    0.upto(by_weight_nested[weight].values.map(&:size).max - 1) do |i|
      publishers.each do |publisher|
        sorted << by_weight_nested[weight][publisher][i]
      end
    end
  end

  sorted.compact
end

Upvotes: 1

txtcoder
txtcoder

Reputation: 51

sorted = Items.sort{|x,y| y.weight <=> x.weight}
sorted.uniq!{|x| x.publisher}

Upvotes: 1

Related Questions