Author |
Topic: make unique string (Read 3256 times) |
|
birbal
Full Member
Gender: 
Posts: 250
|
 |
make unique string
« on: Dec 12th, 2012, 9:43am » |
 Quote  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:
Posts: 13730
|
|
Re: make unique string
« Reply #1 on: Dec 12th, 2012, 11:27am » |
Quote 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
Gender:
Posts: 56
|
|
Re: make unique string
« Reply #2 on: Dec 13th, 2012, 3:34am » |
Quote 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:
Posts: 250
|
|
Re: make unique string
« Reply #3 on: Dec 13th, 2012, 9:49am » |
Quote 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:
Posts: 13730
|
|
Re: make unique string
« Reply #4 on: Dec 13th, 2012, 11:38am » |
Quote 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
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print