mind=body=soul

Of all the things I've lost, I miss my mind the most. - (Mark Twain and me)

Sunday, November 26, 2006

 

Interesting problem...

Note-1: I dont know the solution for this, though I have some of my own nothing-great solutions for this.
Note-2:I made complete changes to an original problem which I heard to make it simple and elegant.

There are some N fixed-length-bit-sequences(call it word) . You have to split these words into different groups(say max is G groups. N>>G) such that the maximum "difference" between two words is minimized. "difference" is the number of bit positions which differs in the 2 words. How would do u this in an ideal world where speed or memory is not an issue(this is more like a puzzle than an algo problem)? In a realistic world where time/space is an issue(this is algo-type. graphs can come handy or atleast i think)?
Another interesting question(which came to me as I write this) is what if words are being added/deleted. How to group so as to minimize the re-organization of buckets but allowing for an approximate solution initially(say u can have G+g groups). I think this is hard.
Since I cooked-up this one, if something is not clear make ur own "reasonable assumptions".
I would love to hear ur solutions.

Labels:


Comments:
I sorta didn't get it.. can u link to the original question?
 
Oh, someone put this in an internal mailing list. So, no url :(
Will give u an example, if it can make clearer:
Lets say there are 5(N) words and max is 2 groups(G)
1111
1110
0000
0001
0011

The grouping will be
G1
1111
1110
G2
0000
0001
0011

The difference in G1 is 1 and dffference
in G2 is 2(diff(0000,0011)). Basically given some N words, u have to form a grouping with atmost G groups so that max difference between any two words is miinised. In the above example if 1110 and 0001 was put in the same group, the diff is 4 which is the worst case.
 
My relatives every time say that I am killing my time
here at web, but I know I am getting experience everyday by reading such nice articles
or reviews.

my site :: how to find the cheapest auto insurance
 
Post a Comment

Subscribe to Post Comments [Atom]



Links to this post:

Create a Link



<< Home

Archives

November 2006   December 2006   February 2007   March 2007   April 2007   May 2007   July 2007   August 2007   September 2007   October 2007   November 2007   January 2008   February 2008   March 2008   April 2008   July 2008   September 2008   October 2008   November 2008   December 2008   January 2009   February 2009   March 2009   April 2009   May 2009   January 2011  

Buddie blogs

Musings (Balaji)  
Question (Vijay)  
Theres always room(My prev. blog)  
Boss rendu T oru Wills(Madhu)  
Anand  
My alpine path(Nisha)  
Yves Lu  
Rumination of a restless mind(S_Arun)  
Ridhus Digest  

Unknown encounters

Steve Pavlina  


This page is powered by Blogger. Isn't yours?

Subscribe to Posts [Atom]

Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial 3.0 United States License.