Geek asks and answers

Creating non-sequential combinations

I am trying to create a generator (an iterator that supports the execution of the following, possibly using yield in python), which gives all combinations of r elements from {1,2, ... n} (n and r are parameters), such as that in the selected there are no two consecutive elements of r.

For example, for r = 2 and n = 4

The generated combinations {1,3}, {1,4}, {2, 4}.

I could generate all combinations (as an iterator) and filter those that do not meet the criteria, but we will do unnecessary work.

Is there any generation algorithm such that nextis O (1) (and if this is not possible, O (r) or O (n)).

The order in which the sets are returned does not matter (and, I hope, allows the use of the O (1) algorithm).

Note. I marked it as python, but the agnostic algorithm will also help.

Update:

I found a way to display it to create clean combinations! A web search shows that O (1) is possible for combinations (although it seems complicated).

Here is the mapping.

Suppose we have a combination of x_1, x_2, ..., x_r with x_1 + 1 <x_2, x_2 + 1 <x_3, ...

We pass to y_1, y_2, ..., y_r as follows

y_1 = x_1

y_2 = x_2 - 1

y_3 = x_3 - 2

...

y_r = x_r - (r-1)

Thus, we have that y_1 <y_2 <y_3 ... without an indispensable restriction!

It basically comes down to choosing r elements from nr + 1. Thus, all I need to do is start the generation for (nr + 1 select r).

For our purposes, using display after things are generated is good enough.

Reasons for choosing svkcr answer

All great answers, but I chose svkcr answer.

,

1) ( "" ). . : O (r) .

2) . (), .

( ), ( , CPU/ )!

, , , , .

+5
5

! :

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] <= 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 > 0 and combination[p] + a > 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)

next() O (r).. , , , , .

> list(nonconsecutive_combinations(2, 4))
[(1, 3), (1, 4), (2, 4)]
> list(nonconsecutive_combinations(3, 6))
[(1, 3, 5), (1, 3, 6), (1, 4, 6), (2, 4, 6)]

, .

c r, :

  • , 2. (c[x] >= c[x-1] + 2)
  • n. - 1. , , n. (c[r-1] <= n)

, , (1, 3, 5, ..., 2*r-1). , "" , .

Blckknght, , 2.

while:

  • , 1. , , :

    combination = range(1, r*2, 2)
while combination[r-1] <= n:

    1. 2 2.

  • , 1.

    yield tuple(combination)

    while (2) , , 1, .

    , , "1" .

    # we don't actually do this:
combination[r-1] += 1

    2 . , 2, . 10: " 9, 0." , 1.

    # if above does not work
combination[r-2] += 1
combination[r-1]  = combination[r-2] + 2

    , . , , , , a. p , .

    p = r-1
a = 1
while p > 0 and combination[p] + a > n:
  p -= 1
  a += 2

    (p = r-1, p - = 1) . (a = 1), 2*x, x - . (a + = 2, [p] + a)

    , , , , , 2:

    combination[p:] = range(combination[p]+1, combination[p] + 2*(r-p), 2)

    . , , " ", , . , , :)

..

, , , Python. , Python. , .

, , , , C. while - O (log r), O (log r). , , . , , C, .

+2

( n+1 - , n - ):

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]]

:

O (1) - O (1). , , r, r -item. , r , . n r, , itertools.

:

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)

( Windows 7, python 64 2.7.3, ​​i5 8- ):

(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

, itertools.combination , n .

, r - r , , itertools.combinations. , n=20, r=9: 220 167960 (20C9). n r , itertools.combinations , r , . ( , itertools ( for, if, while , , itertools), , python - , , .

+3

O (1), O (r) . , itertools.combinations O (1) next, r-1 , r-1 O (1), right?

, , , O (1) combinations, O (r). - ? . ...

:

def nonconsecutive_combinations(p, r):
    def good(combo):
        return not any(combo[i]+1 == combo[i+1] for i in range(len(combo)-1))
    return filter(good, itertools.combinations(p, r))

r, n = 2, 4
print(list(nonconsecutive_combinations(range(1, n+1), r))

:

[(1, 3), (1, 4), (2, 4)]

itertools , combinations O (1) next. , O (1), , , .

, ... , .

http://pastebin.com/ydk1TMbD , thkang . - , .

n 4 20 r, 2, , . (, , , , the total length). n 7 20 r, 4, .

n 12 r 2 5, 2 5, 1 6, .

- 924 6 , ? next , n . , .

, combinations O (1) next; , - . O (r) next; . , , next ( , , ).

, . ( , return yield from , ... , ?)

+2

:

def combinations_nonseq(r, n):
    if r == 0:
        yield ()
        return

    for v in range(2*r-1, n+1):
        for c in combinations_nonseq(r-1, v-2):
            yield c + (v,)

, thkang, . n r*2-1, , r ( n) . , svckr, n r.

, , , n 2*r-1, , . , thkang.

thkang test. timeit, , , . # , ( , ).

( n, r)      # |abarnert |  thkang |   svckr |BlckKnght| Knoothe |JFSebastian
===============+=========+=========+=========+=========+=========+========
(16, 2)    105 |  0.0037 |  0.0026 |  0.0064 |  0.0017 |  0.0047 |  0.0020
(16, 4)    715 |  0.0479 |  0.0181 |  0.0281 |  0.0117 |  0.0215 |  0.0143
(16, 6)    462 |  0.2034 |  0.0400 |  0.0191 |  0.0125 |  0.0153 |  0.0361
(16, 8)      9 |  0.3158 |  0.0410 |  0.0005 |  0.0006 |  0.0004 |  0.0401
===============+=========+=========+=========+=========+=========+========
(24, 2)    253 |  0.0054 |  0.0037 |  0.0097 |  0.0022 |  0.0069 |  0.0026
(24, 4)   5985 |  0.2703 |  0.1131 |  0.2337 |  0.0835 |  0.1772 |  0.0811
(24, 6)  27132 |  3.6876 |  0.8047 |  1.0896 |  0.5517 |  0.8852 |  0.6374
(24, 8)  24310 | 19.7518 |  1.7545 |  1.0015 |  0.7019 |  0.8387 |  1.5343

n abarnert , :

( n, r)      # |  thkang |   svckr |BlckKnght| Knoothe |JFSebastian
===============+=========+=========+=========+=========+========
(32, 2)    465 |  0.0069 |  0.0178 |  0.0040 |  0.0127 |  0.0064
(32, 4)  23751 |  0.4156 |  0.9330 |  0.3176 |  0.7068 |  0.2766
(32, 6) 296010 |  7.1074 | 11.8937 |  5.6699 |  9.7678 |  4.9028
(32, 8)1081575 | 37.8419 | 44.5834 | 27.6628 | 37.7919 | 28.4133

, , .

+2

Here's a solution similar to @thkang's answer , but with an explicit stack:

def combinations_stack(seq, r):
    stack = [(0, r, ())]
    while stack:
        j, r, prev = stack.pop()
        if r == 0:
            yield prev
        else:
            for i in range(len(seq)-1, j-1, -1):
                stack.append((i+2, r-1, prev + (seq[i],)))

Example:

print(list(combinations_stack(range(1, 4+1), 2)))
# -> [(1, 3), (1, 4), (2, 4)]

For some values, (n, r)this is the fastest solution according to the reference on my machine:

name                                time ratio comment
combinations_knoothe           17.4 usec  1.00 8 4
combinations_blckknght         17.9 usec  1.03 8 4
combinations_svckr             20.1 usec  1.16 8 4
combinations_stack             62.4 usec  3.59 8 4
combinations_thkang            69.6 usec  4.00 8 4
combinations_abarnert           123 usec  7.05 8 4
name                                time ratio comment
combinations_stack              965 usec  1.00 16 4
combinations_blckknght         1e+03 usec  1.04 16 4
combinations_knoothe           1.62 msec  1.68 16 4
combinations_thkang            1.64 msec  1.70 16 4
combinations_svckr             1.84 msec  1.90 16 4
combinations_abarnert           3.3 msec  3.42 16 4
name                                time ratio comment
combinations_stack               18 msec  1.00 32 4
combinations_blckknght         28.1 msec  1.56 32 4
combinations_thkang            40.4 msec  2.25 32 4
combinations_knoothe           53.3 msec  2.96 32 4
combinations_svckr             59.8 msec  3.32 32 4
combinations_abarnert          68.3 msec  3.79 32 4
name                                time ratio comment
combinations_stack             1.84  sec  1.00 32 8
combinations_blckknght         2.27  sec  1.24 32 8
combinations_svckr             2.83  sec  1.54 32 8
combinations_knoothe           3.08  sec  1.68 32 8
combinations_thkang            3.29  sec  1.79 32 8
combinations_abarnert            22  sec 11.99 32 8

where combinations_knootheis the implementation of the algorithm described in the question:

import itertools
from itertools import imap as map

def _combinations_knoothe(n, r):
    def y2x(y):
        """
        y_1 = x_1
        y_2 = x_2 - 1
        y_3 = x_3 - 2
        ...
        y_r = x_r - (r-1)
        """
        return tuple(yy + i for i, yy in enumerate(y))
    return map(y2x, itertools.combinations(range(1, n-r+1+1), r))

def combinations_knoothe(seq, r):
    assert seq == list(range(1, len(seq)+1))
    return _combinations_knoothe(len(seq), r)

and other functions - from the corresponding answers (modified to enter input in a unified format).

+1
source

More articles:


All Articles