与Scheme中的更多列表相交 [英] Intersect more lists in Scheme

问题描述

我正在尝试与Scheme中的更多列表相交，我需要一点帮助.列表如下所示:

I am trying to intersect more lists in Scheme and I need a little help. The lists look like this:

前两个:

(((?x john) (?city new-york))  
 ((?x mike) (?city chicago))  
 ((?x mary) (?city london)))

和

(((?city chicago))     
 ((?city new-york)))

我需要查看第一个列表中的每个列表(例如A)，看看第二个列表中是否有一个列表(例如B)，以便A与B至少有一个共同点.这样的元素，结果列表将不包含A.上面提到的两个列表的结果将是:

I need to look in every list (say A) from the first list and see if there is a list (say B) in the second one so that A has at least one element in common with B. If there is no such element, the resulting list will not contain A. The result for the two lists mentioned above will be:

(((?x john) (?city new-york))  
 ((?x mike) (?city chicago)))

因为列表((?x mary) (?city london))与(((?city chicago) ((?city new-york)))中的任何列表没有共同点.

since the list ((?x mary) (?city london)) has nothing in common with any list from (((?city chicago) ((?city new-york))).

现在，结果列表必须与下一个列表相交:

Now the resulting list has to be intersected with the next list:

(((?x mike) (?game tennis))  
 ((?x john) (?game air-hockey)))

结果列表中的第一个列表((?x john) (?city new-york))将与((?x john) (?game air-hockey))共用(?x john)，因此在我的新结果列表中，第一个列表如下所示:((?x john) (?city new-york) (?game air-hockey)).按照第二个列表的这种模式，我将得到((?x mike) (?city chicago) (?game tennis))，而新的结果列表将是:

The first list from the resulting list, ((?x john) (?city new-york)) will have (?x john) in common with ((?x john) (?game air-hockey)) and therefore in my new resulting list the first list will look like this: ((?x john) (?city new-york) (?game air-hockey)). Following this pattern with the second list, I will get ((?x mike) (?city chicago) (?game tennis)) and my new resulting list will be:

(((?x john) (?city new-york) (?game air-hockey))  
 ((?x mike) (?city chicago) (?game tennis)))

这意味着，对于具有至少一个共同元素的每两个列表，我必须进行重新团聚并将其添加到新的结果列表中.

This means that, for every two lists that have at least one element in common I have to do their reunion and add it to the new resulting list.

现在我的问题是，您能帮我在Scheme中实现这一点吗?我不需要代码，只有一些关于我应该使用哪些功能的想法:).

Now my question is, can you give me a little help in implementing this in Scheme? I don't want the code, only some ideas regarding which functions should I use :).

推荐答案

我知道您必须使用列表来解决此问题，我不会编写列表实现，因为这样做会很麻烦(这不是适用于的最佳数据结构作业)，我将向您展示如何通过Racket的设置操作解决问题，以便您可以将其转换为使用列表.首先，数据的表示形式:

I understand that you have to solve this with lists, I won't write a list implementation because it'd be cumbersome (it's not the best data structure for the job), instead I'll show you how to solve the problem in terms of Racket's set operations, so you can translate it to use lists. First, a representation of the data:

(define s1 (set (set '(?x john) '(?city new-york))
                (set '(?x mike) '(?city chicago))
                (set '(?x mary) '(?city london))))

(define s2 (set (set '(?city chicago))
                (set '(?city new-york))))

(define s3 (set (set '(?x mike) '(?game tennis))
                (set '(?x john) '(?game air-hockey))))

使用表示形式后，我们需要一个过程，给定单个基准，查找是否与某个数据列表共享某些元素-如果找到一个匹配项，则返回数据的并集；如果不存在，则返回数据的并集.找到返回#f的任何内容:

With the representation in place, we need a procedure that given a single datum finds if it shares some element in common with a list of data - if it finds one match, it returns the union of data, if it doesn't find any it returns #f:

(define (find-match one-set set-of-sets)
  (cond ((set-empty? set-of-sets)
         #f)
        ((not (set-empty? (set-intersect one-set (set-first set-of-sets))))
         (set-union one-set (set-first set-of-sets)))
        (else
         (find-match one-set (set-rest set-of-sets)))))

例如:

(find-match (set '(?x mike) '(?city chicago))
            (set (set '(?x mike) '(?game tennis))
                 (set '(?x john) '(?game air-hockey))))

=> (set '(?x mike) '(?city chicago) '(?game tennis))

现在很容易编写一个将一组数据中的所有元素与另一组数据重复匹配的过程:

Now it's easy to write a procedure that repeatedly matches all elements in one set of data with another set of data:

(define (join s1 s2)
  (let loop ((s1 s1)
             (result (set)))
    (if (set-empty? s1)
        result
        (let ((match (find-match (set-first s1) s2)))
          (if match
              (loop (set-rest s1) (set-add result match))
              (loop (set-rest s1) result))))))

例如，s1和s2(如上定义)之间的第一个匹配如下所示:

For instance, the first match between s1 and s2 (as defined above) would look like this:

(join s1 s2)

=> (set (set '(?x mike) '(?city chicago))
        (set '(?x john) '(?city new-york)))

要在几组数据中查找连续的匹配项，只需根据需要多次调用join，每组数据都会累加结果:

To find successive matches among several sets of data just call join as many times as needed, with each set of data, accumulating the result:

(define (join-all . data)
  (if (empty? data)
      (set)
      (foldr join (first data) (rest data))))

(join-all s1 s2 s3) ; equivalent to (join (join s1 s2) s3)

=> (set
     (set '(?x john) '(?city new-york) '(?game air-hockey))
     (set '(?x mike) '(?city chicago)  '(?game tennis)))

如您所见，最终结果是我们预期的结果.

As you can see, the end result is the one we expected.

这篇关于与Scheme中的更多列表相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！