Перечисляя декартово произведение, минимизируя повторение

Question

Учитывая два комплекта и т.д .:

{A B C}, {1 2 3 4 5 6} 

Я хочу, чтобы сгенерировать декартово произведение в порядке, который помещает столько места, сколько возможно между равными элементами. Например, [A1, A2, A3, A4, A5, A6, B1…] не годится, потому что все A s находятся рядом друг с другом. Приемлемое решение будет идти «вниз по диагонали», а затем каждый раз, когда он оборачивает компенсируя один, например:

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

Выраженный визуально:

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

или, что то же самое, но без повторения строк/столбцов :

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

Я полагаю, что есть и другие решения, но об этом мне было легче всего думать. Но я ударяю головой о стену, пытаясь понять, как выражать ее в общем случае - это удобная вещь, когда мощность двух наборов кратно друг другу, но я хочу, чтобы алгоритм выполнял The Right Thing для множеств например, размер 5 и 7. Или размер 12 и 69 (это настоящий пример!).

Существуют ли для этого установленные алгоритмы? Я продолжаю отвлекаться от мысли о том, как рациональные числа отображаются на множество натуральных чисел (чтобы доказать, что они являются счетными), но путь, который он принимает через ℕ × ℕ, не работает для этого случая.

Так получилось, что приложение написано на Ruby, но меня не интересует язык. Pseudocode, Ruby, Python, Java, Clojure, Javascript, CL, абзац на английском языке - выберите ваш любимый.

---

проверка концепции решения в Python (скоро будет портирован на Ruby, и соединился с 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

Если наборы X и Y являются размеры т и п и Xi является индексом элемента из X, который находится в паре го в вашем декартово произведение (и аналогично для Y), то

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

Вы можете получить ваши диагоналей немного больше распространены, заполнив вашу матрицу следующим образом:

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

Answer 3

Как насчет использования фрактальной/рекурсивной? Эта реализация делит прямоугольный диапазон на четыре квадранта, затем дает точки от каждого квадранта. Это означает, что соседние точки в последовательности отличаются по меньшей мере квадрантом.

#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))) 

Выходы:

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 

    | a b c d e f g h i j k 
----------------------------------- 
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