Блог

Главная - Вопросы по программированию - Упорядочивание массива с как можно меньшим количеством смежных значений

Упорядочивание массива с как можно меньшим количеством смежных значений

#sql #algorithm #sorting

#sql #алгоритм #сортировка

Вопрос:

С таким массивом, как этот:

 [google, google, yahoo, yahoo, yahoo, msn, msn, msn, google]

каков наилучший способ упорядочить его с как можно меньшим количеством смежных значений?
Цель состоит в том, чтобы получить что-то вроде этого, например:

 [google, msn, yahoo, google, yahoo, msn, yahoo, msn, google]

Еще лучше был бы алгоритм, который гарантирует, что любые похожие значения находятся как можно дальше друг от друга.

А еще лучше было бы сделать это непосредственно в SQL.

Я делаю это для скрипта, над которым я работаю, который отправляет информационные бюллетени, и я бы хотел избежать одновременной отправки слишком большого количества электронных писем в один и тот же домен.

[править] Я использую MySQL

Комментарии:

1. Это сортировка? Больше похоже на перетасовку с определенными ограничениями… в любом случае, что вы пробовали до сих пор?

2. @user996651 — какую базу данных вы используете?

3. @Felix Kling — пока я выбираю их случайным образом: ВЫБЕРИТЕ * ИЗ порядка таблицы С ПОМОЩЬЮ ‘RAND ()’

Ответ №1:

Используя SQL Server 2005 и выше, вы можете воспользоваться преимуществами ROW_NUMBER функциональности

  • Добавьте номер строки к каждому элементу, разделяя на sitename .
  • выберите из этого подзапроса
  • упорядочите результаты по номеру строки и имени.

Ваше требование о том, что они должны быть как можно дальше друг от друга, может быть не выполнено, но в целом этого будет достаточно.

Инструкция SQL

 SELECT  Site
FROM    (
            SELECT  Site, o = ROW_NUMBER() OVER (PARTITION BY Site ORDER BY Site)
            FROM    q
        ) q
ORDER BY                
        o, Site

Результаты

google msn yahoo google msn yahoo google msn yahoo

Тестовый скрипт

 ;WITH q ([site])AS (
    SELECT 'google'
    UNION ALL SELECT 'google'
    UNION ALL SELECT 'yahoo'
    UNION ALL SELECT 'yahoo'
    UNION ALL SELECT 'yahoo'
    UNION ALL SELECT 'msn'
    UNION ALL SELECT 'msn'
    UNION ALL SELECT 'msn'
    UNION ALL SELECT 'google'   
)
SELECT  Site
FROM    (
            SELECT  Site, o = ROW_NUMBER() OVER (PARTITION BY Site ORDER BY Site)
            FROM    q
        ) q
ORDER BY                
        o, Site

Ответ №2:

Спасибо Ливен, я адаптировал ваш ответ к MySQL, и он отлично работает :

 select *
from (
    select
      @i := if(@last_name != t2.name, 1, @i   1) as row_number,
      @last_name := t2.name as `name`
    from
      site t2,
      (select @i := 0) vt1,
      (select @last_name := null) vt2
    order by t2.name
) t1
order by t1.row_number, t1.name
;

дает :

  ------------ -------- 
| row_number | name   |
 ------------ -------- 
|          1 | google |
|          1 | msn    |
|          1 | yahoo  |
|          2 | google |
|          2 | msn    |
|          2 | yahoo  |
|          3 | google |
|          3 | msn    |
|          3 | yahoo  |
 ------------ --------