排序其值對

Question

我有一個字典，看起來像這樣的字典：

未分類：

12 {12 489} 29 {89 12} 27 {301 302} 26 {489 329} 8 {89 302} 55 {44 301} 

我想這樣的排序是：

55 {44 301} 27 {301 302} 8 {89 302} 29 {89 12} 12 {12 489} 26 {489 329} 

正如你可以看到，在大多數情況下，前一個條目的第二個鍵值與以下條目的第一個鍵條目相同。 （12和489在最後兩項中）

這雖然沒有要求。第二個和第三個條目中的302也滿足了第二個和第三個條目中存在的「鏈條」的要求。

我想要做的唯一事情就是以這種方式排序這些條目，使花括號中的值形成一個不間斷的鏈。

如果結果看起來像這個例子，或者它是鏡像的，這並不重要。

從TCL 8.6開始，我可以使用stride來做類似於Sort Tcl dict by value的操作。但我堅持這個（Tcl8.5.9）版本。最簡單的方法是什麼？

Answer 1

我不知道這是最簡單的方法：

set x [dict create 12 {12 489} 29 {89 12} 27 {301 302} 26 {489 329} 8 {89 302} 55 {44 301}] 

# transform the dict into a list of lists 
dict for {k v} $x {lappend unsorted [list $k $v]} 
lappend sorted [lindex $unsorted 0] 
set unsorted [lrange $unsorted 1 end] 

# keep going until there's nothing more to add to the sorted list 
while {[llength $unsorted] != 0} { 
    set changed false 

    for {set idx 0} {$idx < [llength $unsorted]} {incr idx} { 
     set elem [lindex $unsorted $idx] 
     lassign [lindex $elem end] a b 

     set head [lindex $sorted 0 end] 
     set tail [lindex $sorted end end] 

     if {$a in $head || $b in $head} { 
      set sorted [linsert $sorted 0 $elem] 
      set changed true 
     } elseif {$a in $tail || $b in $tail} { 
      lappend sorted $elem 
      set changed true 
     } 

     if {$changed} { 
      set unsorted [lreplace $unsorted $idx $idx] 
      break 
     } 
    } 

    # avoid infinite loop if the unsorted list is not empty, but 
    # contains nothing to add to the sorted list 
    if {! $changed} break 
} 

foreach elem $sorted {dict set y {*}$elem} 

puts "Unsorted: $x" 
puts "Sorted: $y" 

Unsorted: 12 {12 489} 29 {89 12} 27 {301 302} 26 {489 329} 8 {89 302} 55 {44 301} 
Sorted: 55 {44 301} 27 {301 302} 8 {89 302} 29 {89 12} 12 {12 489} 26 {489 329}