셔플 알고리즘 : 저녁 식사를위한 부서 셔플

Question

의사 소통을 확대하기 위해 회사는 저녁 식사를 위해 부서를 혼합하기로 결정했습니다. 각 테이블이 저녁 식사로 10 명을 허용하도록 고안되었지만 다른 사람을 추가하는 것도 좋습니다. 따라서 직원 수 N % 10이 6보다 작 으면 N % 10 명은 다른 10 명으로 표를 배치해야합니다.

20 개 부서가 있고 각 부서마다 10 ~ 30 명이 있다고 가정합니다. 같은 부서에 속한 사람들이 같은 테이블에있을 기회가 가장 적어 지도록 두 식당의 재산이 테이블에서 만날 수 있도록 저녁 식사를 무작위로 준비 하시겠습니까?

제 구현시 무작위로 10 명을 무작위로 배치합니다. 그런 다음 각 테이블의 각 부서에 대해 고유 한 것을 남겨두고 다른 테이블을 꺼내 배열에 넣습니다. 배열은 무작위로 섞여서 다시 테이블에 놓입니다. 비용 함수 F가 결코 감소하지 않을 때까지 이것을 수행하십시오. F는 동일한 표에 표시된 동일한 부서의 사람들 수의 합으로 정의됩니다.

Answer 1

모든 것을 이해하면이 문제는 완전히 사소한 것처럼 보입니다. 필요한 테이블의 수를 미리 계산하십시오 (제공된 기준을 사용하여 N%10 기준). 가장 큰 부서에서 시작하여 부서 당 부서원을 테이블 당 하나씩 할당하십시오. 마지막 테이블에 도달하면 첫 번째 테이블로 돌아가서 테이블 당 한 사람을 계속 할당하십시오. 부서의 모든 직원이 배정되면 2 번째로 큰 부서로 이동합니다. 가득 찬 테이블에 도달하면 건너 뜁니다.

가장 큰 부서에있는 사람들의 수는 테이블의 수보다 작은 경우

, 같은 테이블에 같은 부서 내부의 사람들이의 확률은 0