wood burning stoves*
The moose likes Meaningless Drivel and the fly likes Programming Diversion 1 Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Other » Meaningless Drivel
Bookmark "Programming Diversion 1" Watch "Programming Diversion 1" New topic
Author

Programming Diversion 1

Jason Menard
Sheriff

Joined: Nov 09, 2000
Posts: 6450
Once upon a time we discussed the possibility of a new forum to post little programming challenges of varying difficulty and the like, just to get people to think a little bit about algorithms and such, and to stretch their brain. It doesn't look like that forum's going to happen (too bad, I hear Mark Herschberg has a ton of these), but I thought I would begin posting a few every now and then just to see how it goes.
Anyway, here's a little programming challenge for people to play around with.

The Challenge
-------------
Given any string (you might have to set a character limit though or you'll probably run out of memory), write a small program that displays all the anagrams for that string.
That is if my input string is "abc" my output should be:
abc
acb
bac
bca
cab
cba
There are no "correct" answers per se, assuming the output is correct, so I won't be posting what the "right" way to do it is (even if I did know ). It's just an exercise to see how different people come up with a way to solve a problem and maybe we'll have some resulting discussion about maybe what some "best" ways are to solve the problem. When you post your code, be sure to use the UBB CODE tags.
Have fun.
[ September 12, 2002: Message edited by: Jason Menard ]
M Suguna
Ranch Hand

Joined: Jun 07, 2002
Posts: 37
Hmmm...made me to use my brain after a long time!
Here is my solution to your problem. Have a look.

Howz it?


Who says nothing is impossible? I've been doing nothing for years
David Weitzman
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
I decided to expand on the idea behind the previous solution by doing it all without allocating any new memory. This solution and the previous, though, will print identical strings more than once if a charater repeats (i.e. if you passed 'aab'). I'll think about efficiently preventing duplicates. Maybe sorting the letters first would help. Anyway, the code:
Jason Menard
Sheriff

Joined: Nov 09, 2000
Posts: 6450
Those both look like good solutions.
I mentioned memory in the begining but didn't really elaborate why it could be a problem. Although the specification was only to display the anagrams, what if they needed to be stored for search and retrieval? Since a word of length N will have N! anagrams (not counting duplicates because of duplicate letters), memory may become an issue if for example you wanted to find the anagrams to a word like "supercalafragalisticexpealadocious".
Jason Menard
Sheriff

Joined: Nov 09, 2000
Posts: 6450
Not that it's a contest of speed or anything but just in case you are wondering, I ran both of your methods against threewords "abcde", "abcdef", and "abcdefg". Here are the results in milliseconds:
<pre>
abcde abcdef abcdefg
===== ====== =======
M Suguna 471 3025 23914
David W 451 2764 24906
</pre>
Someone else can run this and see what kind of numbers they get if they'd like.
[ September 13, 2002: Message edited by: Jason Menard ]
Alex Ayzin
Ranch Hand

Joined: Apr 10, 2001
Posts: 107
Your idea is great, Jason. Why don't you continue to post some puzzles, maybe others will join you as well later. That's a great way to really exercise your brain(it seems that I haven't been doing it since college all-nighters ).
Best regards,
--Alex Ayzin
David Weitzman
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
I'm not at my computer to run any tests (and won't be for another 8 hours or so), but I think the best way to speed both of them up is proabably just to tweek the IO.
Buffer it.
In the case of my implementation, wrap a CharWriter around System.out. Using byte[] arrays directly would be even faster (or at least wrapping a CharWriter around the terminal FileDescriptor without the extra layer of a PrintStream).
I still haven't spent any time considering whether presorting would allow duplicates to be prevented. Bad me. It seems like it should (although that obviously increases the running time).
Other speed stuff:
Whether or not my swap method is inlined depends on the particular compiler and settings, but it should be. Would making 'tmp' a member variable add more overhead than it saves in allocation costs? What about the fun XOR swapping method?
Stick on a 'final' in both for good luck.
Excercize for people with reallllly fast computers: See how many letters it takes until the speed difference between the implementations is consistantly and noticably different.
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671
I saw Jason's first post this morning, then spent most of the day in airports, where I cobbled the following together before the battery went out:

Looks like David and I are on the same wavelength. Using Arrays.sort() does allow us to remove duplicates. It takes some time, true, but it's just a one-time O(n log n), compared to O(n!) for the permutations themselves, so I don't imagine this will be much concern.
[ September 14, 2002: Message edited by: Jim Yingst ]

"I'm not back." - Bill Harding, Twister
David Weitzman
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
I was just about to post my fixed version when I saw yours. I'll post it anyway for kicks:
David Weitzman
Ranch Hand

Joined: Jul 27, 2001
Posts: 1365
Since this problem is dealing with numbers in a small known range, you could implement counting sort yourself for O(n) sorting time.
Sridhar Garimella
Ranch Hand

Joined: Feb 18, 2000
Posts: 73
Another Challenge
------------------
Given any integer write an efficient program that checks whether it is possible to represent this no as 2 to the power some thing?
For example
1 - possible to represent as 2 to the power 0
2 - possible to represent as 2 to the power 1
12 - not possible
--Sridhar
Jason Menard
Sheriff

Joined: Nov 09, 2000
Posts: 6450
Originally posted by Sridhar Garimella:
Another Challenge
------------------
Given any integer write an efficient program that checks whether it is possible to represent this no as 2 to the power some thing?
For example
1 - possible to represent as 2 to the power 0
2 - possible to represent as 2 to the power 1
12 - not possible
--Sridhar

Kindly repost this to a different thread.
Jason Menard
Sheriff

Joined: Nov 09, 2000
Posts: 6450
I never posted my solution, so here it is. It doesn't look like I have anything really new here. While I know it is more efficient to manipulate arrays directly, I stuck with string manipulation. While I suspect that given a very large string performance might suffer, Java string manipulation is sufficiently performant that we won't really take a performance hit when dealing with relatively small strings like you do when finding anagrams, and the times bear this out. It looks like I handled duplicates basically the same way as everyone else, sort the string and don't findAnagrams() if the current character is the same as the previous character.

 
wood burning stoves
 
subject: Programming Diversion 1
 
Similar Threads
how to select a block using awt inside an swt component
jQuery - ajax call .load()
Welcome to Programming Diversions!
New Forum: Programming Diversions
deserialization and casting