Равномерное перемешивание списка почтовых адресов по доменам

Question

У меня есть список адресов электронной почты, которые я хочу равномерно распределить по доменам.

Например:

пусть список будет,

a@a.com
b@a.com
c@a.com
a@b.com
b@b.com
c@c.com

Вывод должен быть

a@a.com
a@b.com
c@c.com
b@a.com
b@b.com
c@a.com

Список источников не сортируется по домену, как в примере, но может быть отсортирован по домену, если это может помочь. Каким будет эффективный (однопроходный?) Алгоритм для этого?

Радж

Answer 1

Остерегайтесь ответов, которые предполагают, что количество адресов электронной почты на домен одинаково (или одинаково).

Я пытался решить по существу ту же проблему, и в моем блоге много обсуждалось: Первая статья , Вторая статья

Мы не нашли быстрого, оптимального решения, но самое быстрое, достаточно близкое решение (включая исходный код Perl) пришло из комментария от Аристотеля Пагальтзиса .

Слава Аристотелю.

Answer 2

Вот мое решение этой проблемы. С учетом ввода типа

[["A", 13], ["B", 5], ["C", 3], ["D", 1]] 

Выход

AABABAACABAACABAACABAD

Ruby-источник программы:

require "pp"

def shuffle (total, num)
  ret_arr = Array.new
  intervel = total/num.to_f
  0.upto(num-1) do |i|
    val = i * intervel
    ret_arr << val.floor
  end
  return ret_arr
end

freq_table = [["A", 13], ["B", 5], ["C", 3], ["D", 1]]

pp freq_table
total = 0
freq_table.collect {|i| total += i[1] }
final_array = Array.new(total,0)
print  final_array.to_s + "\n\n"
placed = 0

freq_table.each do |i|
  placements =  shuffle(total - placed, i[1])
  placements.each do |j|
    free_index = -1
    0.upto final_array.size do |k|
      free_index += 1 if (final_array[k] == 0 || final_array[k] == i[0])
      if j == free_index
        final_array[k] = i[0]
        break
      end
    end
  end
  print "Placing #{i[1]} #{i[0]}s over #{total - placed} positions\n"
  pp placements
  print  final_array.to_s + "\n\n"
  placed += i[1]
end

Идея состоит в том, чтобы взять алфавит с наибольшей частотой и сначала распределить его по массиву, размер которого равен общему числу всех элементов. Затем распределите алфавит со второй по величине частотой и распределите по свободному пространству и так далее.

Если у вас есть вопросы, дайте мне знать, и я с удовольствием отвечу.

Радж

Answer 3

По сути, для каждого адреса электронной почты поместите адрес в связанный список для данного домена. Это операция O (n), затем создание нового сбалансированного списка является еще одной грубой операцией O (n) путем циклического перемещения по спискам доменов.

Это примерно двухпроходная сложность, как приказано.

Answer 4

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

Если это имеет смысл.

Следующий код полностью НЕПРОВЕРЕН , и я знаю, что во втором цикле есть куча вещей, которые не прямо, но это было быстрее, чем пытаться объяснить дальше.

$sortedList = array();
$tempList
$emailList = array('a@a.com', 'b@a.com', 'c@b.com', 'd@b.com', 'e@c.com', 'f@a.com');

$emailCount = 0;
foreach ( $emailList as $email ) {
    list($username, $domain) = explode('@', $email);
    $tempList[$domain][] = $user;
    $emailCount++;
}

for ( $i = 0; $i < $emailCount; $i++ ) {
    $listIndex = $i % count($tempList);
    if ( !empty($tempList[$listIndex]) ) {
        $sortedList[] = $tempList[$listIndex][0];
        unset($tempList[$listIndex][0]);
    } else {
        unset$tempList[$listIndex]);
    }
}