рубин sort_by with_index по модулю

Question

у меня есть это:

input = ["a","b","c","d","a","b","c","d","a","b","c","d"] 

Я хочу это:

result = ["a","a","a","b","b","b","c","c","c","d","d","d"] 

Я попытался это:

input.sort_by.with_index do |piece, index| 
    index%3 
end 

Я получил это:

["a", "d", "c", "b", "c", "b", "d", "a", "d", "b", "a", "c"] 

почему?

Answer 1

Если посмотреть на index % 3, вы получите:

input  "a" "b" "c" "d" "a" "b" "c" "d" "a" "b" "c" "d" 
index  0 1 2 3 4 5 6 7 8 9 10 11 
index % 3 0 1 2 0 1 2 0 1 2 0 1 2 

и если вы группировать их по index % 3, вы получите:

input  "a" "d" "c" "b" 
index % 3 0 0 0 0 

input  "b" "a" "d" "c" 
index % 3 1 1 1 1 

input  "c" "b" "a" "d" 
index % 3 2 2 2 2 

Так вроде в Рубине не является стабильным, когда вы сортировать их по index % 3, вы получите:

[ 
    <some permutation of "a" "d" "c" "b">, 
    <some permutation of "b" "a" "d" "c">, 
    <some permutation of "c" "b" "a" "d">, 
] 

который что вы получили.

Answer 2

Попробуйте это:

input.sort_by.with_index do |piece, index| 
    index%3 + (index.to_f/input.count) 
end 

Как мы сюда попали?

Решение OP близко, но, как упоминалось в @sawa, index%3 дает нам только 0, 1 или 2. Нестабильный сортир Ruby будет смешивать элементы в этих группах.

Этого не должно быть. Вместо этого вы можете вымачивать эти ключи сортировки, поэтому у ruby ​​нет выбора, кроме как отсортировать его правильно. Нам просто нужно выдумки-фактор, который:

• всегда растет, но
• всегда достаточно небольшой случайно не врезаться нас в новую группу (т.е. < 1)

Episode One: выстрел в темноте

Рассмотрим, жульничество его index:

input.sort_by.with_index do |piece, index| 
    index%3 + index 
end 

Это может показаться глупым, но оно соответствует критериям 1/2: всегда увеличивается, оно просто велико. Мы можем это исправить.

Episode Two: Ruby Redemption

Мы знаем index < input.count, так что если мы просто разделим обе стороны от input.count мы получаем index.to_f/input.count <, что это именно то, что мы хотим (но не забудьте преобразовать в поплавком) !

input.sort_by.with_index do |piece, index| 
    index%3 + (index.to_f/input.count) 
end 

Bonus

Я думаю, что это решение умна, но по той же причине на самом деле не использовать его в общественных местах:

input.sort_by.with_index do |piece, index| 
    index%3 - 1.to_f/(1 + index) 
end