algorithm - 什么是计算笛卡尔积的良好非递归算法？

Question

注意事项

这不是特定于 REBOL 的问题。您可以用任何语言回答。

背景

REBOL language 支持创建特定领域的语言，在 REBOL parlance 中称为“方言”。我为列表理解创建了这样一种方言，REBOL 本身不支持它。

列表理解需要一个好的笛卡尔积算法。

问题

我使用元编程来解决这个问题，方法是动态创建然后执行一系列嵌套的 foreach 语句。它工作得很漂亮。但是，因为它是动态的，所以代码可读性不是很好。 REBOL 不能很好地进行递归。它会迅速耗尽堆栈空间并崩溃。所以递归解决方案是不可能的。

总而言之，如果可能的话，我想用可读的、非递归的“内联”算法替换我的元编程。解决方案可以是任何语言，只要我能在 REBOL 中重现它。 (我几乎可以阅读任何编程语言:C#、C、C++、Perl、Oz、Haskell、Erlang，等等。)

我要强调的是，这个算法需要支持任意数量的集合来“连接”，因为列表理解可以涉及任意数量的集合。

Answer 1

速度提高 3 倍，内存使用量减少(回收次数减少)。

cartesian: func [
 d [block! ] 
 /local len set i res

][
 d: copy d
 len: 1
 res: make block! foreach d d [len: len * length? d]
 len: length? d
 until [
  set: clear []
  loop i: len [insert set d/:i/1   i: i - 1]
  res: change/only res copy set
  loop i: len [
   unless tail? d/:i: next d/:i [break]
   if i = 1 [break]
   d/:i: head d/:i
   i: i - 1
  ]
  tail? d/1
 ]
 head res
]