Algorithme: Comment distribuer uniformément des balles de différentes couleurs?

Question

Disons que j'ai un certain nombre de boules de différentes couleurs. À titre d'exemple, supposons 4 boules rouges, 4 boules bleues et 2 boules vertes. Si je veux répartir ces boules de sorte que la distance la plus cohérente entre deux boules de la même couleur est maintenue, je pourrais avoir la séquence suivante:

RBGRBRBGRB

Même si Blue Balls et Rouge ne sont pas toujours à la même distance de leurs homologues, ils sont disposés de manière à garder leurs distances cohérentes tout en maintenant la cohérence pour les Green Balls

Dans le cas de 6 boules rouges, 5 boules bleues, et 3 boules vertes, je pourrais avoir quelque chose comme:

RBRGBRBGRBR- G-R

Je ne sais pas exactement quels seraient les critères de «la distance la plus constante entre deux balles de la même couleur», mais existe-t-il une sorte d'algorithme ou de solution généralisée qui résoudrait ce problème? Quel est le nom officiel de ce problème, si c'est le cas?

Answer 1

Ce problème est similaire au dessin de ligne dans l'espace nD (ici 3D). Vous pouvez donc utiliser des algorithmes de type Bresenham/DDA pour générer une séquence avec une distribution équitable des éléments (au lieu d'une distribution équitable des changements de pixels dans une dimension donnée). Arbitraire found example
(je n'ai pas vérifié l'exactitude - la division peut-être dm/2 pourrait produire moins bons résultats que doubler d'erreur):

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; } 
    } 
} 

Remplacer x1-x0 par le premier nombre de couleurs, y1-y0 par le second et ainsi de suite. couleur correspondant à la sortie en cas de succès conditions:

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