Talk:Find the missing permutation: Difference between revisions

Content added Content deleted
(Maybe this is a fault in the Perl shuffler?)
Line 2: Line 2:
: Looking at it, I suspect that the Perl impl of that task has a bug in it; it doesn't appear to always guarantee to consider shuffling the first element. (I think. I might have also misread it.) For the Tcl version, what I did was do some frequency analysis to check whether the shuffle was fair; we shuffled the list 1,2,3,4,5 a hundred thousand times and counted up the total for each position in the list across all the runs; when the total for each column was close to 300k, we had a reasonable estimate that there weren't any subtle errors. (We checked for gross errors by eyeballing it.) My perl is very rusty though, so I'm not quite sure how to write the same thing. Perhaps later...
: Looking at it, I suspect that the Perl impl of that task has a bug in it; it doesn't appear to always guarantee to consider shuffling the first element. (I think. I might have also misread it.) For the Tcl version, what I did was do some frequency analysis to check whether the shuffle was fair; we shuffled the list 1,2,3,4,5 a hundred thousand times and counted up the total for each position in the list across all the runs; when the total for each column was close to 300k, we had a reasonable estimate that there weren't any subtle errors. (We checked for gross errors by eyeballing it.) My perl is very rusty though, so I'm not quite sure how to write the same thing. Perhaps later...
: Do you want me to add in the Tcl solution for this task? –[[User:Dkf|Donal Fellows]] 09:41, 24 December 2009 (UTC)
: Do you want me to add in the Tcl solution for this task? –[[User:Dkf|Donal Fellows]] 09:41, 24 December 2009 (UTC)

== Prototype Tcl Solution ==

<tt><nowiki>=={{header|Tcl}}==</nowiki><br>
<nowiki>{{libheader|tcllib}}</nowiki></tt>
<lang tcl>package require struct::list
package require struct::set

# Make complete list of permutations of a string of characters
proc allCharPerms s {
set perms {}
set p [struct::list firstperm [split $s {}]]
while {$p ne ""} {
lappend perms [join $p {}]
set p [struct::list nextperm $p]
}
return $perms
}

# The set of provided permutations (wrapped for convenience)
set have {
ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA CBAD ABDC
ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB
}
# Get the real list of permutations...
set all [allCharPerms [lindex $have 0]]
# Find the missing one(s)!
set missing [struct::set difference $all $have]
puts "missing permutation(s): $missing"</lang>
Retrieved from "https://rosettacode.org/wiki/Talk:Find_the_missing_permutation"