LISP中两个位向量之间的距离

Question

我在使用常见的lisp计算两个位向量之间的距离时遇到问题.

我是lisp的新手,这是我的人工智能家庭作业的最终作业问题,并且相信我遇到的问题是语法问题.

这是一个问题:

在由1和0的列表表示的相同长度的两个位向量之间写入递归函数DISTANCE.例如,

(距离'(1 0 1 1)'(0 1 0 1))

答案 - 3

如果向量长度不同,讨论必须做什么.

根据我的理解,两个位向量之间的距离只是对两个向量进行异或,然后向上计数1.

使用这个例子,我们将得到1011 ^ 0101 = 1110,它等于3.

假设这是计算距离的正确方法,那么我的问题是除了使这个递归之外还找到一种在lisp中进行异或的方法.

我如何获取两个列表并将它们放入我可以使用logxor (如此处所示)之类的格式中,然后在结果列表中计算1？

虽然尝试这样做(logxor '(1 0 1 1) '(0 1 0 1))告诉我'(1 0 1 1)不是一个整数所以它似乎logxor不适用于让我不知所措的列表.

您可以提供的任何帮助将不胜感激

谢谢!

Answer 1

你的问题提到"位向量",但你实际上是在使用位列表.但是Common Lisp实际上提供了一种bit-vector类型.这是一种特殊类型的数组.但它仍然是一个向量,所以你可以使用适用于任意序列(向量或列表)的序列函数,因此你可以编写一个适用于位向量的解决方案以及其元素为位的任何其他序列.map:

(defun distance (bits1 bits2)
  (reduce '+ (map 'bit-vector 'logxor bits1 bits2)))

它按预期工作,但请注意,您可以使用位向量(您可以使用#*…表示法轻松编写)以及列表.你没有这种灵活性mapcar,它只适用于列表.还要注意使用(reduce '+ …)而不是(apply '+ …).有两个原因

1. reduce 适用于任意序列,因此您可以将它与矢量和列表一起使用.
2. apply是call-arguments-limit可以传递给函数的最大参数数量.虽然这里的小案例不会与此相反,但如果你有更大的位向量,你可能会遇到这个问题.

CL-USER> (distance #*1011 #*0101)
3
CL-USER> (distance '(1 0 1 1) '(0 1 0 1))
3
CL-USER> (distance #*1011 '(0 1 0 1))
3

Rainer Joswig的回答指出你也可以用整数做位操作.因为这是一个非常合理的事情(特别是因为你可以使用二进制整数表示法),所以值得制作一个适用于它的版本.这是一个实现,它将所有参数转换为整数(无论它们是否已经是整数或位序列)并使用(logcount (logxor … …)):

(defun distance (bits1 bits2)
  (flet ((to-int (bits)
           (if (integerp bits) bits
               (reduce (lambda (int bit)
                         (logior (ash int 1) bit))
                       bits))))
    (logcount (logxor (to-int bits1) (to-int bits2)))))

CL-USER> (distance #b1011 '(0 1 0 1))
3
CL-USER> (distance #*1011 '(0 1 0 1))
3
CL-USER> (distance #*1011 5)
3
CL-USER> (distance 11 5)
3