Databases
StackOverflow2013
Postsdbo
POHow can I represent a self-enumerating pangram as a boolean function?
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow can I represent a self-enumerating pangram as a boolean function?
    primarykey
    data
    text
    <p>The wiki article for self-enumerating pangrams states that they are computed using Binary Decision Diagrams. I've been reading about BDDs and from my understanding you need to represent some problem as a boolean function before you can construct a BDD for it.</p> <p>How would I go about doing this?</p> <p>I've been thinking about the problem for a few days now, and I'm pretty sure you could representing the input to the boolean function using a straightforward encoding:</p> <pre><code>10000 01010 01011 10101 ... 16A's 10B's 11C's 21D's ... </code></pre> <p>So for a pangram starting "sixteen A's, ten B's, eleven C's, twenty-one D's", you could represent it as 10000010100101110101...</p> <p>This would mean that there are 26 * 5 = 130 variables in the boolean function, assuming you restrict the maximum frequency of a character to 32 occurrences.</p> <p>The output should be whether the representation is a self-enumerating pangram or not, i.e. if the sentence describes its own set of frequencies.</p> <p>To do this, a hash table (or several) must surely be required along the way.</p> <p>So for the letter E, the hash table might begin:</p> <pre><code>one -&gt; 1 two -&gt; 0 three -&gt; 2 four -&gt; 0 five -&gt; 1 ... </code></pre> <p>Which in binary, might look like:</p> <pre><code>1 -&gt; 1 10 -&gt; 0 11 -&gt; 10 100 -&gt; 0 101 -&gt; 1 </code></pre> <p>If the summation of all lookups from the E hash table is equal to five input bits corresponding to E, then that section of the self-enumerating pangram is correct. If all sections are correct then the boolean function should yield 1, otherwise 0.</p> <p>I'm fairly sure I could figure out how to carry out addition using a boolean function and how to check if two numbers are equal. I have no idea where to start with representing the hash table as a boolean function, however. Also, connecting all of the pieces together is likely to bewilder me.</p> <p>Any thoughts? Ideas? Collaboration? I'd like to see where this goes.</p> <p>Thanks in advance.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USChris
    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. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow can I represent a self-enumerating pangram as a boolean function?
      1. USChris
      1. VTBountyStart
    2. VO
      singulars
      1. POHow can I represent a self-enumerating pangram as a boolean function?
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POHow can I represent a self-enumerating pangram as a boolean function?
      1. USstormCloud
      1. VTFavorite
    1. COhas some leads: http://www.fatrazie.com/EWpangram.html
      singulars
      1. POHow can I represent a self-enumerating pangram as a boolean function?
      1. USTom Sirgedas
    2. COThis is a really interesting problem, that I've enjoyed thinking about for the past few hours. Personally I'd try and solve the problem with search, rather than try and mathematically solve it with boolean functions. I've had a look at some of the literature available on this [link](http://scholar.google.com/scholar?q=pangram+search), and these papers put the way forward to solve it far more eloquently than I could. Hope that helps, and thanks very much for a few hours of very interesting thought. Dave
      singulars
      1. POHow can I represent a self-enumerating pangram as a boolean function?
      1. USstormCloud
    3. COVery interesting indeed. Maybe you could find this document about Binary Decision Diagrams useful: http://www.voronkov.com/lics_doc.cgi?what=chapter&n=10
      singulars
      1. POHow can I represent a self-enumerating pangram as a boolean function?
      1. UScprogcr
 

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