Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>here is my recursive generator(it just skips <code>n+1</code>th item if <code>n</code>th item is selected):</p> <pre><code>def non_consecutive_combinator(rnge, r, prev=[]): if r == 0: yield prev else: for i, item in enumerate(rnge): for next_comb in non_consecutive_combinator(rnge[i+2:], r-1, prev+[item]): yield next_comb print list(non_consecutive_combinator([1,2,3,4], 2)) #[[1, 3], [1, 4], [2, 4]] print list(non_consecutive_combinator([1,2,3,4,5], 2)) #[[1, 3], [1, 4], [1, 5], [2, 4], [2, 5], [3, 5]] print list(non_consecutive_combinator(range(1, 10), 3)) #[[1, 3, 5], [1, 3, 6], [1, 3, 7], [1, 3, 8], [1, 3, 9], [1, 4, 6], [1, 4, 7], [1, 4, 8], [1, 4, 9], [1, 5, 7], [1, 5, 8], [1, 5, 9], [1, 6, 8], [1, 6, 9], [1, 7, 9], [2, 4, 6], [2, 4, 7], [2, 4, 8], [2, 4, 9], [2, 5, 7], [2, 5, 8], [2, 5, 9], [2, 6, 8], [2, 6, 9], [2, 7, 9], [3, 5, 7], [3, 5, 8], [3, 5, 9], [3, 6, 8], [3, 6, 9], [3, 7, 9], [4, 6, 8], [4, 6, 9], [4, 7, 9], [5, 7, 9]] </code></pre> <p>on efficiency :</p> <p>this code can't be O(1) because of traversing stack and building a new collection upon each iteration won't be O(1). also, a recursive generator means you have to use <code>r</code> maximum stack depth to get <code>r</code>-item combination. this means with low <code>r</code>, the cost of calling stacks can be more expensive then non-recursive generation. with enough <code>n</code> and <code>r</code>, it is potentially much more efficient than itertools-based solution. </p> <p>i've tested two uploaded codes in this question:</p> <pre><code>from itertools import ifilter, combinations import timeit def filtered_combi(n, r): def good(combo): return not any(combo[i]+1 == combo[i+1] for i in range(len(combo)-1)) return ifilter(good, combinations(range(1, n+1), r)) def non_consecutive_combinator(rnge, r, prev=[]): if r == 0: yield prev else: for i, item in enumerate(rnge): for next_comb in non_consecutive_combinator(rnge[i+2:], r-1, prev+[item]): yield next_comb def wrapper(n, r): return non_consecutive_combinator(range(1, n+1), r) def consume(f, *args, **kwargs): deque(f(*args, **kwargs)) t = timeit.timeit(lambda : consume(wrapper, 30, 4), number=100) f = timeit.timeit(lambda : consume(filtered_combi, 30, 4), number=100) </code></pre> <p>results and more results(edit) (on windows7, python 64bit 2.7.3, core i5 ivy bridge with 8gb ram) : </p> <pre><code>(n, r) recursive itertools ---------------------------------------- (30, 4) 1.6728046 4.0149797 100 times 17550 combinations (20, 4) 2.6734657 7.0835997 1000 times 2380 combinations (10, 4) 0.1253318 0.3157737 1000 times 35 combinations (4, 2) 0.0091073 0.0120918 1000 times 3 combinations (20, 5) 0.6275073 2.4236898 100 times 4368 combinations (20, 6) 1.0542227 6.1903468 100 times 5005 combinations (20, 7) 1.3339530 12.4065561 100 times 3432 combinations (20, 8) 1.4118724 19.9793801 100 times 1287 combinations (20, 9) 1.4116702 26.1977839 100 times 220 combinations </code></pre> <p>as you can see, <strike>the gap between recursive solution and itertools.combination based solution gets wider as <code>n</code> goes up</strike>.</p> <p>in fact, with the gap between both solutions is heavily dependent on <code>r</code> - bigger <code>r</code> means you have to throw away more combinations generated from <code>itertools.combinations</code>. for example, in case of <code>n=20, r=9</code> : we filter and take only 220 combinations among 167960(20C9) combinations. if <code>n</code> and <code>r</code> are small, using <code>itertools.combinations</code> can be faster because it is more efficient at less r and does not use stack as I explained. (as you can see, itertools are very optimized(if write your logic with <code>for</code>, <code>if</code>, <code>while</code> and bunch of generator and list comprehensions, it won't be as fast as the abstracted one with itertools), and this is an one of reasons why people love python - you bring your code to higher level, and you get rewarded. not many languages to that.</p>
    singulars
    1. This table or related slice is empty.
    1. POGenerating non-consecutive combinations
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USthkang
    1. USthkang
    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
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThank you for your answer.
      singulars
      1. PO
      1. USKnoothe
    2. COThis is clearly not O(1) on the `next` call. Calculating exactly what it _is_ (in terms of `n` and `r`) is a bit harder… but the good news is that it seems like it has the same complexity as the filtered-itertools solution, so if we figure out how to calculate one, we know the answer for the other.
      singulars
      1. PO
      1. USabarnert
    3. COPS, why `[each for each in foo]` instead of just `list(foo)`?
      singulars
      1. PO
      1. USabarnert
 

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