1
$\begingroup$

I have a string and I need to generate some new strings that are not in the set I already have. What would be an efficient way to do it?

Average length of a string is 20. Alphabet contains about 100 different values.

Surely I can generate random and compare until I have a different one, but I think it would be an interesting exercise to devise such an algorithm.

Improve this question
$\endgroup$
4
  • $\begingroup$ Do you need some kind of random generation, or would a deterministic algorithm suffice? In the first case, do you need uniformity (or near-uniformity) in the generation? $\endgroup$ Commented Jan 19 at 15:20
  • $\begingroup$ With $100^{20}$ possibilities you don't need to check, even. $\endgroup$ Commented Jan 19 at 19:16
  • $\begingroup$ But what? Why have you rejected the approach you already know of? What are your requirements, and which requirement does that approach fail? $\endgroup$ Commented Jan 20 at 0:22
  • $\begingroup$ @AinsleyH. nice observation. Still, would be nice to devise a deterministic algorithm. $\endgroup$ Commented Jan 20 at 13:01

1 Answer 1

Reset to default
2
$\begingroup$

Pick the letter $a$ in the alphabet that appears the least amount of time among the first letters of the strings in the set.

If $a$ appears $0$ time, then any string beginning with $a$ is suitable.

Otherwise, keep track of the strings beginning with $a$, and do it again with the second letter, and so on.

Using that idea, the number of strings to consider is divided by at least the size of the alphabet with each letter, so you are likely to find a candidate quickly.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.