• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Programming Diversion 1

 
Sheriff
Posts: 6450
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ]
 
Ranch Hand
Posts: 37
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hmmm...made me to use my brain after a long time!
Here is my solution to your problem. Have a look.

Howz it?
 
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 6450
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 6450
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ]
 
Ranch Hand
Posts: 107
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 1365
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Wanderer
Posts: 18671
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ]
 
David Weitzman
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I was just about to post my fixed version when I saw yours. I'll post it anyway for kicks:
 
David Weitzman
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Since this problem is dealing with numbers in a small known range, you could implement counting sort yourself for O(n) sorting time.
 
Ranch Hand
Posts: 73
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 6450
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 6450
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.

reply
    Bookmark Topic Watch Topic
  • New Topic