1

動的リストに基づいて並べ替えを行いたい。以下で説明させてください。私は変更できない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 リストに優先順位に基づいて個々のメンバーが含まれるように、それらを並べ替えたいと考えています。昇順/降順があるように。どちらの場合も、個々の 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.

同様に、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

あなたの考えを教えてください。

前もって感謝します ！

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]

ソートされたサブリストから始める方法で元のリストを前処理または作成できない場合、これを行うより良い方法はないと思います。ソートされたサブリストから始めない限り、すべての項目を調べることなく、各サブリストのどの項目を出力する必要があるかを決定することはできません。上記でコーディングしました。

ループ形式で、特に一度に 1 つの繰り返しを取得する必要がない場合は、

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 に答える