アルゴリズム：異なる色のボールを均等に分配する方法は？

Question

私はいくつかの異なる色の球がいくつかあるとしましょう。例として、赤いボール4個、青いボール4個、緑色のボール2個を想定してみましょう。私は均等に同じ色の2つのボールの間で最も一貫性の距離が維持されるように、私は以下の配列を有する可能性がこれらのボールを配布する場合：

RBGRBRBGRB

を青と赤のボールは、常にではないにもかかわらず、グリーンボールの一貫性を維持しながら距離を一定に保つような方法で配置されています。

赤いボール6個、青いボール5個、緑色のボール3個の場合、次のようなもの：

RBRGBRBGRBR- G-R

「同じ色の2つの球の間の最も一貫した距離」の基準は何でしょうか？これを解決するアルゴリズムまたは一般化された解決策がありますか？この場合の正式な名前は何ですか？

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を交換してください。場合は、条件の成功に色を対応する出力：

HERE

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