Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>This is fun! How about this:</p> <pre><code>def nonconsecutive_combinations(r, n): # first combination, startng at 1, step-size 2 combination = range(1, r*2, 2) # as long as all items are less than or equal to n while combination[r-1] &lt;= n: yield tuple(combination) p = r-1 # pointer to the element we will increment a = 1 # number that will be added to the last element # find the rightmost element we can increment without # making the last element bigger than n while p &gt; 0 and combination[p] + a &gt; n: p -= 1 a += 2 # increment the item and # fill the tail of the list with increments of two combination[p:] = range(combination[p]+1, combination[p] + 2*(r-p), 2) </code></pre> <p>Each <code>next()</code> call should have an O(r) .. I got the idea while thinking about how this would translate to natural numbers, but it took quite some time to get the details right.</p> <pre><code>&gt; list(nonconsecutive_combinations(2, 4)) [(1, 3), (1, 4), (2, 4)] &gt; list(nonconsecutive_combinations(3, 6)) [(1, 3, 5), (1, 3, 6), (1, 4, 6), (2, 4, 6)] </code></pre> <h1>Let me try to explain how this works.</h1> <p>Conditions for a tuple <code>c</code> with <code>r</code> elements to be part of the result set:</p> <ol> <li>Any element of the tuple is at least as large as the preceding element plus 2. (<code>c[x] &gt;= c[x-1] + 2</code>)</li> <li>All elements are less than, or equal to <code>n</code>. Because of 1. it is sufficient to say that <em>the last element</em> is less than or equal to <code>n</code>. (<code>c[r-1] &lt;= n</code>)</li> </ol> <p>The smallest tuple that <em>may</em> be part of the result set is <code>(1, 3, 5, ..., 2*r-1)</code>. When I say a tuple is "smaller" than another, I am assuming the lexicographical order.</p> <p>As Blckknght is pointing out, even the smallest possible tuple may be to large to satisfy condition 2.</p> <p>The function above contains two while loops:</p> <ul> <li><p>The outer loop steps through the results and assumes they appear in lexicographical order and satisfy condition one. As soon as the tuple in question violates condition two, we know that we have exhausted the result set and are done:</p> <pre><code>combination = range(1, r*2, 2) while combination[r-1] &lt;= n: </code></pre> <p>The first line initializes the result-tuple with the first possible result according to condition one. Line two squarely translates to condition two.</p></li> <li><p>The inner loop finds the next possible tuple satisfying condition one.</p> <pre><code>yield tuple(combination) </code></pre> <p>Since the <code>while</code> condition (2) is true and we made sure the result satisfies condition one we can yield the current result-tuple.</p> <p>Next, to find the lexicographically next tuple, we would add "1" to the last element.</p> <pre><code># we don't actually do this: combination[r-1] += 1 </code></pre> <p>However, that may break condition 2 too early. So, <em>if</em> that operation would break condition 2, we increment preceding element and adjust the last element accordingly. This is a little like counting integers base 10: "If the last digit is larger than 9, increment the previous digit and make the last digit a 0." But instead of adding zeros, we fill the tuple so that condition 1 is true.</p> <pre><code># if above does not work combination[r-2] += 1 combination[r-1] = combination[r-2] + 2 </code></pre> <p>Problem is, the second line may break condition two yet again. So what we actually do is, we keep track of the last element and that is what is done with the <code>a</code>. Also we use the <code>p</code> variable to refer to the index current element we are looking at.</p> <pre><code>p = r-1 a = 1 while p &gt; 0 and combination[p] + a &gt; n: p -= 1 a += 2 </code></pre> <p>We are iterating right-to-left (p = r-1, p -= 1) through the items of the result tuple. Initially we want to add one to the last item (a = 1) but when stepping through the tuple we actually want to replace the last item with the value of a preceding item plus <code>2*x</code>, where <code>x</code> is the distance between the two items. (a += 2, combination[p] + a)</p> <p>Finally, we have found the item we want to increment, and fill the rest of the tuple with a sequence starting at the incremented item, with a step size of 2:</p> <pre><code>combination[p:] = range(combination[p]+1, combination[p] + 2*(r-p), 2) </code></pre> <p>And that's it. It seemed so easy when I first thought of it, but all the arithmetic throughout the function make a great place for off-by-one errors and describing it is harder than it should be. I should have known I'm in trouble when I added that inner loop :)</p></li> </ul> <h1>On performance ..</h1> <p>Unfortunately while loops filled with arithmetic are not the most efficient thing to write in Python. The other solutions accept that reality and use list comprehensions or filtering to push the heavy lifting down into the Python runtime. This seems to me to be <em>the right thing to do</em>.</p> <p>On the other hand, I'm quite certain that my solution would perform a lot better than most if this were C. The inner while loop is O(log r) and it mutates the result in-place and the same O(log r). It does not consume additional stack frames and does not consume any memory besides the result and two variables. But obviously this is not C, so none of this really matters.</p>
    singulars
    1. This table or related slice is empty.
    1. POGenerating non-consecutive combinations
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USsvckr
    1. USsvckr
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POGenerating non-consecutive combinations
      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. VTAcceptedByOriginator
    1. COThank you for your answer. Could you please explain your algorithm in english?
      singulars
      1. PO
      1. USKnoothe
    2. COI did my best; hope this is of some help!
      singulars
      1. PO
      1. USsvckr
    3. COThanks for the explanation. You can modify it to get combinations too :-)!
      singulars
      1. PO
      1. USKnoothe
 

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