test
July 22nd, 2010Ruby Script for Combinations and Permutations
July 22nd, 2010Note that there are 27 permutations of a three-item set, but the script below returns 39 because there are 39 ways of combining some or all of the items in a three-item set (i.e. in addition to the 27 permutations of 1, 2, and 3, there are also 12 permutations of 1, 2, or 3.)
The code
Array.class_eval do
# return hash with
# keys being unique elements of self;
# values being number of occurrences of those elements
# similar to SQL select x,count(1) from y group by x
# [1,3,3,9,9,9,9].count_distinct
# => {1=>1, 3=>2, 9=>4}
def count_distinct
c={}
self.each{|x|c[x]=(c[x]||0)+1}
c
end
end
def permute(i,els,perms,options)
els.each{|e|
if (i.size+1)<=options[:max_size]
nxt=i.dup<<e
perms<<nxt if nxt.size>=options[:min_size]
permute(nxt,els,perms,options)
end
}
end
def easy_permute(elements,min=1,max=elements.size)
permutations=[]
options={:min_size=>min,:max_size=>max}
permute([],elements,permutations,options)
permutations
end
def easy_combine(elements,min=1,max=elements.size,max_repetitions=nil)
puts "min is #{min}"
permutations=easy_permute(elements,min,max)
permutations.each{|x|x.sort!}.sort!
permutations.uniq!
permutations.delete_if{|x|
x.count_distinct.values.detect{|y|
y>max_repetitions}} if max_repetitions
permutations
end
Usage and testing…
test_combine=easy_combine(['a','b','c'])
test_combine_3=easy_combine(['a','b','c'],3)
test_combine_3_no_rep=easy_combine(['a','b','c'],3,3,1)
test_permute=easy_permute(['a','b','c'])
test_permute_3=easy_permute(['a','b','c'],3)
msg= "=========================\n"
msg<<"COMBINATIONS (#{test_combine.size})\n"
test_combine.each {|x|msg<<x.join(',')<<"\n"};nil
msg<<"=========================\n"
msg<<"COMBINATIONS OF 3 (#{test_combine_3.size})\n"
test_combine_3.each {|x|msg<<x.join(',')<<"\n"};nil
msg<<"=========================\n"
msg<<"COMBINATIONS OF 3 WITH NO REPETITION (#{test_combine_3_no_rep.size})\n"
test_combine_3_no_rep.each {|x|msg<<x.join(',')<<"\n"};nil
msg<<"=========================\n"
msg<<"PERMUTATIONS (#{test_permute.size})\n"
test_permute.each {|x|msg<<x.join(',')<<"\n"};nil
msg<<"=========================\n"
msg<<"PERMUTATIONS OF 3 (#{test_permute_3.size})\n"
test_permute_3.each {|x|msg<<x.join(',')<<"\n"};nil
puts msg
========================= COMBINATIONS (19) a a,a a,a,a a,a,b a,a,c a,b a,b,b a,b,c a,c a,c,c b b,b b,b,b b,b,c b,c b,c,c c c,c c,c,c ========================= COMBINATIONS OF 3 (10) a,a,a a,a,b a,a,c a,b,b a,b,c a,c,c b,b,b b,b,c b,c,c c,c,c ========================= COMBINATIONS OF 3 WITH NO REPETITION (1) a,b,c ========================= PERMUTATIONS (39) a a,a a,a,a a,a,b a,a,c a,b a,b,a a,b,b a,b,c a,c a,c,a a,c,b a,c,c b b,a b,a,a b,a,b b,a,c b,b b,b,a b,b,b b,b,c b,c b,c,a b,c,b b,c,c c c,a c,a,a c,a,b c,a,c c,b c,b,a c,b,b c,b,c c,c c,c,a c,c,b c,c,c ========================= PERMUTATIONS OF 3 (27) a,a,a a,a,b a,a,c a,b,a a,b,b a,b,c a,c,a a,c,b a,c,c b,a,a b,a,b b,a,c b,b,a b,b,b b,b,c b,c,a b,c,b b,c,c c,a,a c,a,b c,a,c c,b,a c,b,b c,b,c c,c,a c,c,b c,c,c
Ruby Script for Combinations
July 16th, 2010Say you have the set 1,2,3,4,5,6 and you want to know all combinations, not permutations, of the set. Here is a Ruby script to do so.
elements=[1,2,3,4,5,6]
t1=Time.now
combinations=[]
elements.each_with_index do |element,i|
# the by-itself combination
combinations<<[element]
# the last item's combinations are already defined
unless i==elements.size-1
elements[(i+1)..(elements.size-1)].each do |next_element|
combinations<<(combinations.last.dup<<next_element)
end
end
end
t2=Time.now
combinations.each {|c|puts c.join(',')}
puts "it took #{(t2-t1)*1000}ms to generate this set"
and the output:
1 1,2 1,2,3 1,2,3,4 1,2,3,4,5 1,2,3,4,5,6 2 2,3 2,3,4 2,3,4,5 2,3,4,5,6 3 3,4 3,4,5 3,4,5,6 4 4,5 4,5,6 5 5,6 6 it took 8ms to generate this set
It also works with words. The real-world case for this is that I’m working on a keyword co-occurrence database. I want to know, out of a given set of survey responses, the frequency of words which appear in the same sentence. For the given sentence I love Ruby, it is such a great programming language — and powerful, too., with the common words removed…
elements=["love","Ruby","great","programming","language","powerful"]
and the output:
love love,Ruby love,Ruby,great love,Ruby,great,programming love,Ruby,great,programming,language love,Ruby,great,programming,language,powerful Ruby Ruby,great Ruby,great,programming Ruby,great,programming,language Ruby,great,programming,language,powerful great great,programming great,programming,language great,programming,language,powerful programming programming,language programming,language,powerful language language,powerful powerful it took 13ms to generate this set
This script doesn’t handle large sets!
elements=(1..500).to_a it took 30819ms to generate this set elements=(1..5000).to_a #my computer crashed from lack of memory!
But if you can reduce the depth of combinations…
There isn’t much value (at least in the context of what I am doing!) in indexing every possible combination of words in a large text. Really, I only need maybe four-word combinations. This script will work with a large text because the result set is relatively small because it limits the combination depth to three elements.
max=3
elements=[1,2,3,4,5,6]
t1=Time.now
combinations=[]
elements.each_with_index do |element,i|
# the by-itself combination
combinations<<[element]
# the last item's combinations are already defined
unless i==elements.size-1
elements[(i+1)..(elements.size-1)].each do |next_element|
c=combinations.last.dup<<next_element
c.delete_at(1) until c.size<=max
combinations<<c
end
end
end
t2=Time.now
combinations.each {|c|puts c.join(',')}
puts "it took #{t2-t1}ms to generate this set"
1 1,2 1,2,3 1,3,4 1,4,5 1,5,6 2 2,3 2,3,4 2,4,5 2,5,6 3 3,4 3,4,5 3,5,6 4 4,5 4,5,6 5 5,6 6 it took 13ms to generate this set
Now I can work with large texts!
elements=(1..5000).to_a it took 28370ms to generate this set
Now I have what I need to build a database index representing combinations of words in sentences. From there, I can find all sentences with, say, powerful and language in them (because all sentences will be indexed according to the combinations of words that appear in them). However, knowing to look for powerful and language in advance is not my goal -- I want the database to tell me the most frequent co-occurrences, so that I can examine them. My goal is to have the database tell me, in essence, the most common combination of words the combination of problem and feature so that I can pinpoint what people are talking about without having to read every single sentence. (I'm pretty sure this is impossible since people might not use the same terminology even though they're all talking about the same thing).
But more on this topic later...
Set Modified Time to Date and Time Picture was Taken (in Linux)
May 22nd, 2010Oh no! I just moved 3 gigs of pictures, afterwards realizing that the modified-time was changed from the time the picture was taken to the time the file was moved. What a mess, I thought, since I always refer to the modified-time when I wonder when a picture was taken.
exiv2 and touch to the rescue!
exiv2 will tell you, among a ton of other things, the time the picture was taken, and touch will allow you to change the modified-time of the image.
Note:Any command below, spread across multiple lines, is done so for clarity. To use the command, the line breaks must be removed such that the entire command is on one line!
This is the output of exiv2:
File name : my_picture.jpg File size : 77443 Bytes MIME type : image/jpeg Image size : 425 x 543 Camera make : Canon Camera model : Canon PowerShot SD1100 IS Image timestamp : 2010:04:26 20:06:07 Image number : 100-2025 Exposure time : 1/60 s Aperture : F4.9 Exposure bias : 0 Flash : Yes, auto, red-eye reduction Flash bias : 0 EV Focal length : 18.6 mm Subject distance: 266 ISO speed : 250 Exposure mode : Easy shooting (Auto) Metering mode : Multi-segment Macro mode : Off Image quality : Fine Exif Resolution : 1848 x 2360 White balance : Auto Thumbnail : JPEG, 7866 Bytes Copyright : Exif comment :
Now you just use grep to find the Image timestamp line:
exiv2 my_image.jpg | grep timestamp Image timestamp : 2010:04:26 20:06:07
Now use awk to massage that date into almost the touch-required format of YYYYMMDDHHMM.SS
exiv2 my_image.jpg |
grep timestamp |
awk '{split($5,t,":");print $4,t[1],t[2],".",t[3]}'
2010:04:26 20 06 . 07
Now use sed to remove the space and colons to complete the formatting
exiv2 my_image.jpg |
grep timestamp |
awk '{split($5,t,":");print $4,t[1],t[2],".",t[3]}' |
sed 's/[:, ]//g'
201004262006.07
And the final command, to actually touch an image:
touch my_image.jpg -t
`exiv2 my_image.jpg |
grep timestamp |
awk '{split($5,t,":");print $4,t[1],t[2],".",t[3]}' |
sed 's/[:, ]//g'`
For an entire directory:
find *.jpg |
while read f; do
touch "${f}" -t `
exiv2 "${f}" |
grep timestamp |
awk '{split($5,t,":");print $4,t[1],t[2],".",t[3]}' |
sed 's/[:, ]//g'`;
done
Use ImageMagick’s convert Command Instead of jpegorient in KDE
May 19th, 2010
One annoying thing that has plagued my laptop is that right-clicking a JPEG in Dolphin makes a menu fly out with unusable options to rotate and flip the image. They don’t work because jpegorient doesn’t come with openSUSE 11.1, and I don’t know what it is or how to get it. I’ve been using the convert command (a part of ImageMagick) from a command line, so I wondered if I could make the Actions menu use it as well.
I edited the ServiceMenu file for the Actions menu, which is at /usr/share/kde4/services/ServiceMenus/jpegorient.desktop on my computer. You can execute locate jpegorient.desktop or find jpegorient.desktop if you don’t see it at that path. The changes are below in bold.
Name=Rotate Clockwise
Icon=object-rotate-right
Exec=convert -rotate 90 %F %F
[Desktop Action jpegRot270]
Name=Rotate Counter-Clockwise
Icon=object-rotate-left
Exec=convert -rotate 270 %F %F
#[Desktop Action jpegRot180]
#Name=Rotate 180
#Icon=misc
#Exec=jpegorient +180 %F
[Desktop Action jpegFlipV]
Name=Flip Vertically
Icon=2uparrow
Exec=convert -flip %F %F
[Desktop Action jpegFlipH]
Name=Flip Horizontally
Icon=2rightarrow
Exec=convert -flop %F %F
SSH Without Password
May 18th, 2010I was looking for a quick and dirty way to SSH into a handful of hosts. I SSH into these hosts all day long, and I was looking for a way to skip the password prompt (I’m way too much into efficiency — every second counts!). I wasn’t interested in learning how to set up the public/private key authentication. I just wanted to automate the login so all I would need to type is goto host. Obviously this is less than secure, but I’m not overly concerned with security at my workstation.
Here’s what I came up with:
1) a file named goto.passwd
– which contains hostnames, usernames, and passwords (e.g. myhost myuser mypassword)
2) a script named goto
– which accepts one parameter (e.g. goto myhost)
– parses the goto.passwd file looking for that host
– and then passes that info to
3) a script borrowed from here
– and slightly modified.
Here is an example (the command is simply goto myhost and I’m instantly in.):
spawn ssh user@myhost
user@myhost’s password:
Last login: Tue May 18 11:31:05 2010 from 1.2.3.4
-bash-3.2$
Here are the scripts (you can also download them as a zip or tar):
goto.passwd
myhost root password myotherhost root passwordforroot anotherhost root password12345
goto
#!/bin/bash
host=$1
user=`cat goto.passwd | grep -e ^$host | awk '{print $2}'`
pass=`cat goto.passwd | grep -e ^$host | awk '{print $3}'`
goto.expect $user $pass $host
goto.expect
omitted. see zip or tar file below.
Viewing very large log files
April 15th, 2010Someone came to me today and asked if I could track down a 403 error that was handed to a user the morning of 4/13/2010. The web server log file is 465 megs. Gulp. sed and grep to the rescue!
Just pick a random number (representing a wild guess at where, in the log file, your starting point may be) and use sed -n 2000p where 2000 is your random number. My original guess was way off. The time period in question ended up spanning lines 500,000 to 680,000 in the server log. Great, just read 180,000 lines, right? WRONG! Use grep. Here’s the final string of commands I used.
# just to locate the correct line... sed -n 2000p site-access_log sed -n 12000p site-access_log sed -n 100000p site-access_log sed -n 300000p site-access_log sed -n 500000p site-access_log sed -n 680000p site-access_log # now to search that time period for a 403 error sed -n 500000,685000p site-access_log | grep ' 403'
Not perfect, but good enough to get the job done. sed whittled the 465 meg file down to 180,000 lines, and grep whittled that down to 50 or so lines, some of which were relevant, others not.
chmod +x on the script folder
February 10th, 2010A handful of my Rails apps were created in a Windows development environment… Which means that the files in the script directory do not have the +x permission, which means I have to type ruby script/console instead of just script/console… SVN doesn’t see adding the execute permission to a file as being a change, so you can’t commit it by simply changing the permissions… So I wrote a script to copy the script folder, delete it, check it in, restore it, add execute permission, and check it back in. Ahh, I don’t have to type ruby anymore!
svn export script script2 svn delete script svn commit -m "temporarily deleted script/*" mv script2 script svn add script sudo chmod +x script/* svn commit -m "restored script/* with +x"
svn delete script
svn commit -m “deleted script/* so that i could chmod +x and check back in”
mv script2 script
svn add script
sudo chmod +x script/*
svn commit -m “deleted script/* so that i could chmod +x and check back in”
How to Buy Books
January 15th, 2010I only give free advertising to truly exceptional companies. BookFinder.com is one of them. I have spent wasted countless hours looking for the best price on books from the usual suspects: Amazon, eBay, and half.com. No longer! BookFinder.com quickly and easily locates books from a multitude of sellers and includes the shipping cost in the price. And if you have trouble with the site, their customer service is fast and friendly. Two thumbs up for BookFinder.com!
Convert Inches to Feet and Inches
January 6th, 2010I love simple problems, such as fill a drop-down with a range of feet and inches.
One way to do it is to hand-code a <select> element and fill it with hand-coded <option> elements, but what’s the fun in that?
It’s more fun to iterate over an array (range) of integers representing inches, and do the math to convert those inches to feet and inches. To get feet, use the floor function, which truncates all decimal places without rounding. To get inches, use the modulus operator (the % operator) which returns the remainder. 36 is 3′0″ and 74 is 6′2″.
The math is the same but (as John Madden would say, if he were a programmer) the syntax varies by language… Here’s how you do it in Ruby:
<%= select :person,
:height,
(36..95).collect{|i|["#{(i/12).floor}' #{i%12}\"",i]},
{:selected=>@person.height} %>
And here’s what you end up with:
And unformatted:
