World's most popular travel blog for travel bloggers.

How many segmentations are possible for a string length N?

, , No Comments
Problem Detail: 

I have a string with length N. I would like to know how many segmentations are possible to it. Consider the example abcdc the number of N = 5 All possible segmentations are

['abcdc'] ['abcd', 'c'] ['abc', 'dc'] ['abc', 'd', 'c'] ['ab', 'cdc'] ['ab', 'cd', 'c'] ['ab', 'c', 'dc'] ['ab', 'c', 'd', 'c'] ['a', 'bcdc'] ['a', 'bcd', 'c'] ['a', 'bc', 'dc'] ['a', 'bc', 'd', 'c'] ['a', 'b', 'cdc'] ['a', 'b', 'cd', 'c'] ['a', 'b', 'c', 'dc'] ['a', 'b', 'c', 'd', 'c'] 

Then what will happen when my N tends to infinity . Any closed form equations?

Asked By : Karun
Answered By : Kaveh

There are n-1 points where you can break the string. Each is independent of the others. Therefore there are $2^{n-1}$ possibilities to break the string.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54700

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback