Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Here is a quick idea.</p> <p>One well-known trick to lazily generate the powerset of a set of size N is to iterate each number from 0 to (2^N)-1, considering its binary representation. Each iteration produces a partition : you put the i-th element of the set in the current partition if the i-th digit of the current number is 1.</p> <p>You can do the same in your case: a partition of P is given not by a binary number below 2^N, but by a number below N^N, in base N. Now the trick to get the partitions with the fewest component first is:</p> <ul> <li>first iterate upto 2^N (this gives you the partitions of 2 components)</li> <li>then iterate upto 3^N, rejecting the numbers that don't have both a 0, a 1 and a 2 in their representation (this rules out the previously produced partitions)</li> <li>then iterate upto 4^N, taking only numbers with all 4 distinct digits</li> <li>etc... upto N^N</li> </ul> <p>Obviously this makes you manipulate quite large numbers. You do not need to encode them as integers/bignum. For example in the powerset case, a list of booleans is just as good. The same idea could be reused in the partition case. Moreover, the K-ary representation of two consecutive numbers are close, so you can probably cache some information to get a more efficient algorithm:</p> <ul> <li>you can cache a part of your current partitioning (say, you could represent the current partition as an array of lists, and just destructively update the few digits that change)</li> <li>you can cache the information of which digits are currently present in the number (to know quickly if you have already seen such a number in a previous iteration)</li> </ul> <p>Quite naive and no code to propose yet, sorry, but I hope my idea is clear and you can make something useful out of it. People That Know certainly have more direct ideas.</p> <p>In particular there may be a clever way to know if a number below K^N uses all K digits its K-ary representation. For example, you know that no number below K^(K-1) does (they have less than K distinct digits).</p>
    singulars
    1. This table or related slice is empty.
    1. PO"Ordered power set" / "Graph coloring" sets
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USgasche
    1. USgasche
    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. COI was starting to think along these lines myself; it seems excellent as long as you don't mind seeing some repeated partitions. If you just think about two partitions, you see that {a, b} {c} is the same as {c} {a, b}. The first would be generated by the binary value 100 and the second by 011. I can see the pattern for two partitions, but for larger numbers of partitions it seems quite difficult to detect these repetitions. (But maybe there's an easy way, I'm no combinatorialist.)
      singulars
      1. PO
      1. USJeffrey Scofield
    2. COThanks, I'll look into the ideas. But as Jeffrey mentionend, I want to avoid repeating sets.
      singulars
      1. PO
      1. USLasse Espeholt
    3. CO@Jeffrey is right, I didn't account for this kind of repetition. It is possible to avoid it by the classic technique of imposing an ordering on the result (such that it makes only one of the repetitions valid). For example, you can ask that, when you read the digit from right to left, each distinct digit is introduced in increasing order. Eg. 3313221 is valid (from right to left, introduced in order 1,2,3) but its repetition 2212332 is not (2,3,1). I believe this gives injectivity, but I could as well be wrong as I was the last time. If kvb's solution work, it's certainly simpler.
      singulars
      1. PO
      1. USgasche
 

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