How to create an efficient permutation algorithm in Tcl?

Theoretical Physics 0
Viewed 41

I have written the following proc in tcl which gives a permutation of the set {1, 2, ..., n} for some positive integer n:

proc permu {n} {
   set list {}
   while {[llength $list] < $n} {
     set z [expr 1 + int(rand() * $n)]
     if {[lsearch $list $z] == -1} {
        lappend list $z
     }
   }
return $list
}

I have used some code snippets from tcl-codes which I found on other web sites in order to write the above one. The following part of the code is problematic:

[lsearch $list $z] == -1

This makes the code quite inefficient. For example, if n=10000 then it takes a few seconds until the result is displayed and if n=100000 then it takes several minutes. On the other hand, this part is required as I need to check whether a newly generated number is already in my list.

I need an efficient code to permute the set {1, 2, ..., n}. How can this be solved in tcl?

Thank you in advance!

tcl
1 Answers

Looking up a value in a list is a problem that grows in runtime as the list gets larger. A faster way is to look up a key in a dictionary. Key lookup time does not increase as the size of the dictionary increases.

Taking advantage of the fact the Tcl dictionary keys are ordered by oldest to most recent:

proc permu {n} {
   set my_dict [dict create]
   while {[dict size $my_dict] < $n} {
     set z [expr 1 + int(rand() * $n)]
     if {![dict exists $my_dict $z]} {
         dict set my_dict $z 1
     }
   }
   return [dict keys $my_dict]
}

This fixes the problem of slow list lookup, but the random number z is now the limiting factor. As the dict size approaches $n you need to wait longer and longer for a new value of z to be a unique value.

A different faster approach is to first assign the numbers 1 to n as value to randomized keys in a dict. Next, you can get values of each sorted key.

proc permu2 {n} {
    # Add each number in sequence as a value to a dict for a random key.
    set random_key_dict [dict create]
    for {set i 1} {$i <= $n} {incr i} {
        while {1} {
            set random_key [expr int(rand() * $n * 100000)]
            if {![dict exists $random_key_dict $random_key]} {
                dict set random_key_dict $random_key $i
                break
            }
        }
    }

    # Sort the random keys to shuffle the values.
    set permuted_list [list]
    foreach key [lsort -integer [dict keys $random_key_dict]] {
        lappend permuted_list [dict get $random_key_dict $key]
    }

    return $permuted_list
}
Chris Heithoff0
Related