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 
}