알고리즘 : 다른 색의 볼을 균일하게 분배하는 방법?

Question

다른 색깔의 공이 몇 개 있다고 가정 해 보겠습니다. 예를 들어 4 개의 빨간 공, 4 개의 파란색 공 및 2 개의 녹색 공을 가정 해 봅시다.

RBGRBRBGRB

에도 블루와 레드 공은 항상하지 않습니다하지만 : 나는 균등이 공을 배포하려는 경우, 같은 색깔의 두 볼 사이의 가장 일관된 거리가 유지되도록 나는 다음과 같은 순서를 가질 수 있도록 녹색 공에 대한 일관성을 유지하면서 거리를 일관되게 유지하는 방식으로 배열됩니다.

빨간 공이 6 개인 경우, 파란색 공이 5 개인 경우 및 녹색 공이 3 개인 경우 예 :

RBRGBRBGRBR- G-R

"같은 색의 두 볼 사이의 가장 일관된 거리"에 대한 기준이 무엇 일지는 모르지만이를 해결할 수있는 일종의 알고리즘 또는 일반 솔루션이 있습니까? 이 경우 공식적인 이름은 무엇입니까?

Answer 1

이 문제는 nD 공간 (여기 3D)에서의 선 그리기와 유사합니다. 따라서 Bresenham/DDA와 같은 알고리즘을 사용하여 정당한 항목 분포가있는 시퀀스를 생성 할 수 있습니다 (일정 차원의 픽셀 이동을 공정하게 분배하는 대신). 임의 found example
(내가 확인하지 않은 그 정확성 - 아마도 부문 dm/2 오류 배로보다 더 나쁜 결과를 생성 할 수 있음)을 :

void plotLine3d(int x0, int y0, int z0, int x1, int y1, int z1) 
{ 
    int dx = abs(x1-x0), sx = x0<x1 ? 1 : -1; 
    int dy = abs(y1-y0), sy = y0<y1 ? 1 : -1; 
    int dz = abs(z1-z0), sz = z0<z1 ? 1 : -1; 
    int dm = max(dx,dy,dz), i = dm; /* maximum difference */ 
    x1 = y1 = z1 = dm/2; /* error offset */ 

    for(;;) { /* loop */ 
     setPixel(x0,y0,z0); 
     if (i-- == 0) break; 
     x1 -= dx; if (x1 < 0) { x1 += dm; x0 += sx; } 
     y1 -= dy; if (y1 < 0) { y1 += dm; y0 += sy; } 
     z1 -= dz; if (z1 < 0) { z1 += dm; z0 += sz; } 
    } 
} 

첫 번째 색상 수, 그래서 두 번째와에 의해 y1-y0에 의해 x1-x0를 교체합니다. 경우-조건 성공의 색상을 해당 출력 :

여기

{x1 -= dx; if (x1 < 0) { x1 += dm; x0 += sx;}