Trouver tuples qui se chevauchent dans une liste Python et les mélangeant

Question

je la liste suivante de tuples dans Python3.x, chaque tuple se compose de deux entiers au format (start, end):

list_tuple = [(20, 35), (125, 145), (156, 178), (211, 233), (220, 321), 
           (227, 234), (230, 231), (472, 498), (4765, 8971)] 
## list already sorted except for last tuple 

Ce des tuples comme des intervalles le long d'une ligne réelle, par exemple (1,10) est un intervalle de 1 à 10.

Il y a trois façons de trier ce tuple, soit par le premier élément seul, par le second élément seul, soit par le premier et le second élément.

Tri par le premier élément seul:

sorted_by_first = sorted(list_tuple, key=lambda element: (element[0])) ## (first_element, second_element) 

qui délivre en sortie

print(sorted_by_first) 
[(20, 35), (125, 145), (156, 178), (211, 233), (220, 321), (227, 234), (230, 231), (472, 498), (4765, 8971)] 

et pour le tri sur la base du deuxième élément:

sorted_by_second = sorted(list_tuple, key=lambda element: (element[1])) 

qui délivre en sortie

print(sorted_by_second) 
[(20, 35), (125, 145), (156, 178), (230, 231), (211, 233), (227, 234), (220, 321), (472, 498), (4765, 8971)] 

et pour les deux:

sorted_by_both = sorted(list_tuple, key=lambda element: (element[0], element[1])) 

qui délivre en sortie

print(sorted_by_both) 
[(20, 35), (125, 145), (156, 178), (211, 233), (220, 321), (227, 234), (230, 231), (472, 498), (4765, 8971), ...] 

Notez que chacune de ces sorties sont classées dans un ordre différent. Les tuples qui diffèrent par ordre sont des "intervalles de chevauchement", par ex. devrait (227, 234) être placé avant ou après (230, 231), que ces intervalles se chevauchent.

Mon but est de créer une fonction qui (1) recherche la sortie triée pour les "intervalles de chevauchement" et (2) puis les permute aléatoirement entre eux.

Je peux penser à une fonction qui sort tous les tuples qui chevauchent un tuple donné, par ex.

def find_overlaps(input_tuple_list, search_interval): 
    results = [] 
    for tup in input_tuple_list: 
     if ((tup[0] >= search_interval[0] and tup[0] <= search_interval[1]) or (tup[1] >= search_interval[0] and tup[1] <= search_interval[1])): 
      results.append(tup) 
    return results 

qui fonctionne comme suit

foo = (130, 150) 
overlapping_foo = find_overlaps(list_tuple, foo) 
print(overlapping_foo) 
[(125, 145)] 

Cependant, afin d'atteindre l'objectif (1), je dois écrire une fonction qui trouve toutes les lignes qui se chevauchent dans list_tuple. Ce que j'ai essayé: J'ai d'abord pensé que je pouvais rechercher le tuple original avec lui-même, par ex.

total_overlaps = [] 
for tupp in list_tuple: 
    total_overlaps.append(find_overlaps(list_tuple, tupp)) 

Ceci est évidemment faux, car la sortie est le tuple d'origine lui-même.

Le plus gros problème avec est que je ne vois pas comment exécuter le but (2). Je dois seulement mélanger/réorganiser les tuples qui se chevauchent.Disons que j'avais une liste de tuples qui se chevauchent résultat (1):

overlap_list = [(211, 233), (220, 321), (227, 234), (230, 231), (6491, 7000), (6800, 7200)] 

La compréhension de la liste suivante échoue

from random import shuffle 
reordered = [shuffle(tupp) for tupp in overlap_list] 

donnant

TypeError: 'tuple' object does not support item assignment 

Il est également important que je ne mélangez pas (6491, 7000) avec (211, 233), car ceux-ci ne sont pas liés.

Comment trouver les intervalles de chevauchement dans la liste des tuples, puis mélanger individuellement ces tuples qui se chevauchent.

Answer 1

Notez bien que je comprends ce que vous demandez concernant le shuffle. Mais vous pouvez utiliser la itertools recette pairwise pour jumeler les éléments, puis utiliser itertools.groupby(), pour regrouper les chevauchements successifs, à savoir diviser (211, 233) de (6491, 7000):

import itertools as it 

def pairwise(iterable): 
    "s -> (s0,s1), (s1,s2), (s2, s3), ..." 
    a, b = it.tee(iterable) 
    next(b, None) 
    return zip(a, b) 

>>> overlap_list = [(211, 233), (220, 321), (227, 234), (230, 231), (6491, 7000), (6800, 7200)] 
>>> [list(p) for k, p in it.groupby(pairwise(overlap_list), lambda x: x[0][0] < x[1][0] < x[0][1]) if k] 
[[((211, 233), (220, 321)), ((220, 321), (227, 234)), ((227, 234), (230, 231))], 
[((6491, 7000), (6800, 7200))]] 

Vous pourriez unpairwise ces listes avec:

def unpairwise(iterable): 
    a, b = zip(*iterable) 
    yield a[0] 
    yield from b 

donc:

>>> [list(unpairwise(p)) for k, p in it.groupby(pairwise(overlap_list), lambda x: x[0][0] < x[1][0] < x[0][1]) if k] 
[[(211, 233), (220, 321), (227, 234), (230, 231)], [(6491, 7000), (6800, 7200)]] 

Answer 2

Extension de la réponse de @AChampion, il devrait être facile de mélanger votre liste de listes de tuples qui se chevauchent pour obtenir ce que vous voulez:

>>> overlaps = [[(211, 233), (220, 321), (227, 234), (230, 231)], [(6491, 7000), (6800, 7200)]] 
>>> for x in overlaps: 
...  random.shuffle(x) 
... 
>>> overlaps 
[[(227, 234), (230, 231), (220, 321), (211, 233)], [(6491, 7000), (6800, 7200)]] 
>>> for x in overlaps: 
...  random.shuffle(x) 
... 
>>> overlaps 
[[(220, 321), (227, 234), (230, 231), (211, 233)], [(6491, 7000), (6800, 7200)]] 
>>> for x in overlaps: 
...  random.shuffle(x) 
... 
>>> overlaps 
[[(227, 234), (211, 233), (220, 321), (230, 231)], [(6800, 7200), (6491, 7000)]] 

Notez que random.shuffle est en place.