algorithm - 枚举笛卡尔积同时最小化重复

Question

给定两个集合，例如:

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

我想以在相等元素之间放置尽可能多的空间的顺序生成笛卡尔积。例如，[A1, A2, A3, A4, A5, A6, B1...] 是不好的，因为所有的 A 都彼此相邻。一个可接受的解决方案是“沿着对角线”，然后每次它都将偏移量换行，例如:

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

我想还有其他解决方案，但这是我发现最容易想到的解决方案。但我一直在用头撞墙试图弄清楚如何通用地表达它——这两个集合的基数是彼此的倍数是一件很方便的事情，但我希望算法为集合做正确的事情例如，尺寸 5 和 7。或尺寸 12 和 69(这是一个真实的例子!)。

是否有任何既定的算法？我一直在思考如何将有理数映射到自然数集(以证明它们是可数的)，但它通过 ℕ×ℕ 的路径不适用于这种情况。

碰巧应用程序是用 Ruby 编写的，但我不关心语言。伪代码、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;
    }
}