枚举笛卡尔积,同时尽量减少重复

Question

给出两组,例如:

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

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

[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(这是一个真实的例子!).

有没有建立的算法？我一直在分心思考如何将有理数映射到自然数集上(以证明它们是可数的),但是它通过ℕ×path所采用的路径对于这种情况不起作用.

事实上应用程序是用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;
    }
}