Algorithm to maximize the distance (avoid repetition) of picking elements from sets -

i'm looking find algorithm generalizes following problem n number of sets, simplicity assume there 4 different sets, each containing 4 elements. can assume each set contains equal number of elements, there can number of elements. if there 37 elements in first set, can assume there 37 elements contained in each of other sets.

a combination of elements formed taking 1 element first set , putting first place, 1 element second set , putting in second place, , on. example first set contains {a₀,a₁,a₂,a₃}, second set contains {b₀,b₁,b₂,b₃}, third {c₀,c₁,c₂,c₃} , fourth {d₀,d₁,d₂,d₃}. 1 possible combination [a₀, b₂, c₁, d₃].

the goal find path maximizes distance when cycling through possible combinations, avoiding repetition as possible. , avoiding repetition applies contiguous groups individual columns. example:

1. individual columns

   1. [a₀, b₀, c₀, d₀]
   2. [a₁, b₁, c₁, d₁]
   3. [a₂, b₀, c₂, d₂]

this incorrect because b₀ repeated sooner had be.

2. contiguous groups

   1. [a₀, b₀, c₀, d₀]
   2. [a₁, b₁, c₁, d₁]
   3. [a₂, b₂, c₂, d₂]
   4. [a₃, b₃, c₃, d₃]
   5. [a₀, b₀, c₁, d₂]

this incorrect because contiguous pair (a₀, b₀) repeated sooner had be. if last 1 instead [a₀, b₁, c₀, d₁] alright.

when cycling through possible combinations contiguous groups have repeated, goal maximize distance between them. example if (a₀, b₀) used, ideally other first pairs used before it's used again.

i able find solution when there 3 sets, i'm having trouble generalizing n sets , solving 4 sets. ideas?

can post solution 3 sets?

sure, first wrote down possible combinations. made 3 3x3 matrices of entries grouping entries non-contiguous (first , third) elements repeated:

 (a0,b0,c0)1, (a1,b0,c1)4, (a2,b0,c2)7    (a0,b0,c1)13, (a1,b0,c2)16, (a2,b0,c0)10    (a0,b0,c2)25, (a1,b0,c0)19, (a2,b0,c1)22
 (a0,b1,c0)8, (a1,b1,c1)2, (a2,b1,c2)5    (a0,b1,c1)11, (a1,b1,c2)14, (a2,b1,c0)17    (a0,b1,c2)23, (a1,b1,c0)26, (a2,b1,c1)20
 (a0,b2,c0)6, (a1,b2,c1)9, (a2,b2,c2)3    (a0,b2,c1)18, (a1,b2,c2)12, (a2,b2,c0)15    (a0,b2,c2)21, (a1,b2,c0)24, (a2,b2,c1)27 

then realized if traversed in diagonal pattern (order indicated superscript index) obey rules. wrote following code take advantage of visual pattern:

@test public void run() {      list<string> = new arraylist<string>();     a.add("0");     a.add("1");     a.add("2");     list<string> b = new arraylist<string>();     b.add("0");     b.add("1");     b.add("2");     list<string> c = new arraylist<string>();     c.add("0");     c.add("1");     c.add("2");      int numelements = a.size();      list<string> output = new arraylist<string>();      int offset = 0;     int nextoffset = 0;      (int = 0; < a.size()*b.size()*c.size(); i++) {          int j = % numelements;         int k = / numelements;          if (j == 0 && k%numelements == numelements-1) {             nextoffset = (j+k+offset) % numelements;         }          if (j == 0 && k%numelements == 0) {             offset = nextoffset;         }          string first = a.get((j+k+offset) % numelements);         string second = b.get(j);         string third = c.get((j+k) % numelements);          system.out.println(first + " " + second + " " + third);         output.add(first + second + third);     }  } 

however realized isn't ideal either, since looks pair (a₀,b₁) repeated soon, @ indices 8 , 11 :( think maybe unavoidable, when crossing on 1 group another?.. difficult problem! harder looks

if can think , revise actual requirements

okay decided remove restriction of traversing through possible combinations, , instead reduce yield little bit improve quality of results.

the whole point of take elements belonging particular set , combine them form combination of elements appear unique. if start out 3 combinations , there 3 sets, can break each combination 3 elements , place elements respective sets. can use algorithm mix , match elements , produce 27 seemingly unique combinations -- of course they're formed derivative elements appear unique long don't closely!

so 3 combinations formed hand can turned 3³ combinations, saving lot of time , energy. of course scales pretty nicely too, if form 10 combinations hand algorithm can generate 1000 combinations. don't need quite many combinations anyways, can sacrifice entries better avoid repetition. in particular 3 sets noticed while solution decent, there bunching occurred every numelements² entries. here example of 3 sets of 5 elements, obvious repetition after 25 combinations:

19) a1 b3 c1
20) a2 b4 c2
21) a4 b0 c4 <--
22) a0 b1 c0
23) a1 b2 c1
24) a2 b3 c2
25) a3 b4 c3
26) a0 b0 c4 <--
27) a1 b1 c0
28) a2 b2 c1
29) a3 b3 c2
30) a4 b4 c3
31) a1 b0 c0
32) a2 b1 c1

to fix can introduce following statement , rid of bad block:

if (k % numelements == 0) continue; 

however works when numelements > numsets, otherwise individual columns rule broken. (in case wondering switched ordering of first , third sets in example, did wasn't opening bad repetition)

aaannd i'm still stuck on how form approach n or 4 sets. gets trickier because there different sizes of contiguous groups avoid, contiguous trios pairs.. thoughts? crazy trying this?

even after modifications in question, i'm still not sure want. seems impossible, i'm not sure how relaxation in conditions acceptable. nevertheless, i'll give crack.

oddly there seems little literature (that can find, anyway) covering subject of problem, had invent myself. idea: looking sequence of points on multidimensional torus such elements of sequence far apart possible in complicated metric. reminds me of learned years ago in mechanics class, strangely enough. if have line on flat torus rational slope, line loop onto after few cycles, if have line irrational slope, line densely cover entire torus.

i don't expect mean lot many people, did give me idea. index each set step irrational amount. have take floor, of course, , modulo whatever, seem cover bases well, speak. irrational step each set different (and mutually irrational, use rather loose language).

to make idea more precise, wrote short program. please check out.

class equidistributed {   static final double irrational1 = math.sqrt(2);   static final double irrational2 = math.sqrt(3);   static final double irrational3 = math.sqrt(5)-1;    // 4 sets of 7 elements each   static int setsize = 7;    public static void main(string[] args) {     (int = 0; < math.pow(setsize,4); i++) {       string tuple = "";       int j = % setsize;       tuple += j + ",";       j = ((int)math.floor(i*irrational1)) % setsize;       tuple += j + ",";       j = ((int)math.floor(i*irrational2)) % setsize;       tuple += j + ",";       j = ((int)math.floor(i*irrational3)) % setsize;       tuple += j;       system.out.println(tuple);     }   } } 

i "eyeballed" results, , aren't perfect, they're pretty nice. plus program runs quickly. it's 4 sets variable number of elements (i chose 7 example). irrational numbers i'm using based on square roots of prime numbers; subtracted 1 sqrt(5) result in range between 1 , 2. each tuple

(i, floor(i*irrational1), floor(i*irrational2), floor(i*irrational3)) mod 7 

statistically should make sequence evenly distributed, consequence of want. whether translates right "distance" properties, can't sure. should write program test whether sequence has property want, , pipe output program test.