Enumeration of a Cartesian product while minimizing repetition

Question

For two sets, for example:

{ABC}, {1 2 3 4 5 6} 

I want to generate a Cartesian product in the order that puts as much space as possible between equal elements. For example, [A1, A2, A3, A4, A5, A6, B1…] not suitable, because all A are next to each other. An acceptable solution would be down diagonally, and then each time it wraps the offset by one, for example:

 [A1, B2, C3, A4, B5, C6, A2, B3, C4, A5, B6, C1, A3…] 

It is visually expressed:

 | | A | B | C | A | B | C | A | B | C | A | B | C | A | B | C | A | B | C | |---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---| | 1 | 1 | | | | | | | | | | | | | | | | | | | 2 | | 2 | | | | | | | | | | | | | | | | | | 3 | | | 3 | | | | | | | | | | | | | | | | | 4 | | | | 4 | | | | | | | | | | | | | | | | 5 | | | | | 5 | | | | | | | | | | | | | | | 6 | | | | | | 6 | | | | | | | | | | | | | | 1 | | | | | | | | | | | | | | | | | | | | 2 | | | | | | | 7 | | | | | | | | | | | | | 3 | | | | | | | | 8 | | | | | | | | | | | | 4 | | | | | | | | | 9 | | | | | | | | | | | 5 | | | | | | | | | | 10| | | | | | | | | | 6 | | | | | | | | | | | 11| | | | | | | | | 1 | | | | | | | | | | | | 12| | | | | | | | 2 | | | | | | | | | | | | | | | | | | | | 3 | | | | | | | | | | | | | 13| | | | | | | 4 | | | | | | | | | | | | | | 14| | | | | | 5 | | | | | | | | | | | | | | | 15| | | | | 6 | | | | | | | | | | | | | | | | 16| | | | 1 | | | | | | | | | | | | | | | | | 17| | | 2 | | | | | | | | | | | | | | | | | | 18| 

or, which is equivalent, but without repeating rows / columns:

 | | A | B | C | |---|----|----|----| | 1 | 1 | 17 | 15 | | 2 | 4 | 2 | 18 | | 3 | 7 | 5 | 3 | | 4 | 10 | 8 | 6 | | 5 | 13 | 11 | 9 | | 6 | 16 | 14 | 12 | 

I believe that there are other solutions, but that it was easiest for me to think. But I hit my head against a wall, trying to understand how to express it in a general way - this is a convenient thing when the power of two sets is ambiguous, but I want the algorithm to do the right thing for sets, for example, sizes 5 and 7. Or sizes 12 and 69 (this is a real example!).

Are there established algorithms for this? I continue to be distracted from the thought of how rational numbers are mapped onto the set of natural numbers (to prove that they are countable), but the path that it takes via ℕ × ℕ does not work for this case.

It so happened that the application is written in Ruby, but I'm not interested in the language. Pseudocode, Ruby, Python, Java, Clojure, Javascript, CL, paragraph in English - choose your favorite.

---

Proof of conceptual solution in Python (it will soon be ported to Ruby and connected to Rails):

 import sys letters = sys.argv[1] MAX_NUM = 6 letter_pos = 0 for i in xrange(MAX_NUM): for j in xrange(len(letters)): num = ((i + j) % MAX_NUM) + 1 symbol = letters[letter_pos % len(letters)] print "[%s %s]"%(symbol, num) letter_pos += 1 

Answer 1

 String letters = "ABC"; int MAX_NUM = 6; int letterPos = 0; for (int i=0; i < MAX_NUM; ++i) { for (int j=0; j < MAX_NUM; ++j) { int num = ((i + j) % MAX_NUM) + 1; char symbol = letters.charAt(letterPos % letters.length); String output = symbol + "" + num; ++letterPos; } } 

Answer 2

How about using fractal / recursive? This implementation divides the rectangular range into four quadrants, then gives points from each quadrant. This means that neighboring points in the sequence differ by at least a quadrant.

 #python3 import sys import itertools def interleave(*iters): for elements in itertools.zip_longest(*iters): for element in elements: if element != None: yield element def scramblerange(begin, end): width = end - begin if width == 1: yield begin else: first = scramblerange(begin, int(begin + width/2)) second = scramblerange(int(begin + width/2), end) yield from interleave(first, second) def scramblerectrange(top=0, left=0, bottom=1, right=1, width=None, height=None): if width != None and height != None: yield from scramblerectrange(bottom=height, right=width) raise StopIteration if right - left == 1: if bottom - top == 1: yield (left, top) else: for y in scramblerange(top, bottom): yield (left, y) else: if bottom - top == 1: for x in scramblerange(left, right): yield (x, top) else: halfx = int(left + (right - left)/2) halfy = int(top + (bottom - top)/2) quadrants = [ scramblerectrange(top=top, left=left, bottom=halfy, right=halfx), reversed(list(scramblerectrange(top=top, left=halfx, bottom=halfy, right=right))), scramblerectrange(top=halfy, left=left, bottom=bottom, right=halfx), reversed(list(scramblerectrange(top=halfy, left=halfx, bottom=bottom, right=right))) ] yield from interleave(*quadrants) if __name__ == '__main__': letters = 'abcdefghijklmnopqrstuvwxyz' output = [] indices = dict() for i, pt in enumerate(scramblerectrange(width=11, height=5)): indices[pt] = i x, y = pt output.append(letters[x] + str(y)) table = [[indices[x,y] for x in range(11)] for y in range(5)] print(', '.join(output)) print() pad = lambda i: ' ' * (2 - len(str(i))) + str(i) header = ' |' + ' '.join(map(pad, letters[:11])) print(header) print('-' * len(header)) for y, row in enumerate(table): print(pad(y)+'|', ' '.join(map(pad, row))) 

Outputs:

 a0, i1, a2, i3, e0, h1, e2, g4, a1, i0, a3, k3, e1, h0, d4, g3, b0, j1, b2, i4, d0, g1, d2, h4, b1, j0, b3, k4, d1, g0, d3, f4, c0, k1, c2, i2, c1, f1, a4, h2, k0, e4, j3, f0, b4, h3, c4, j2, e3, g2, c3, j4, f3, k2, f2 | abcdefghijk ----------------------------------- 0| 0 16 32 20 4 43 29 13 9 25 40 1| 8 24 36 28 12 37 21 5 1 17 33 2| 2 18 34 22 6 54 49 39 35 47 53 3| 10 26 50 30 48 52 15 45 3 42 11 4| 38 44 46 14 41 31 7 23 19 51 27 

Answer 3

If your sets X and Y are sizes m and n, and Xi is the index of an element from X that is in the ith pair in your Cartesian product (and is similar for Y), then

 Xi = i mod n; Yi = (i mod n + i div n) mod m; 

You could get your diagonals a bit more common by filling out your matrix as follows:

 for (int i = 0; i < m*n; i++) { int xi = i % n; int yi = i % m; while (matrix[yi][xi] != 0) { yi = (yi+1) % m; } matrix[yi][xi] = i+1; }