Probability to realize string using subsequences

[MonD1]

Given a input string and 'n' random subsequences of that string , what is the probability of realizing original string using these subsequences correctly?

Example :

Given string = "MISSISSIPPI"
Subsequences:
1) "MISS"
2) "III"
3) "MIP"
4) "SIS"
5) "IS"
6 ) "SP"
7) "MP"How many subsequences will be required for optimal probability?
Is there any specific structure for subsequences for optimal probability?

 

[MarkFL]

Re: probability to realize string using subsequences

Can you post what you have tried or what your thoughts are on how to begin? This will give our helpers a better idea how best to help you. :D

 

[MonD1]

Re: probability to realize string using subsequences

Can you post what you have tried or what your thoughts are on how to begin? This will give our helpers a better idea how best to help you. :D

Input
string of length 'm'
'k' subsequences of the string each of length 'n' (n <m)

What is the probability that by using these subsequences we can come up with the original string?

 

[springfan25]

i still don't understand the question. post #1 doesn't appear to have substrings of the same length as you required in post #3.

Its also not clear what you mean by probablility of "getting the original string" from your substrings.

 

[blue_raver22]

The probability of realizing the original string using the given subsequences depends on the length and composition of the input string, as well as the number and composition of the subsequences. It is difficult to determine an exact probability without knowing these factors.

However, in general, the more subsequences that are available and the longer they are, the higher the probability of realizing the original string correctly. This is because more subsequences provide more opportunities to match the characters in the original string.

The optimal number of subsequences for the highest probability would depend on the specific input string and the composition of the subsequences. In some cases, a larger number of shorter subsequences may provide a higher probability, while in other cases, a smaller number of longer subsequences may be more effective.

There is no specific structure for subsequences that guarantees optimal probability. However, it is important for the subsequences to cover a wide range of characters and positions in the original string in order to increase the chances of a correct match. Additionally, the subsequences should not overlap too much, as this can decrease the overall probability.