topological-sort Chicken Scheme 中的错误?
topological-sort bug in Chicken Scheme?
#;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)
以这种方式排序子列表可能会更清楚正确的输出应该是什么:
(i am)
(am not)
(not trying)
(trying to)
(to confuse)
(am trying)
(confuse the)
(trying the)
(the issue)
看来顺序应该是:
i am not trying to confuse the issue
这是一个错误,还是我遗漏了什么?
---- 编辑:----
将子列表与普通标头合并:
(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 拓扑排序问题:
(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
一个可能的结果(因为hash-tables是无序的,它可能
每次都不一样):
(std ieee dware dw05 dw06 dw07 ramlib std_cell_lib gtech synopsys
dw02 dw01 des_system_lib dw03 dw04)
正在尝试验证答案:
(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
好像是对的
是的,这是一个已知错误:
#;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)
以这种方式排序子列表可能会更清楚正确的输出应该是什么:
(i am)
(am not)
(not trying)
(trying to)
(to confuse)
(am trying)
(confuse the)
(trying the)
(the issue)
看来顺序应该是:
i am not trying to confuse the issue
这是一个错误,还是我遗漏了什么?
---- 编辑:----
将子列表与普通标头合并:
(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 拓扑排序问题:
(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
一个可能的结果(因为hash-tables是无序的,它可能 每次都不一样):
(std ieee dware dw05 dw06 dw07 ramlib std_cell_lib gtech synopsys
dw02 dw01 des_system_lib dw03 dw04)
正在尝试验证答案:
(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
好像是对的
是的,这是一个已知错误: