Finding out fastest way to find how many partitions can be made form a string with variable characters
So let's say I have a string, 1??0.
Now I can replace the question marks with either 1 or 0. Now what's the fastest way to find out how many contiguous blocks I make with this string.
For example, with string 1??0 I can make these strings:
1000, 1010, 1100, 1110
I have 3 strings with 2 contiguous blocks (1000, 1100, 1110)
And I have 1 string with 4 contiguous blocks (1010)
So the program would output something like:
"There are 3 permutations that have 2 blocks\nThere is 1 string with 3 contiguous blocks"
Now what is the fastest way I can count and store the number of unique blocks of contiguous numbers of size n.
Now I can replace the question marks with either 1 or 0. Now what's the fastest way to find out how many contiguous blocks I make with this string.
For example, with string 1??0 I can make these strings:
1000, 1010, 1100, 1110
I have 3 strings with 2 contiguous blocks (1000, 1100, 1110)
And I have 1 string with 4 contiguous blocks (1010)
So the program would output something like:
"There are 3 permutations that have 2 blocks\nThere is 1 string with 3 contiguous blocks"
Now what is the fastest way I can count and store the number of unique blocks of contiguous numbers of size n.
I'm assuming that by "contiguous block" you mean successive numbers of the same value.
I'm also going to assume that you have only 2 values (in your example, 0 and 1). It is harder if there are more.
The contiguous blocks are essentially defined by the dividers between them; if there are n items then there are n-1 possible positions for a divider (between first and second, second and third, third and fourth in your given example) and the number of blocks is the number of dividers plus 1.
In the case of strings containing only 0 and 1, if the end numbers are different there must be an odd number of dividers (1 or 3 in your case) and hence an even number of blocks (2 or 4 in your case).
In general, if the string has length n:
- if the start and end numbers are different (two possibilities: 0..1 or 1..0):
-> for each even number of blocks r <= n there are (n-1)C(r-1) ways of choosing the r-1 dividers from the n-1 possible positions of a divider.
- if the start and end numbers are the same (again, two possibilities: 0..0 or 1..1):
-> for each odd number of blocks r <= n there are (n-1)C(r-1) ways of choosing the r-1 dividers from the n-1 possible positions of a divider.
So, I think your problem amounts to being able to compute combinatorics of the form nCr (warning: simply calculating the factorials involved is not a clever way of doing this, as they grow very rapidly) for either even or odd values of r.
Again, I'm presupposing that each digit must be either 0 or 1 (not a bad assumption in Computer Science!)
I'm also going to assume that you have only 2 values (in your example, 0 and 1). It is harder if there are more.
The contiguous blocks are essentially defined by the dividers between them; if there are n items then there are n-1 possible positions for a divider (between first and second, second and third, third and fourth in your given example) and the number of blocks is the number of dividers plus 1.
In the case of strings containing only 0 and 1, if the end numbers are different there must be an odd number of dividers (1 or 3 in your case) and hence an even number of blocks (2 or 4 in your case).
In general, if the string has length n:
- if the start and end numbers are different (two possibilities: 0..1 or 1..0):
-> for each even number of blocks r <= n there are (n-1)C(r-1) ways of choosing the r-1 dividers from the n-1 possible positions of a divider.
- if the start and end numbers are the same (again, two possibilities: 0..0 or 1..1):
-> for each odd number of blocks r <= n there are (n-1)C(r-1) ways of choosing the r-1 dividers from the n-1 possible positions of a divider.
So, I think your problem amounts to being able to compute combinatorics of the form nCr (warning: simply calculating the factorials involved is not a clever way of doing this, as they grow very rapidly) for either even or odd values of r.
Again, I'm presupposing that each digit must be either 0 or 1 (not a bad assumption in Computer Science!)
Last edited on
the ones with 2 contiguous blocks work because 1000 becomes (1) and (000). Hence two blocks
the one with 4 blocks is (1) (0) (1) (0), which makes 4 blocks.
This is supposed to be an easy programming problem and I keep getting time outs just by counting and permutating the possible ways of the question marks
the one with 4 blocks is (1) (0) (1) (0), which makes 4 blocks.
This is supposed to be an easy programming problem and I keep getting time outs just by counting and permutating the possible ways of the question marks
Hello @Code Apperentice
In your case, n=4, so n-1 is 3 - the number of positions of possible dividers.
For two contiguous blocks, there will be 1 divider (denoted by | below)
1|000
11|00
111|0
That is 3C1 = 3 possible ways (given the end values).
For 4 contiguous blocks, there will be 3 dividers:
1|0|1|0
That is 3C3 = 1 possible way (given the end values)
It gets more interesting with larger strings.
I think you should only be evaluating nCr - this is defined (but NOT programmed) as
n!/(r! (n-r)! )
If you want r blocks from a string of length n then you will strictly be computing
(n-1)C(r-1)
because you want to choose r-1 positions for a divider from a possible n-1. The number of blocks must be even if the end values are different and the number of blocks must be odd if the end values are the same.
You shouldn't be getting timeouts with that. Sounds like you have infinitely repeating loops somewhere - print out some intermediate values.
(I'm assuming throughout that you are only interested in the number of permutations, and you don't intend to store all the permutations. If that is not the case then you had better correct me. You don't actually have to create all the permutations just to count them.)
In your case, n=4, so n-1 is 3 - the number of positions of possible dividers.
For two contiguous blocks, there will be 1 divider (denoted by | below)
1|000
11|00
111|0
That is 3C1 = 3 possible ways (given the end values).
For 4 contiguous blocks, there will be 3 dividers:
1|0|1|0
That is 3C3 = 1 possible way (given the end values)
It gets more interesting with larger strings.
I think you should only be evaluating nCr - this is defined (but NOT programmed) as
n!/(r! (n-r)! )
If you want r blocks from a string of length n then you will strictly be computing
(n-1)C(r-1)
because you want to choose r-1 positions for a divider from a possible n-1. The number of blocks must be even if the end values are different and the number of blocks must be odd if the end values are the same.
You shouldn't be getting timeouts with that. Sounds like you have infinitely repeating loops somewhere - print out some intermediate values.
(I'm assuming throughout that you are only interested in the number of permutations, and you don't intend to store all the permutations. If that is not the case then you had better correct me. You don't actually have to create all the permutations just to count them.)
Last edited on
Yes I don't have to store them. But will this work if the question marks are arbitrarily placed? For example 1???000001111000??1
With your example 000001111000??1 you will simply have another two blocks, 00000 and 1111, for each of the permutations fitting 0??1.
Are you sure that your problem is not just
1????????????????1
Can you state EXACTLY what your problem is, before it gets changed again.
1????????????????1
Can you state EXACTLY what your problem is, before it gets changed again.
Topic archived. No new replies allowed.