StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You can generate the set of strings based on following steps: </p> <p>Some chucks of numbers and their legal position are enumerated:</p> <hr> <p>Start: 110</p> <p>Must have one, anywhere: 111</p> <p>Anywhere: 0, 010, 0110</p> <p>End: 011</p> <hr> <p>Depend on the length of target string (the length should be bigger than 3)</p> <p>Condition 1: Length = 3 : {111}</p> <hr> <p>Condition 2: 6 > Length > 3 : (Length-3) = 1x + 3y + 4z</p> <hr> <p>For example, if length is 5: answer is (2,1,0) and (1,0,1)</p> <p>(2,1,0) -> two '0' and one '010' -> ^0^010^ or ^010^0^ (111 can be placed in any one place marked as ^)</p> <p>(1,0,1) -> one '0' and one '0110' ...</p> <p>Condition 3: If 9 > Length > 6, you should consider the solution of two formulas:</p> <hr> <p>Comments: </p> <p>length – 3 : the length exclude 111</p> <p>x: the times 0 occurred</p> <p>y: the times 010 occurred</p> <p>z: the times 0110 occurred</p> <hr> <p>Finding all solutions {(x,y,z) | 1x + 3y + 4z = (Length - 3)} ----(1)</p> <p>For each solution, you can generate one or more qualified string. For example, if you want to generate strings of length 10. One solution of (x,y,z) is (0,2,1), that means '010' should occurred twice and '0110' should occurred once. Based on this solution, the following strings can be generated:</p> <hr> <p>0: x0 times</p> <p>010: x 2 times</p> <p>0110: x1 times</p> <p>111: x1 times (must have)</p> <hr> <p>Finding the permutations of elements above. 010-0110-010-111 or 111-010-010-0110 …</p> <p>(Length - 6) = 1x + 3y + 4z ---(2) Similar as above case, find all permutations to form an intermediate string. Finally, for each intermediate string Istr, Istr + 011 or 110 + Istr are both qualified. </p> <p>For example, (10-6) = 1*0 + 3*0 + 4*1 or = 1*1 + 3*1 + 4*0</p> <p>The intermediate string can be composed by one '0110' for answer(0,0,1): Then ^0110^011 and 110^0110^ are qualified strings (111 can be placed in any one place marked as ^)</p> <p>Or the intermediate string can also be composed by one '0' and one '010' for answer (1,1,0)</p> <p>The intermediate string can be 0 010 or 010 0 Then ^0010^011 and 110^0100^ are qualified strings (111 can be placed in any one place marked as ^)</p> <p>Condition 4: If Length > 9, an addition formula should be consider:</p> <hr> <p>(Length – 9) = 1x + 3y + 4z </p> <p>Similar as above case, find all permutations to form an intermediate string. Finally, for each intermediate string Istr, 110 + Istr + 011 is qualified. </p> <hr> <p>Explaination:</p> <p>The logic I use is based on Combinatorial Mathematics. A target string is viewed as a combination of one or more substrings. To fulfill the constraint ('111' appears exactly one time in target string), we should set criteria on substrings. '111' is definitely one substring, and it can only be used one time. Other substrings should prevent to violate the '111'-one-time constraint and also general enough to generate all possible target string.</p> <p>Except the only-one-111, other substrings should not have more than two adjacent '1'. (Because if other substring have more than two adjacent 1, such as '111', '1111', '11111,' the substring will contain unnecessary '111'). Except the only-one-111, other substrings should not have more than two consecutive '1'. Because if other substring have more than two consecutive 1, such as '111', '1111', '11111,' the substring will contain unnecessary '111' . However, substrings '1' and '11' cannot ensure the only-one-111 constraint. For example, '1'+'11,' '11'+'11' or '1'+'1'+'1' all contain unnecessary '111'. To prevent unnecessary '111,' we should add '0' to stop more adjacent '1'. That results in three qualified substring '0', '010' and '0110'. Any combined string made from three qualified substring will contain zero times of '111'. </p> <p>Above three qualified substring can be placeed anywhere in the target string, since they 100% ensure no additional '111' in target string. </p> <p>If the substring's position is in the start or end, they can use only one '0' to prevent '111'. </p> <p>In start:</p> <p>10xxxxxxxxxxxxxxxxxxxxxxxxxxxx</p> <p>110xxxxxxxxxxxxxxxxxxxxxxxxxxx</p> <p>In end:</p> <p>xxxxxxxxxxxxxxxxxxxxxxxxxxx011</p> <p>xxxxxxxxxxxxxxxxxxxxxxxxxxxx01</p> <p>These two cases can also ensure no additional '111'. </p> <p>Based on logics mentioned above. We can generate any length of target string with exactly one '111'. </p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload