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

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

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

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

$sortedList = array();
$tempList
$emailList = array('[email protected]', '[email protected]', '[email protected]', '[email protected]', '[email protected]', '[email protected]');

$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]);
    }
}

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

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

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

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

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

Престижность Аристотелю.

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

[["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

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

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

радж