LINUX.ORG.RU

История изменений

Исправление TeopeTuK, (текущая версия) :

Держи вот прототип реализации (иногда с загадочными решениями типа выбор K наибольших значений сортировкой): 

#!/usr/bin/tclsh

set K 5

set graph {
    {{} {Desktop 0 Smartphone 0 Server 0}}
    {Desktop {Windows 9 Linux 6 Android 3}
     Smartphone {Windows 6 Linux 3 Android 9}
     Server {Windows 6 Linux 9 Android 3}}
    {Windows {ARM 3 x86 9 MIPS 3}
     Linux {ARM 9 x86 9 MIPS 3}
     Android {ARM 9 x86 6 MIPS 6}}
    {ARM {Intel 6 AMD 3 Toshiba 3}
     x86 {Intel 9 AMD 9 Toshiba 3}
     MIPS {Intel 3 AMD 3 Toshiba 6}}
}

proc bestK {graph {K 1}} {
    if {[llength $graph] == 1} {
        return $graph
    } else {
        set start [lrange $graph 0 end-2]
        set end1 [lindex $graph end-1]
        set end [lindex $graph end]
        set res [dict create]
        dict for {key val} $end1 {
            dict for {key1 val1} $val {
                dict for {key2 val2} [dict get $end $key1] {
                    dict lappend res $key [concat $key1 $key2] [expr {$val1+$val2}]
                }
            }
        }
        dict for {key val} $res {
            dict set res $key [lrange [lsort -integer -decreasing -stride 2 -index 1 $val] 0 [expr {2*$K-1}]]
        }
        tailcall bestK [linsert $start end $res] $K
    }
}

puts [bestK $graph $K]

Исходная версия TeopeTuK, :

Держи вот прототип реализации (иногда с загадочными решениями типа выбор K наибольших значений сортировкой): 

#!/usr/bin/tclsh

set K 5

set graph {
    {{} {Desktop 0 Smartphone 0 Server 0}}
    {Desktop {Windows 9 Linux 6 Android 3}
     Smartphone {Windows 6 Linux 3 Android 9}
     Server {Windows 6 Linux 9 Android 3}}
    {Windows {ARM 3 x86 9 MIPS 3}
     Linux {ARM 9 x86 9 MIPS 3}
     Android {ARM 9 x86 6 MIPS 6}}
    {ARM {Intel 6 AMD 3 Toshiba 3}
     x86 {Intel 9 AMD 9 Toshiba 3}
     MIPS {Intel 3 AMD 3 Toshiba 6}}
}

proc bestK {graph {K 1}} {
    if {[llength $graph] == 1} {
        return $graph
    } else {
        set start [lrange $graph 0 end-2]
        set end1 [lindex $graph end-1]
        set end [lindex $graph end]
        set res [dict create]
        dict for {key val} $end1 {
            dict for {key1 val1} $val {
                dict for {key2 val2} [dict get $end $key1] {
                    dict lappend res $key [concat $key1 $key2] [expr {$val1+$val2}]
                }
            }
        }
        dict for {key val} $res {
            dict set res $key [lrange [lsort -integer -decreasing -stride 2 -index 1 $val] 0 [expr {2*$K-1}]]
        }
        return [bestK [linsert $start end $res] $K]
    }
}

puts [bestK $graph $K]