wu :: forums
« wu :: forums - make unique string »

Welcome, Guest. Please Login or Register.
Dec 10th, 2024, 6:31pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: towr, william wu, ThudnBlunder, Grimbal, Eigenray, Icarus, SMQ)
   make unique string
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: make unique string  (Read 3258 times)
birbal
Full Member
***





   


Gender: male
Posts: 250
make unique string  
« on: Dec 12th, 2012, 9:43am »
Quote Quote Modify Modify

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.
IP Logged

The only thing we have to fear is fear itself!
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: make unique string  
« Reply #1 on: Dec 12th, 2012, 11:27am »
Quote Quote Modify Modify

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.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
cartoonle
Junior Member
**





   
WWW

Gender: male
Posts: 56
Re: make unique string  
« Reply #2 on: Dec 13th, 2012, 3:34am »
Quote Quote Modify Modify

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).
IP Logged

friv - something i've built
birbal
Full Member
***





   


Gender: male
Posts: 250
Re: make unique string  
« Reply #3 on: Dec 13th, 2012, 9:49am »
Quote Quote Modify Modify

on Dec 12th, 2012, 11:27am, towr wrote:
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.

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.
IP Logged

The only thing we have to fear is fear itself!
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: make unique string  
« Reply #4 on: Dec 13th, 2012, 11:38am »
Quote Quote Modify Modify

When it comes to that, the problem doesn't state what we should do when we have Xk 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.)
« Last Edit: Dec 13th, 2012, 11:39am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board