도메인별로 메일 주소 목록을 균등하게 바꿉니다.

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

다음은이 문제에 대한 나의 해결책입니다.

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

같은 입력을 감안할 때 출력은

AABABAACABAACABAACABAD 

프로그램의

루비 소스는 다음과 같습니다

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 2

모든 도메인 충돌이 그룹화 한 후, 링크 된 목록을 한 번에 하나씩 불구하고 반복 할 수 있도록, 연결리스트의 해시지도 것이 내 시작 시도.

그게 의미가있는 경우.

는

다음 코드는 완전히 안된이고, 나는 물건의 무리를 잘 작성하지 못했습니다 두 번째 루프가 알고 있지만, 더 빨리 더 설명하는 것보다했다.

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

Answer 3

기본적으로 각 이메일 주소에 대해 지정된 도메인에 대한 링크 된 목록에 주소를 입력하십시오. 이것이 O (n) 연산이고, 새로운, 균형 잡힌리스트를 생성하는 것은 도메인 목록을 순환하는 또 다른 대략 O (n) 연산입니다.

주문한대로 약 2 패스 복잡성입니다.

Answer 4

도메인 당 이메일 주소 수가 같거나 비슷한 것으로 가정하는 응답에 유의하십시오.

나는 본질적으로 같은 문제를 해결하기 위해 노력하고, 내 블로그에 토론을 많이받은 : First Article, 우리는 빠르고 최적의 솔루션을 찾을 수 없습니다 Second Article

하지만, fastest, close-enough solution (포함 펄 소스 코드)은 Aristotle Pagaltzis의 댓글에서 왔습니다.

명예의 전당.