A Little Off Code, Computers, Photography and Guns

13Mar/090

Power Set Generator

Recently I had a bout of programming withdrawal so I set out to write a power-set generator.

So a little background on the power set. The power set of a given set A is the set containing all subsets of A. Suppose that we have a set:

A = \{x,y,z\}

The power set of A would be:

\mathcal{P}(A) = \left\{\emptyset, \{x\}, \{y\}, \{z\}, \{x, y\}, \{x, z\}, \{y, z\}, \{x, y, z\}\right\}\,\!.

Now looking more carefully at the power set of A you'll notice that it contains 2 to the power of the cardinality of A subsets, always containing the empty set.

2^{|A|} = 8

The code I came up with for this is short and more or less simple:

1
2
3
4
5
6
7
8
9
10
def PowerSet(base):
    power_set = []
    b = len(base)
    map(lambda g: power_set.append(map(lambda x: base[x],
        filter(lambda x: g[x], range(0, b)))),
        map(lambda value: map(lambda x: (value >> x) & 1, range(b - 1, -1, -1)),
        map(lambda value: value ^ (value / 2), range(0, 2**b))))
    return power_set

print PowerSet([1,2,3])

I figured out shortly after I wrote this that I had the right general idea but in this particular case, since I'm not actually using set types... the graycode I'm generating is useless for this sort of thing.

The point of generating graycode for this is that graycode is used for binary counting such that only one digit is changed from one consecutive value to the next. It was originally designed so that mechanical switches in early computers wouldn't cause a race condition while counting fast enough.

In this particular solution using graycode is useful for only having to add one new element to a set at a time which if I were actually using sets, would be faster, but since I'm not, it isn't. I'll probably rewrite it later to make it play nicer with graycode.

The basic procedure here is that given a set A we're going to count from 0 to 2^|A| - 1 and in binary graycode, the 1's determine the elements of the base set that will be added as a new set to the power set and 0's indicate that that element of the base set will be ignored in the current subset.

Tagged as: , , , , , , No Comments
5Mar/091

Free Subversion Hosting

I've been in a very coding-prone mood lately. I've been working on developing a Python ETR (Employee Time Record) script for a friend and his club here at the University of Arizona. The project has grown significantly since I started it and this is one of the first projects in a while that I've developed for someone to use other than myself and I've been wanting a way to manage my code better.

I did some searching for free subversion hosting. I've seen google code hosting before and looked at it's feature set, which is quite complete. In terms of project management google code hosting is probably the best for my needs. Though after reading through more of their help//support section I discovered that there's a maximum project creation limit of 10. Supposedly you can email support at the google code hosting service and work out a deal to get more than 10 projects but that's really a hassle. So I started looking elsewhere. Currently though the PythonETR script is hosted at google code.

I stumbled upon ProjectLocker which looked really promising. It turned out to be a very well put together system you get 300MB of storage and unlimited subversion repositories along with Trac instances for each repository. There's just a big HOWEVER in the middle of what seems to be an awesome service. The however is that there is NO public anonymous subversion access. If you want your projects to be available there's no way for you to allow the public to check out a read-only copy of your project. They also only allow a maximum of 2 user accounts and you count as one of them.

Once I discovered all the limitations of ProjectLocker I kept on searching. The next promising service I found was XP-Dev. XP-Dev pretty much one-up's ProjectLocker on just about everything except a few crucial parts. There's no Trac, they provide their own "project tracking" tools like: stories, blogs, wikis, bugs. There's no real way to associate projects with subversion repositories on this service. You get 1.5GB of storage and as many subversion repositories//projects you want to fill that up with. If all you're looking for is free subversion hosting with no project tracking then this is probably the service for you. Though if you're even the slightest bit paranoid about crypto this service definitely isn't for you. Most of the defaults are for non-SSL connections and the services that allow SSL use a self-signed certificate by XP-Dev. I did discover that they do allow public read-only access to subversion repositories but only if you choose to enable this feature so for private projects you don't have to make them publicly available.

Tagged as: , , , , , , , 1 Comment
21Feb/090

Why ‘A Little Off’?

Thursday afternoon at some arbitrary time I was discussing my frustration with getting some of the code to work on my Arduino with a friend of mine at work. This sort of lead to me showing him the blog post I had written a draft for the night before. He noticed I finally got the syntax highlighting plugin working and he was actually there when I was looking through the different color themes for the code. Eventually I settled on one which almost but didn't quite match the theme for the rest of my blog perfectly.

Until this point I hadn't really thought much about why I named the blog what I did. Except now I have a real reason. Before I just sort of thought... "What will people say when they read these posts... AH HAH! 'A Little Off'!!". This doesn't necessarily mean I know my posts will suck or that nobody will appreciate them for whatever they might actually be worth but... generally my ideas are a little off, good, but a little off. But now I have a real reason: If anyone should ask me "Why 'A Little Off'?" all I'll have to do is say "Take a look at the syntax highlighting on the code".

Tagged as: , No Comments
   

QR Code

Blogroll

Comics

Info

Archives

RSS Recommended Reading