1

我想根据动态列表进行一些排序。让我在下面解释一下，我使用的是 tcl 版本 8.4，我无法更改，必须使用它

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

列表 1 是一个 tcl 列表，它有 3 个成员，它们以任意顺序形成不同类型的子列表，甚至每次都会改变。例如下一次，列表 1 将是：

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

现在我想以这样一种方式对它们进行排序，如果我在它们周围使用循环或lsort或string compare或任何其他 tcl 命令，新的 tcl 列表应该包含基于优先级的单个成员。就像我们有上升/下降一样。请注意，在这两种情况下，各个 sub_lists 的长度都在增加和减少，同时从 a、b、c 开始也不断旋转。

就我而言，我希望“a”具有最高优先级，然后是“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.

同样，在第二次迭代完成处理后的输出应该是：

$> 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

让我知道你的想法。

提前致谢 ！

4

1 回答 1

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
}
于 2013-11-15T08:22:46.723 回答