首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >鸡方案中的拓扑排序错误?

鸡方案中的拓扑排序错误?
EN

Stack Overflow用户
提问于 2017-06-16 07:07:54
回答 0查看 89关注 0票数 0
代码语言:javascript
复制
#;2> (topological-sort
 '((i am)
   (not trying)
   (confuse the)
   (am trying)
   (trying to)
   (am not)
   (trying the)
   (to confuse)
   (the issue))
  eqv?)
(not i am trying to confuse the issue)

以这种方式对子列表进行排序可能会使正确的输出更加清晰:

代码语言:javascript
复制
   (i am)
   (am not)
   (not trying)
   (trying to)
   (to confuse)
   (am trying)
   (confuse the)
   (trying the)
   (the issue)

看起来这个命令应该是:

代码语言:javascript
复制
i am  not trying to confuse the issue

这是一个bug,还是我漏掉了什么?

--编辑:

将子列表与公共头部相结合:

代码语言:javascript
复制
(topological-sort
 '((i am)
   (not trying)
   (confuse the)
   (am trying not)
   (trying to the)
   (to confuse)
   (the issue))
  eqv?)

(i am not trying to confuse the issue)

因此,似乎正确的方法是对输入进行预处理,以确保没有两个子列表共享相同的头。

解决Rosetta Code拓扑排序问题:

代码语言:javascript
复制
(use srfi-1) ; list operators
(use srfi-69) ; hash-tables

(define data
 '((des_system_lib std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee)
  (dw01             ieee dw01 dware gtech)
  (dw02             ieee dw02 dware)
  (dw03             std synopsys dware dw03 dw02 dw01 ieee gtech)
  (dw04             dw04 ieee dw01 dware gtech)
  (dw05             dw05 ieee dware)
  (dw06             dw06 ieee dware)
  (dw07             ieee dware)
  (dware            ieee dware)
  (gtech            ieee gtech)
  (ramlib           std ieee)
  (std_cell_lib     ieee std_cell_lib)
  (synopsys)))

(define table (make-hash-table))

(for-each
  (lambda (xs)
    (let ((head (car xs)) (tail (cdr xs)))
      (for-each
        (lambda(key)
          (when (not (eqv? key head))
            (hash-table-update!/default
              table key (lambda (accum) (cons head accum)) '())))
        tail)))
  data)

(define answer
  (topological-sort (hash-table->alist table) eqv?))

answer

一个可能的结果(因为哈希表是无序的,所以每次都可能是不同的):

代码语言:javascript
复制
(std ieee dware dw05 dw06 dw07 ramlib std_cell_lib gtech synopsys
 dw02 dw01 des_system_lib dw03 dw04)

正在尝试验证答案:

代码语言:javascript
复制
(any
  (lambda (tail)
    (any
      (lambda (key) 
        (and (hash-table-exists? table key)
             (member (car tail) (hash-table-ref table key))))
      (cdr tail)))
  (reverse (pair-fold cons '() answer)))

#f

这似乎是正确的。

EN

回答

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/44578335

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档