Generate all combinations with maximum difference of consecutive elements

Question

I would like to generate combinations with length 9 out of a sorted list (length 150) without any repeated values:

24, 110, 157, 256, 278, 368, 416, 502, 593, 666, 751, 801, 827, 925, 991, 1044, 1118, 1159, 1203, 1296, 1375, 1479, 1546, 1621, 1679, 1695, 1726, 1832, 1922, 1978, 1995, 2041, 2119, 2160, 2240, 2315, 2421, 2493, 2527, 2543, 2559, 2654, 2762, 2813, 2883, 2950, 2982, 3009, 3052, 3103, 3162, 3239, 3346, 3427, 3462, 3480, 3548, 3638, 3670, 3761, 3833, 3898, 3946, 3979, 4051, 4096, 4124, 4219, 4289, 4393, 4455, 4497, 4590, 4695, 4769, 4835, 4874, 4891, 4965, 5065, 5159, 5247, 5323, 5352, 5406, 5493, 5534, 5581, 5687, 5796, 5881, 5982, 6049, 6110, 6200, 6266, 6297, 6312, 6392, 6452, 6501, 6599, 6651, 6734, 6758, 6799, 6859, 6912, 6942, 7049, 7149, 7258, 7296, 7317, 7363, 7446, 7494, 7589, 7653, 7737, 7803, 7820, 7929, 8012, 8117, 8135, 8174, 8242, 8349, 8417, 8511, 8589, 8611, 8643, 8717, 8765, 8795, 8854, 8880, 8936, 8987, 9041, 9100, 9186, 9292, 9398, 9472, 9502, 9598, 9642, 9731, 9789, 9864, 9936

I already tried it with:

itertools.combinations(list, 9)

However, that's not very efficient and would generate more than a billion combinations. I only want the combinations where the difference between each pair of consecutive numbers is 150 or less. For example, the combination

(24, 110, 157, 256, 278, 368, 416, 502, 593)

has no consecutive pairs with a difference greater than 150, but the combination

(24, 110, 157, 256, 278, 368, 416, 502, 9936)

has a consecutive pair 502, 9936 with a difference greater than 150.

How can I achieve this in Python? The input list is sorted and I need the output to be sorted as well.

---

I already found this solution, which was very good. However the output wasn't sorted which was my problem, and it generates combinations where every pair has a maximum difference of 150 - not just consecutive pairs - so it excludes the example given above because 593 - 24 > 150.

import itertools
import random

def combs(nums):
    result = set()
    for lower in nums:
        options = [n for n in nums if lower <= n <= lower + 150]
        result.update(itertools.combinations(options, 9))
    return result

print(combs([random.randrange(0, 5000) for _ in range(150)]))

Encephalitis

I meant the difference between every pair of numbers in the combination – Encephalitis

My input list is sorted, the code written above was from an older version – Encephalitis

Possible duplicate of How to generate all possible combinations with a given condition to make it more efficient? – Cheiron

Answer 1

To sort the output you can use python's sorted() function.

Full code:

import itertools, random

def combs(nums):
  result = set()
  for lower in nums:
     options = [n for n in nums if lower <= n <= lower + 150] 
     result.update(itertools.combinations(options, 9))
  return result

unsorted = combs([random.randrange(0, 5000) for _ in range(150)])

# Go through each element in your set and sort it - must convert result to tuple
sorted_set = set()
for elem in unsorted:
  elem = tuple(sorted(elem))
  sorted_set.add(elem)

Sutherlan

saying a <= n <=b is not correct syntax - on the contrary, this is correct syntax in Python. See docs.python.org/3/reference/expressions.html#comparisons – Cheiron

The last step of sorting each tuple is unnecessary given that the input list is supposed to already be sorted. – Cheiron

Thanks for the heads up, I was not aware of this! – Sutherlan

According to the OP and what I can see, unsorted is not sorted and they would like to sort it. – Sutherlan

First of all, thank you very much for your answer. I just realized, that the code does only create combinations, where the first element and the last element have the difference. But I want a combination where each element does have a maximum difference of 150 to the previous and the next element and not only the first element to the last one. – Encephalitis

The only sorting you should need to do here is just to sort the list nums, since it has been generated randomly and therefore isn't in order. If you do that then the tuples that itertools.combinations produces will naturally be in order. The question says that nums ought to be in order, so this seems like a simple oversight. – Cheiron

@Cheiron Thanks but how can I change the code in order to have a maximum difference of 150 between each of the elements instead of the first and last element? – Encephalitis

My input list is sorted, the code written above was from an older version – Encephalitis

Having a difference of at most 150 between the smallest and largest element is equivalent to having a difference of at most 150 between every pair of elements. – Cheiron

No, it's a difference whether I have 100, 105, .., 250 or 100, 250, 400,..., 1200 – Encephalitis

Having it be exactly 150 apart, would make it not as random as you mentioned. If your tuples are fixed in length, you would just need to randomly select the first element and add 150 to it until you get to the correct length. – Sutherlan

No sry, it doesnt have to be exactly 150, but it has to have a maximum difference to the next element of 150 – Encephalitis

Then what @Cheiron said makes complete sense. You probably want the difference between 2 neighboring elements to be at least 150? – Sutherlan

No, I want all possible combinations, where the distance between an element and the following element is a maximum of 150 – Encephalitis

So you want a maximum difference between only consecutive elements, not between all elements. I asked under the question whether you meant consecutive pairs, and you said between "every pair", which includes the smallest and the largest (i.e. first and last). – Cheiron

Yeah exactly, I'm sorry if I didnt express myself clearly enough – Encephalitis

Does anybody of you sees a way to do this (have a max difference between only consecutive elements)? – Encephalitis