logo标签列表

枚举笛卡尔积并最小化重复。

algorithmmathenumerationdiscrete-mathematicscartesian-product
5

给定两个集合，例如：

{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
如果基数不是倍数，那么发生的事情就是需要更长的时间来完成循环 - 例如 A1 B2 C3 D1 A2 B3 C1 D2 A3 B1 C2 D3。如果两个数字互质，则在覆盖整个集合之前它们不会循环。因此，您只需要等待循环发生，然后找到尚未被覆盖的符号即可。 - mcdowella
这听起来很像线性代数作业。我认为你解释问题的方式有误。退一步，阅读你的课程材料。问题应该很明显。 - starmole
1
这不是作业。这是我作为爱好项目在Rails中开发的健身应用程序；基本思路是，如果你有六种腹肌锻炼方式，每种方式可以向左、向右或直接进行，那么总共有18种锻炼方式，但你不想每天都做所有的锻炼，如果你每天只做5个，你也不希望它们都在身体的同一侧。因此，该应用程序将计算出所有的组合，然后呈现一个合理的顺序来完成它们。我只是不想用DB模式等东西来污染这个问题——我的核心问题是关于算法的。 - tsm
@tsm：非常抱歉！我一开始误解成了图形问题。 - starmole
3个回答
2
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;
    }
}
谢谢！但是你的其中一个for条件是否需要更改呢？这将始终生成36个组合，而|{ABC} x {123456}|当然是18，我想在某些时候用ABCDEFGH替换ABC。 - tsm
啊，我明白了并且已经让它工作了。你可以在原帖中看到我正在使用什么（好吧，在Python中...最终会用Ruby）。 - tsm
@tsm 我按照你给的算法编程了，如果你有需要可以随意进行编辑。 - Tim Biegeleisen
没问题 - 我只需要让它更通用。它只是将一个 MAX_NUM 更改为 letters.length。 - tsm
2

尝试使用分形/递归的方法如何？该实现将一个矩形范围划分为四个象限，然后从每个象限生成点。这意味着序列中相邻的点至少会因为所在的象限而有所不同。

#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
1
如果你的集合X和Y的大小分别为m和n，Xi是在笛卡尔积中第i个对应元素在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;
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接