检查重复列表的方案功能

我需要编写一个Scheme函数来检查重复条目的列表。我认为我已经将工作流程放在纸上了，我只需要帮助将它从论文中转化为代码。检查重复列表的方案功能

首先我需要检查它是否是一个空的列表。所以，我有...

(define (checkDupe mylist) 
    (if (null? mylist) 
    () 
     (checkDupeB mylist) 
) 
)

然后，我有这种“双递归”，我查了第一个数字对列表的其余部分，然后对列表的其余部分的第二个数字，并等等，当它发现一个匹配时，它会分出一个#t，如果它遇到了结尾并且没有找到匹配，那么函数的结果是#f。问题是我无法将这个递归的东西包裹起来。这是一个家庭作业问题，但我非常喜欢学习这些东西。

有人可以向我扔一些代码，并帮助我通过这个工作吗？

来源

2012-03-06 user1252121

你可能想看看如何设计程序，第2版草案，特别是从第4章开始：http：//www.ccs。 neu.edu/home/matthias/HtDP2e/htdp2e-part2.html。该章介绍了如何系统地处理这类列表问题。 – dyoo 2012-03-06 18:04:53

了解递归，你只需要了解计数。我们用自然数来计算。什么是自然数？它是0或者比自然数多一个。 [想象你是一个巫师]（http://stackoverflow.com/a/19951540/849891）在炎热的干旱沙漠中。你知道附近每个城市的方向;你怎么决定要去？你想找到最近的一个。你怎么能知道到一个城市的距离，而没有实际去那里？你是一个巫师;你创建一份你自己的副本，离这个城市更近一步，并且问*它*作为答案。既然他也是一个巫师，他会重复这个过程。 – 2015-09-11 08:33:50

我猜这是家庭作业。这是一个简单的过程，但是你错过了在您的导航流的情况下，3例出现需要考虑：

如果该列表是空的，会发生什么？这意味着它中没有任何重复项
如果列表的当前元素存在于列表的其余部分中，会发生什么？那么就意味着有一个在列表中的重复（提示：member过程可能是有用的）
如果上述为真，则继续下一个元素

随着进一步的帮助，这里的总体思路，填入空格：

(define (checkDupe mylist) 
    (cond ((null? myList) ???) ; case 1 
     (??? #t)    ; case 2 
     (else ???)))   ; case 3

来源

2012-03-06 12:20:25

有多种方法可以解决问题。这是建议。

写一个辅助函数（IS-元素的列表？x长），如果x在列表L，否则为false返回true。

填空在

(define (contains-duplicate? l) 
    (cond [(list? l) (or <check whether (first l) is in (rest l)> 
         <check where (rest l) contains a duplicate>) 
     [else false]))

来源

2012-03-06 14:47:54 soegaard

迭代通过整个列表再次为每个成员来检查重复可能是昂贵的 - 为O（n^2）。检查邻近重复是便宜得多 - O（n）。如果您不介意更改列表中元素的顺序，则可以通过首先对列表进行排序来使所有重复项相邻。该列表必须由可由某个>运算符进行比较的元素组成。

(define (remove-duplicates xs) 
    (fold-right cons-if-not-duplicate '() (sort xs >)))

该方法的一个优点是它依赖于标准折叠运算符而不是自定义递归。由于这是作业，我将删除cons-if-not-duplicate的定义。

来源

2012-03-08 01:46:52 gcbenison

这是一种方式

(define (has-duplicates? lst) 
    (cond 
    [(empty? lst) #f] 
    [(not (not (member (first lst) (rest lst)))) #t] 
    [else (has-duplicates? (rest lst)) ]))

来源

2015-09-09 19:17:32 JennyToy

这是我的解决方案，虽然未经测试应该工作，

(define rmdup 
    (lambda list 
     (cond 
     ((null? list) '()) 
     ((eq? (car list) (car (cdr list)) (rmdup(cdr list))) 
      (else(cons (car list) (rmdup(cdr list)))))))

算法出声：如果最初的汽车等于下一辆车？首先剁碎，然后再去，否则，保留它，然后继续。这样我们只保留唯一的副本，而不是任何与邻居兄弟的任何东西

来源

2015-10-09 02:56:07 bmc

我修正了你的格式，但我不认为这有效。（提示：（rmdup'（1 2 3 1））会返回什么？ – Foon 2015-10-09 03:06:22

检查重复列表的方案功能

回答

相关问题