Talk:Find the missing permutation

An odd observation...I used a Perl script derived from the Knuth shuffle task to shuffle an ordered list of permutations. I find it interesting that the left two columns show a greater vertical repeat frequency and length than the right two columns. --Michael Mol 06:32, 24 December 2009 (UTC)

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? –Donal Fellows 09:41, 24 December 2009 (UTC)

Prototype Tcl Solution

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

1. 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

}

1. 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

}

1. Get the real list of permutations...

set all [allCharPerms [lindex $have 0]]

1. Find the missing one(s)!

set missing [struct::set difference $all $have] puts "missing permutation(s): $missing"</lang>