Talk:Find the missing permutation

Perl shuffle

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)

Hmm, when I test the Perl shuffle code with: <lang perl>my @tot = (0, 0, 0, 0, 0); for my $x (1 .. 100000) {

 my @a = shuffle(1, 2, 3, 4, 5);
 for (0 .. 4) {
   $tot[$_] += $a[$_];
 }

} print "totals: @tot\n"</lang> I get totals that indicate that things are OK. Not sure what's wrong then, if anything. Don't think it really matters though; the list of permutations doesn't have an obviously missing element, so a short program is indeed the best way to find the missing item. –Donal Fellows 10:31, 24 December 2009 (UTC)

I wrote that function. I based it closely on the Wikipedia pseudocode, and I was especially careful to avoid fencepost errors. I'm pretty sure it's correct. —Underscore (Talk) 12:56, 24 December 2009 (UTC)

I suspect that it was just someone forgetting that every permutation should be equally likely, even the “unlikely” ones. The testing code indicates fairness (or balanced wrongness of course, but I can't conceive of that code doing it). –Donal Fellows 13:15, 24 December 2009 (UTC)

Heh. I didn't try running several times, so that one result set definitely isn't a representative sample. However I do use that Perl script for a few other things at home (It's great for shuffling things before they get to xargs when doing find-based playlists). I tried adding a reverse and reshuffle stage (the Knuth shuffle itself sits in its own function), and had elements pop up near the beginning of the list I'd forgotten I'd even had. That suggests to me there's something broken about my Perl implementation's rand function. As the Wp artical mentions, your shuffle quality is limited by your source of random numbers. I'll write a program some time today to do a more representative search and check of the results I noticed. --Michael Mol 16:05, 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>

Which version of Tcl does that require? struct::list Doesn't seem to come with Ubuntu 9.10's Tcl v 8.5:

shortcircuit@dodo~
11:27:02 $ tclsh8.
tclsh8.4  tclsh8.5  
shortcircuit@dodo~
11:27:02 $ tclsh8.5 missing.tcl 
can't find package struct::list
    while executing
"package require struct::list"
    (file "missing.tcl" line 1)
shortcircuit@dodo~
11:27:11 $

--Michael Mol 16:30, 24 December 2009 (UTC)