Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>To count the number of non-periodic strings on length <em>n</em>:</p> <ul> <li>The total number of strings: 2ⁿ</li> <li>Subtract the number of periodic strings of length <em>n</em></li> </ul> <p>To count the number of periodic strings on length <em>n</em>:</p> <ul> <li><p>Find all divisors of <em>n</em>, except n itself. For example: if <em>n</em>=6 - the divisors are 1,2,3.</p> <p>(The method for this had been discussed <a href="https://stackoverflow.com/questions/5793009/efficiently-finding-all-divisors-of-a-number">here</a>)</p></li> <li><p>Each divisor m can be used to represent 2^m periodic strings. For example</p></li> <li>m=1: {0,1} - 2^1 periodic strings</li> <li>m=2: {00,01,10,11} - 2^2 periodic strings</li> <li><p>m=3: {000,...111} - 2^3 periodic strings</p> <p>So for n=6, there are 2+4+8 periodic strings</p> <p>As Jeffery Sax and ANeves pointed out, some of these periodic strings are identical {for example 0* = 00* = 000*), so we have to eliminate these.</p> <p>A naive method would be to add all these strings to an associative container that stores unique elements (such as <a href="http://www.cplusplus.com/reference/stl/set/" rel="nofollow noreferrer">set</a> in C++), and count the number of elements in the that container.</p> <p>A better optimization would be: for m=m1, find all divisors of m1, and avoid adding strings that are periodic of strings already in these sets.</p></li> </ul> <p>The next step would be to calculate the <a href="http://en.wikipedia.org/wiki/Hamming_distance" rel="nofollow noreferrer">Hamming distance</a> between any of these periodic strings and the received string. If it is less than K- count it.</p> <hr> <p><strong>Edit: A better solution for large N and small K</strong></p> <p><strong>Algorithm for checking if a string is periodic:</strong></p> <p>This can be accomplished by comparing the string with a shifted-version of itself. If a string is identical to it's p-bit circular-shift - then it has a cycle of p.</p> <p>So circularly-shifting the string one bit at a time - we can detect if it is periodic in up to floor(N/2) string comparisons.</p> <p><strong>Counting possible transmitted strings</strong></p> <p>If there would be no non-periodic transmission requirement, and we received an N bits message - the number of possible messages that could have been transmitted is <code>C(N, 0) + C(N, 1) + C(N, 2) + ... + C(N, K)</code></p> <p>For N=1000 and K=3: C(1000,0)+C(1000,1)+C(1000,2)+C(1000,3)= 166,667,501</p> <p>(This is the number of combinations of switching 0/1/2/3 bits in the original string).</p> <p>From this number, we need to decrease the number of periodic strings - which couldn't have been transmitted.</p> <p>For example: if the received string was 000000 and K=2, we can be sure that the transmitted string was not in {000000,001001,010010,100100}. These are all periodic, with hamming distance of up to K from the received string.</p> <p>C(6,0)+C(6,1)+C(6,2)=1+6+15=22 Out of these, 4 combinations are periodic.</p> <p><strong>Algorithm:</strong></p> <p>We'll start with the received string, and generate all combinations stated above. For each combination we will check if it is periodic. If so - we'll decrease our count by 1.</p>
    singulars
    1. This table or related slice is empty.
    1. POBinary String permutations
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USCommunity
    1. USLior Kogan
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COYou are counting some periodic strings more than once. In your example, you're counting all 0's and all 1's three times.
      singulars
      1. PO
      1. USJeffrey Sax
    2. CO@Jeffrey Sax: Correct. Thank you. I'll fix this.
      singulars
      1. PO
      1. USLior Kogan
    3. COI believe `m=2` contains all in `m=1`. So for `n=6`, there should be 8 periodic strings.
      singulars
      1. PO
      1. USANeves
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

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