Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Donald Knuth has written the paper <a href="http://www.cs.ncl.ac.uk/publications/trs/papers/61.pdf" rel="nofollow">A Structured Program to Generate all Topological Sorting Arrangements</a>. This paper was originally pupblished in 1974. The following quote from the paper brought me to a better understanding of the problem (in the text the relation i &lt; j stands for "i precedes j"):</p> <blockquote> <p>A natural way to solve this problem is to let x<sub>1</sub> be an element having no predecessors, then to erase all relations of the from x<sub>1</sub> &lt; j and to let x<sub>2</sub> be an element &ne; x<sub>1</sub> with no predecessors in the system as it now exists, then to erase all relations of the from x<sub>2</sub> &lt; j , etc. It is not difficult to verify that this method will always succeed unless there is an oriented cycle in the input. Moreover, in a sense it is the <b>only</b> way to proceed, since x<sub>1</sub> must be an element without predecessors, and x<sub>2</sub> must be without predecessors when all relations x<sub>1</sub> &lt; j are deleted, etc. This observation leads naturally to an algorithm that finds <b>all</b> solutions to the topological sorting problem; it is a typical example of a "backtrack" procedure, where at every stage we consider a subproblem of the from "Find all ways to complete a given partial permutation x<sub>1</sub>x<sub>2</sub>...x<sub>k</sub> to a topological sort x<sub>1</sub>x<sub>2</sub>...x<sub>n</sub> ." The general method is to branch on all possible choices of x<sub>k+1</sub>.<br/> A central problem in backtrack applications is to find a suitable way to arrange the data so that it is easy to sequence through the possible choices of x<sub>k+1</sub> ; in this case we need an efficient way to discover the set of all elements &ne; {x<sub>1</sub>,...,x<sub>k</sub>} which have no predecessors other than x<sub>1</sub>,...,x<sub>k</sub>, and to maintain this knowledge efficiently as we move from one subproblem to another.</p> </blockquote> <p>The paper includes a pseudocode for a efficient algorithm. The time complexity for each output is O(m+n), where m ist the number of input relations and n is the number of letters. I have written a C++ program, that implements the algorithm described in the paper – maintaining variable and function names –, which takes the letters and relations from your question as input. I hope that nobody complains about giving the program to this answer – because of the language-agnostic tag.</p> <pre class="lang-cpp prettyprint-override"><code>#include &lt;iostream&gt; #include &lt;deque&gt; #include &lt;vector&gt; #include &lt;iterator&gt; #include &lt;map&gt; // Define Input static const char input[] = { 'A', 'D', 'G', 'H', 'B', 'C', 'F', 'M', 'N' }; static const char crel[][2] = {{'A', 'B'}, {'B', 'F'}, {'G', 'H'}, {'D', 'F'}, {'M', 'N'}}; static const int n = sizeof(input) / sizeof(char); static const int m = sizeof(crel) / sizeof(*crel); std::map&lt;char, int&gt; count; std::map&lt;char, int&gt; top; std::map&lt;int, char&gt; suc; std::map&lt;int, int&gt; next; std::deque&lt;char&gt; D; std::vector&lt;char&gt; buffer; void alltopsorts(int k) { if (D.empty()) return; char base = D.back(); do { char q = D.back(); D.pop_back(); buffer[k] = q; if (k == (n - 1)) { for (std::vector&lt;char&gt;::const_iterator cit = buffer.begin(); cit != buffer.end(); ++cit) std::cout &lt;&lt; (*cit); std::cout &lt;&lt; std::endl; } // erase relations beginning with q: int p = top[q]; while (p &gt;= 0) { char j = suc[p]; count[j]--; if (!count[j]) D.push_back(j); p = next[p]; } alltopsorts(k + 1); // retrieve relations beginning with q: p = top[q]; while (p &gt;= 0) { char j = suc[p]; if (!count[j]) D.pop_back(); count[j]++; p = next[p]; } D.push_front(q); } while (D.back() != base); } int main() { // Prepare std::fill_n(std::back_inserter(buffer), n, 0); for (int i = 0; i &lt; n; i++) { count[input[i]] = 0; top[input[i]] = -1; } for (int i = 0; i &lt; m; i++) { suc[i] = crel[i][1]; next[i] = top[crel[i][0]]; top[crel[i][0]] = i; count[crel[i][1]]++; } for (std::map&lt;char, int&gt;::const_iterator cit = count.begin(); cit != count.end(); ++cit) if (!(*cit).second) D.push_back((*cit).first); alltopsorts(0); } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POGiven a dictionary, find all possible letter orderings
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USChristian Ammer
    1. USChristian Ammer
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POGiven a dictionary, find all possible letter orderings
      singulars
      1. PTQuestion
    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
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

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