wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> make unique string
        
(Message started by: birbal on Dec 12^th, 2012, 9:43am)

Title: make unique string
Post by birbal on Dec 12^th, 2012, 9:43am

Given a set X of alphabets,a set of n strings each of length k formed of X. Task is to find a string which does not matches with any of the given n strings.

Title: Re: make unique string
Post by towr on Dec 12^th, 2012, 11:27am

[hide]diagonalization?
i.e. make a string that differs on the first character from the first string, on the second from the second, etc. So the final doesn't match any.

Or maybe the puzzle isn't quite clear to me.[/hide]

Title: Re: make unique string
Post by cartoonle on Dec 13^th, 2012, 3:34am

Is this a riddle or a practical question?

If i would have to implement this, i would simply generate random string, than check if it already exists. If it doesn't we have the string, if it does i'll repeat the steps (generate new string).

Title: Re: make unique string
Post by birbal on Dec 13^th, 2012, 9:49am

on 12/12/12 at 11:27:18, towr wrote:

What if number of strings > size of string ?
This approach will give a definite answer only if we have enough length so that we make sure it differs from each of the given strings in at least one character.

Title: Re: make unique string
Post by towr on Dec 13^th, 2012, 11:38am

When it comes to that, the problem doesn't state what we should do when we have X^k different strings and the problem can't be solved.

So in the worst case scenario we're screwed anyway, and there isn't an efficient worst case solution. (Because whatever string we can come up with, we need to check against all the input strings).

On the average case, you can take an optimistic approach, find the distribution over X for every position, then pick the least used character in the position it's least used.
Then repeat the process with only the strings that match in that position (but ignoring this position in future processing, since we've chosen what character it will be).
(You can add backtracking to retry with second-used character, etc, if you don't find a solution; this will get you to a solution if there is one, if the greedy approach doesn't work.)