Applying subproblem technique to permutations with grouping

Question

I am trying to apply overlapping subproblems and dynamic programming to permutations.

Say, we have a set of $n$ elements in a string. Each of these elements could be a 1ドル$ or a 0ドル$.

Given some string, I am trying to count the number of valid permutations- where a valid arrangement is defined as an ordering with no 1ドル$ that stands alone from other 1s.

Example input string: 0101ドル$

Example of valid arrangements: 1100,ドル 0011, 0110$

Not valid: 0101,ドル 1010, 1001$

EXPECTED OUTPUT: 3ドル$

For example:

Say our input string contains four 1s and two 0s.

I suppose my difficulty is coming with defining the sub-problem. I initially thought I could set up a string with only the 0ドル$ elements with slots/bins in between. $[ ] 0 [ ] 0 [] $, and then continue to use combinatorics to compute the number of additional arrangements possible with each 1 added in.

The first 1: 0 possibilities, because it will never have a 1 to accompany it.

Adding the 2nd 1: 3 possibilities, because the pair can go in either of the 3 slots.

Adding the 3rd 1: 0 new possibilities, because it must go with the other 2 ones, wherever they are.

Adding the 4th 1: We have enough to make 2 groups of 1ドル$s now... here is where I start getting unsure. I'd think it would be an additional 3 possibilities. $\binom{3}{1} + \binom{3}{2} = 6$ total

Would anyone have an idea if I'm on the wrong track, or if not, how to proceed? This approach doesn't seem like it works for larger values. Thanks!

• RandomPerfectHashFunction: Your problem basically asks for number of possible strings which contain groups of consecutive 1s, where each group has more than one 1 digit. This solution can be directly obtained using the recurrence relation for Associated Stirling numbers of the Second Kind.

Answer 1

The subproblems can be broken down as follows.

f0 :- Number of available 0s.
f1 :- Number of available 1s.
ld :- The last digit of the string generated till now.
dp[f1][f0+f1][0] = dp[f1][f0+f1-1][0] + dp[f1-1][f0+f1-1][1]
dp[f1][f0+f1][1] = dp[f1-2][f0+f1-2][0] + dp[f1-1][f0+f1-1][1]

which basically boils down to,

Say at any step the string is S0

then S011 and S00 are valid as well.

Similarly,

if the string is S1 then S11 and S10 are valid as well.

The following code solves the given problem recursively.

def rec(f0,f1,stn): # Frequency of 0,Frequency of 1, List to store generated output
 if f0==0 and f1==0:
 print(''.join(stn))
 return -1;
 if len(stn)==0 or stn[-1]=='0':
 if f0>0:
 rec(f0-1,f1,[x for x in stn]+['0'])
 if f1>1:
 rec(f0,f1-2,[x for x in stn]+['1','1'])
 else:
 if f1>0:
 rec(f0,f1-1,[x for x in stn]+['1'])
 if f0>0:
 rec(f0-1,f1,[x for x in stn]+['0'])
rec(4,4,[])

You can easily solve the overlapping subproblems issue by using a dp-table along with the propagation rules listed above.

Output of the code for a string with 4 1s and 4 0s:-

00001111
00011110
00011011
00111100
00110011
00110110
01111000
01100011
01100110
01101100
11110000
11000011
11000110
11001100
11011000