Tcl中的動態列表排序

Question

我想根據動態列表進行一些排序。讓我來解釋 我使用TCL 8.4版，我不能改變，必須使用

list1 = {{a b c} {c b c a} {b b a}} ..... 1st input data 

表1是有3個成員形成不同類型的子列表以任意順序，這將一個Tcl列表甚至每次都會改變。例如接下來的時間，單1將是：

list1 = {{c} {b c a} {b c} {a c a c}} ..... 2nd input data (for next time consideration) 

現在我想給他們以這樣的方式進行排序，如果我使用他們周圍循環或lsort或string compare或任何其他Tcl命令，新的TCL列表應包含基於優先級的個人成員。就像我們有上升/下降一樣。 請注意，這兩種情況下，各個子列表長度都在增加和減少，同時從a，b，c也繼續旋轉。

在我來說，我想「一」擁有最高優先級，然後是「B」，然後選擇「C」（A-> B-> C）

所以輸出爲第一次重複的處理完成後應爲：

$> puts $new_list1 
$> {a a a}   # as out of 3 sublists a is present in them and it gets highest priority. 

同樣，處理後輸出2日反覆做應該是：

$> puts $new_list1 
$> {c a b a} # as you can see that list1 1st element is c so it gets output as is, second sublist has b c and a so `a` gets outputted, 3rd sublist is b and c so `b` gets outputted 

讓我知道你的想法是什麼。

在此先感謝！

Answer 1

首先，我要看看是構建這在某種程度上數據結構，這樣你就不必進行排序的所有子列表，例如，使用算法那樣簡單二進制搜索linsert每個元素成每個子列表的排序索引。第二，我會考慮你是否需要儘可能多的「優化」，你可能會認爲你是這樣做的。通常情況下，最好的解決辦法（由於可維護性）是最明顯的事情：子列表排序，然後使用一個循環，就像這樣：

# construct a new list of sorted sublists 
foreach sublist $list { 
    lappend presorted_list [lsort $sublist] 
} 

# given a reference to a list of sorted lists, simultaneously build (1) a list of 
# each sublist's first element and (2) a list of the each sublist's remaining 
# elements, so that the former can be returned, and the latter can be set by 
# reference for the next iteration (and will have omitted any empty sublists) 
proc process_once {presorted_list_ref} { 
    upvar $presorted_list_ref presorted_list 
    foreach sublist $presorted_list { 
     if {[llength $sublist] > 0} { 
      lappend returning_list [lindex $sublist 0] 
      lappend remaining_list [lrange $sublist 1 end] 
     } 
    } 
    set presorted_list $remaining_list 
    return $returning_list 
} 

set iter_1 [process_once presorted_list] 
set iter_2 [process_once presorted_list] 

我不認爲有什麼更好的辦法做到這一點，如果您無法以預先處理或構建您的原始列表的方式從排序的子列表開始。除非從排序的子列表開始，否則無法確定每個子列表中的哪個項目必須輸出，而不檢查所有項目-因此，您可能需要排序一次，因此您將知道每個子列表始終將第一項我已經編碼在上面。

---

在循環的形式，如果你並不需要在專門的時間來檢索一個迭代，

foreach sublist $list { 
    lappend presorted_list [lsort $sublist] 
} 

while {[llength $presorted_list] > 0} { 

    foreach sublist $presorted_list { 
     if {[llength $sublist] > 0} { 
      lappend returning_list [lindex $sublist 0] 
      lappend remaining_list [lrange $sublist 1 end] 
     } 
    } 

    # 
    # do stuff with $returning_list 
    # 

    set presorted_list $remaining_list 
}