CODEWITHSUNDEEP
tcl
Theoretical Physics
Theoretical Physics

Reputation: 1

Code creating randomly positive integers in given range in tcl

My question is related to a tcl code which I found here:

Generate random number within specified range without REDUNDANCY in TCL

The code has been suggested as an answer to the question on the above side and it looks as follows:

set r -1;              # Some value that definitely isn't in the sequence
for {set i 1} {$i < 31} {incr i} {
    upvar 0 fnode($i) fnod($i)
    while {$r == [set r [myRand 1 20]]} {
        # Empty body
    }
set fnod($i) $r;   # Random number is generated between 1 to 20 
}

I would like to understand it but I am confused because of this line:

upvar 0 fnode($i) fnod($i)

Why is this line in the code? The first array, fnode($i), does not occur earlier in the code. Therefore, it is should not be possible to apply upvar to it. And there doesn't seem to be any reason to introduce an alias fnod($i) for it.

Another important point: Why does this code guarantee that among 30 randomly generated numbers, 20 of them are distinct?

In the above code, myRand is the following proc (also suggested on the same side and by the same author):

proc myRand {min max} {
    set range [expr {$max - $min + 1}]
    return [expr {$min + int(rand() * $range)}]
}

It generates randomly an integer in the range [min, max].

I should also add: This code does not run in TclTutor 3.0b6. I get the following error message:

--------
bad variable name "fnod(1)": upvar won't create a scalar variable that looks like an array element
    while executing
"upvar 0 fnode($i) fnod($i)"

Any help is welcome.

Thank you in advance!

Upvotes: 0

Views: 371

Answers (1)

Donal Fellows
Donal Fellows

Reputation: 137667

When you're looking for a group of unique random numbers, there are three cases to consider:

  1. The number of values you are looking for is larger than the number of unique random values that you could choose. This must be an error.

  2. The number of values you are looking for is only a bit smaller than the number of unique random values that you could choose. In this case, the simple approach is to shuffle the set of candidates and take a leading slice of the shuffled sequence. (Or a trailing slice, it doesn't actually matter. Leading is just slightly simpler to implement.)

    proc randomByShuffle {n lowerInclusive upperExclusive} {
    # Generate
    set values {}
    for {set i $lowerInclusive} {$i < $upperExclusive} {incr i} {
        lappend values $i
    }
    # Shuffle
    for {set i 0} {$i < [llength $values] - 1} {incr i} {
        set idx [expr {int(rand() * ([llength $values] - $i)) + $i}]
        # Swap
        set tmp [lindex $values $idx]
        lset values $idx [lindex $values $i]
        lset values $i $tmp
    }
    # Result slice
    return [lrange $values 0 $n]
}

set numbers [randomByShuffle 20 10 35]

    While this approach has the disadvantage of generating a list of all the values you could choose, it doesn't have any weird problems with taking a long time to finish; the amount of work to generate that working list is similar to the cost to generate the minimum number of values required for a simple sequence of that length

  3. The number of values you are looking for is a lot smaller than the number of unique random values that you could choose. In this case, you track what values you've picked and redraw a value if you would otherwise get a duplicate.

    proc randomBySelection {n lowerInclusive upperExclusive} {
    set range [expr {$upperExclusive - $lowerInclusive}]
    set result {}
    while {[llength $result] < $n} {
        set x [expr {int(rand() * $range) + $lowerInclusive}]
        # Only append value to result if this is first time we've seen it
        if {[incr count($x)] == 1} {
            lappend result $x
        }
    }
    return $result
}

set numbers [randomBySelection 20 258 65432]

I've not tested when the costs make switching from one model to the other a good idea. (If you're working with floating point numbers instead of integers, you can probably always use the selection method as the random numbers will almost never overlap.)

Upvotes: 1

Related Questions