给定两个集合,例如:
{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