Eliminating Consecutive Numbers

user_11595664 0
Viewed 134

If you have a range of numbers from 1-49 with 6 numbers to choose from, there are nearly 14 million combinations. Using my current script, I currently have only 7.2 million combinations remaining. Of the 7.2 million remaining combinations, I want to eliminate all 3, 4, 5, 6, dual, and triple consecutive numbers. Example:

  • 3 consecutive: 1, 2, 3, x, x, x
  • 4 consecutive: 3, 4, 5, 6, x, x
  • 5 consecutive: 4, 5, 6, 7, 8, x
  • 6 consecutive: 5, 6, 7, 8, 9, 10
  • double separate consecutive: 1, 2, 5, 6, 14, 18
  • triple separate consecutive: 1, 2, 9, 10, 22, 23

Note: combinations such as 1, 2, 12, 13, 14, 15 must also be eliminated or else they conflict with the rule that double and triple consecutive combinations to be eliminated.

I'm looking to find how many combinations of the 7.2 million remaining combinations have zero consecutive numbers (all mixed) and only 1 consecutive pair.

Thank you!

import functools

_MIN_SUM     = 120
_MAX_SUM     = 180
_MIN_NUM     = 1
_MAX_NUM     = 49
_NUM_CHOICES = 6
_MIN_ODDS    = 2
_MAX_ODDS    = 4

@functools.lru_cache(maxsize=None)
def f(n, l, s = 0, odds = 0):
    if s > _MAX_SUM or odds > _MAX_ODDS:
        return 0
    if n == 0 :
        return int(s >= _MIN_SUM and odds >= _MIN_ODDS)
    return sum(f(n-1, i+1, s+i, odds + i % 2) for i in range(l, _MAX_NUM+1))


result = f(_NUM_CHOICES, _MIN_NUM)

print('Number of choices = {}'.format(result))
python
2 Answers

While my answer should work, I think someone might be able to offer a faster solution.

Consider the following code:

not_allowed = []
for x in range(48):
    not_allowed.append([x, x+1, x+2])

# not_allowed = [ [0,1,2], [1,2,3], ... [11,12,13], ... [47,48,49] ]
my_numbers = [[1, 2, 5, 9, 11, 33], [1, 3, 7, 8, 9, 31], [12, 13, 14, 15, 23, 43]]
for x in my_numbers:
    for y in not_allowed:
        if set(y) <= set(x): # if [1,2,3] is a subset of [1,2,5,9,11,33], etc.
            # drop x

This code will remove all instances that contain double consecutive numbers, which is all you really need to check for, because triple, quadruple, etc. all imply double consecutive. Try implementing this and let me know how it works.

user_96104940

The easiest approach is probably to generate and filter. I used numpy to try to vectorize as much of this as I could:

import numpy as np
from itertools import combinations
combos = np.array(list(combinations(range(1, 50), 6)))  # build all combos
# combos is shape (13983816, 6)
filt = np.where(np.bincount(np.where(np.abs(
    np.subtract(combos[:, :-1], combos[:, 1:])) == 1)[0]) <= 1)[0]  # magic!
filtered = combos[filt]
# filtered is shape (12489092, 6)

Breaking down that "magic" line

  • First we subtract the first five items in the list from the last five items to get the differences between them. We do this for the entire set of combinations in one shot with np.subtract(combos[:, :-1], combos[:, 1:]). Note that itertools.combinations produces sorted combinations, on which this depends.
  • Next we take the absolute value of these differences to make sure we only look at positive distances between numbers with np.abs(...).
  • Next we grab the indicies from this operation for the entire dataset that indicate a difference of 1 (consecutive numbers) with np.where(... == 1)[0]. Note that np.where returns a tuple where the first item are all of the rows, and the second item are all of the corresponding columns for our condition. This is important because any row value that shows up more than once tells us that we have more than one consecutive number in that row!
  • So we count how many times each row shows up in our results with np.bincount(...), which will return something like [5, 4, 4, 4, 3, 2, 1, 0] indicating how many consecutive pairs are in each row of our combinations dataset.
  • Finally we grab only the row numbers where there are 0 or 1 consecutive values with np.where(... <= 1)[0].

I am returning way more combinations than you seem to indicate, but I feel fairly confident that this is working. By all means, poke holes in it in the comments and I will see if I can find fixes!

Bonus, because it's all vectorized, it's super fast!

user_24645970
Related