Wednesday, March 02, 2005

Permuting the Smart Way

Once again, I have a neat algorithm to share so feel free to skip this paragraph if you're not computer-savvy. What if you have a set of numbers and you want to find all the different combinations you can get, but in order? It sounds like a good idea if you ever want to permute a bunch of numbers since it would make it easier to search within it and for whatever other operations you want. So check this out:
public static boolean nextPermutation (long[] a) {
    if (a.length < 2)
        return false;
    int i = a.length - 1;
    while (true) {
        int j = i;
        if (a[i] < a[j]) {
            int k = a.length;
            while (!(a[i] < a[--k])) {}
            swap(a, i, k);
            reverse(a, j, a.length);
            return true;}
        if (i == 0) {
            reverse(a, 0, a.length);
                return false;}}}}

I thought that was interesting because it's so elegant. It's not a very obvious solution though. Basically, you want to go backwards and find two consecutive numbers where the second is bigger than the first. Then, you go backwards again and take note of the first place where there's a number bigger than that first number. Then you just swap, and you reverse the numbers from there until the end. It's simpler than it sounds, and if you compile it and try it out you'll see that it works really well (assuming a is already sorted). While I'm talking about CS I should mention that I'm thinking of changing my degree plan from B.A. to B.S. with a focus on Mathematics. The reason I did the B.A. was because I thought it was necessary if I wanted to get a Business Foundations Certificate, but I crunched some numbers yesterday and figured out that I could still do the B.S., so maybe I'll put up my degree plan next week when I iron it out and I'll talk more about my choice then.

I have some good stuff for today. If you've ever gotten stuck in a jigsaw puzzle you'll appreciate Glyphsaw Puzzle. It's written in 200 lines of Python and can tell you where a puzzle piece belongs if you just show it to a webcam. I think that's pretty amazing! It's not better than face-recognition though, which is a feature that may soon come to Japanese cellular phones. The software would add an extra layer of security to the phone, and I think it would be useful to protect access to personal info but hopefully they don't require proper recognition to place calls. Just another example of evolution in Computer Sciences. Meanwhile, a group of CS professors here in the U.S. are fighting for Grokster with an amicus brief (this is a document presented to a judge in a case by an arbritrary third party). From what I can discern from their arguments, they're trying to show the importance of the technology that it's based on and the fact that P2P isn't a new concept at all. I think it's just funny that they're fighting on the side of Grokster. I'm gonna keep the nerdiness going by mentioning an article on quality assurance that I found rather useful. QA is often left in the dust so that's a great wake-up call article for those of you in an IT field. If any of you live near a Baskin Robbins I hope you all got your free ice cream today courtesy of Yahoo! to celebrate their 10th anniversary. I wonder how much that cost them? Lastly, I just had to menion that Adobe opened an open source library that I have bookmarked for future reference because it holds the key to their whole human interface (Adam and Eve).

I have very few tidbits of movie news today. I mentioned the new Splinter Cell game yesterday and today I have learned that Peter Berg will be working on a movie adaptation of the acclaimed espionage game. Given that he was responsible for Friday Night Lights I wouldn't be surprised if this movie turned out well, but he hasn't given away much in the way of details yet. The trailer for Lords of Dogtown, a movie that aims to document the beginning of extreme skateboarding, was released today but it seems like the movie tries too hard to be melodramatic and surfer cool at the same time. If you want to see a better trailer you may aim your browsers to a fanmade Episode III trailer. Will Ferrell seems to be all over the place and now he's in talks to make an Elf 2, which sounds like it would be horrible (like Mulan 2). I do have high hopes for Melinda and Melinda being some great popcorn entertainment though.

Nice apron

I have a few comic book movie items to boot. The rumor I reported yesterday about a new Superman has been confirmed false and it will remain Brandon Routh. Jamie Foxx may be Luke Cage if you keep up with obscure comic books. The rest of you may care more about Stan Lee teaming up with Robert Evans to make a new superher: Foreverman. Do we really need another fabricated superhero?

I just want to hit on a few quick points before I conclude. I was saddened to learn that FIFA Street really bombed and I'm disappointed in EA for letting that happen. Because I'm a fan of online multiplayer I have to mention that I think that ambitions are growing for the new Timesplitters game and I always knew that it was a series with tons of potential. The Supreme Court has ruled to ban the execution of juveniles, which is great because that really is cruel and unusual punishment. And finally, I thought I'd point out another factor that heavily affects the market: energy prices. A rise in oil prices really tanked stocks today and was even powerful enough to offset the word of Greenspan.

Before I go study like Hell for my Philosophy test (God help me), I'd like to present the Midweek Music Meme:

What song with mostly or completely nonsensical lyrics do you like anyway (or because the lyrics don’t make sense!)?
That's easy: By The Way by the Red Hot Chili Peppers. Do the lyrics mean anything? Who cares. It's a fun song to listen to and a great music video.

No comments: