在时间n^2/2的情况下，在Clojure进行碰撞检查的迭代如何

Question

我对检测碰撞不感兴趣。

我已经习惯了将两个计数器在两个循环中使用Java的方法：

：

第一个循环在所有对象上解析并包含第二个循环。它的计数器是要检查所有其他对象的当前对象的索引。

循环的第二个解析所有未选中的对象。它的计数器是当前正在检查第一个循环所查看的对象的未检查对象的索引。

伪代码：

for(i++)
  for(int j = i, j++)
   collides(objects[i], objects[j)

这是如何在clojure中实现的？

我非常习惯使用没有计数器的map之类的命令，我想知道这种方法是否真的需要计数器。如果有一种方法可以在没有计数器的情况下进行此操作。

我还想明确表示我不想随时间 n^2实施。相反，我想拥有时间n^2/2方法，该方法仅检查未检查的对象以进行碰撞。

Answer 1

您可以通过A进行相同的代码：

(for [i (range (count objs))
      j (range i (count objs))
      :when (collide? (nth objs i) (nth objs j))]
    ...do stuff...)

如果您使用loop，它将运行速度更快，但看起来可能不会那么好。

Answer 2

选择不使用计数器的所有碰撞的对碰撞的对：

(defn select-pairs [collide? objects]
  (for [tail (iterate rest objects) :while (seq tail)
        :let [x (first tail)], y tail :when (collide? x y)]
    [x y]))

例如，

(select-pairs < (range 4))
;([0 1] [0 2] [0 3] [1 2] [1 3] [2 3])

• 这将适用于任何序列，甚至是无尽的序列。
• collide?只是选择对的标准的名称。