Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

December 31, 2009

Haiku

As part of his science fair project, my 3rd-grader needed a large number of random strings of 8 digits, in each of which “1” appears four times, and “2”–“5” appear once each.

 #!/usr/bin/ruby

 class Array
   def scramble
     p = dup
     collect { p.delete_at(rand(p.length) - 1) }
   end
 end

 100.times { puts [1,1,1,1,2,3,4,5].scramble.join }
Posted by distler at December 31, 2009 10:55 AM

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2144

5 Comments & 0 Trackbacks

Re: Haiku

Mathematica is pretty good at this kind of things. The package Combinatorica contains a wealth of combinatorial algorithms (it seems to be loaded automatically in the version 7 of Mathematica). Anyway, the full list of numbers satisfying the constraints you stated can be found by using

FromDigits /@ Permutations[{1,1,1,1,2,3,4,5}]

which is very concise. There are 1680 such numbers.

Posted by: Lord Sidious on January 4, 2010 6:11 AM | Permalink | Reply to this

Re: Haiku

By the way, this is a great pedagogical example how to use FromDigits; /@ or Map; as well as Permutations. ;-)

Posted by: Lubos Motl on January 8, 2010 4:54 AM | Permalink | Reply to this

Re: Haiku

Yes, 8!4!=1680 \frac{8!}{4!} = 1680 But one neither wants, nor needs to construct the full list of such permutations, in order to draw 100 randomly-selected ones from among them.

Posted by: Jacques Distler on January 24, 2010 12:29 AM | Permalink | PGP Sig | Reply to this

Re: Haiku

OK, then the following code should do exactly what you wanted:

<< Combinatorica`;
Table[FromDigits[RandomPermutation[{1, 1, 1, 1, 2, 3, 4, 5}]], {100}]

But indeed using Mathematica for this kind of problem is a vast overkill.

Posted by: Lord Sidious on January 24, 2010 9:25 PM | Permalink | Reply to this

Re: Haiku

But indeed using Mathematica for this kind of problem is a vast overkill.

I wouldn’t quite say that. Mathematica does have a built-in function

 RandomPermutation[{}]

that does precisely what I needed (though I did not realize it at the time).

On the other hand, what I enjoyed was the elegantly-simple two-line implementation of that function, which I called “scramble”, as an extension to Ruby’s Array class.

Posted by: Jacques Distler on January 25, 2010 12:43 AM | Permalink | PGP Sig | Reply to this

Post a New Comment