Podría implementar una búsqueda binaria invertida.

 from typing import Union, List sorted_int_list = [1, 1, 2, 3, 3] unsorted_int_list = [1, 3, 2, 1, 3] sorted_str_list = [ "example.com", "example.com", "test.com", "stackoverflow.com", "stackoverflow.com", ] unsorted_str_list = [ "example.com", "stackoverflow.com", "test.com", "example.com", "stackoverflow.com", ] def inverted_binary_search( input_list: List[Union[str, int]], search_elem: Union[int, str], list_selector_start: int, list_selector_end: int, ) -> int: if list_selector_end - list_selector_start <= 1: if search_elem < input_list[list_selector_start]: return list_selector_start - 1 else: return list_selector_start list_selector_mid = (list_selector_start + list_selector_end) // 2 if input_list[list_selector_mid] > search_elem: return inverted_binary_search( input_list=input_list, search_elem=search_elem, list_selector_start=list_selector_mid, list_selector_end=list_selector_end, ) elif input_list[list_selector_mid] < search_elem: return inverted_binary_search( input_list=input_list, search_elem=search_elem, list_selector_start=list_selector_start, list_selector_end=list_selector_mid, ) else: return list_selector_mid def inverted_binary_insertion_sort(your_list: List[Union[str, int]]): for idx in range(1, len(your_list)): selected_elem = your_list[idx] inverted_binary_search_position = ( inverted_binary_search( input_list=your_list, search_elem=selected_elem, list_selector_start=0, list_selector_end=idx, ) + 1 ) for idk in range(idx, inverted_binary_search_position, -1): your_list[idk] = your_list[idk - 1] your_list[inverted_binary_search_position] = selected_elem return your_list

Producción

 inverted_sorted_int_list = inverted_binary_insertion_sort(sorted_int_list) print(inverted_sorted_int_list) >> [1, 3, 3, 2, 1] inverted_sorted_str_list = inverted_binary_insertion_sort(sorted_str_list) print(inverted_sorted_str_list) >> ['example.com', 'stackoverflow.com', 'stackoverflow.com', 'test.com', 'example.com']

Actualizar:

Teniendo en cuenta los comentarios, también podría ejecutar la función dos veces. Esto desenredará los duplicados.

 inverted_sorted_int_list = inverted_binary_insertion_sort( inverted_binary_insertion_sort(sorted_int_list) ) >> [1, 3, 2, 1, 3]

No existe una definición obvia de desorden que funcione mejor para usted, pero aquí hay algo que al menos funciona bien:

1. ordenar la lista
2. Si la longitud de la lista no es una potencia de dos, distribuya los elementos uniformemente en una lista con el siguiente tamaño de potencia de dos
3. Encuentre un nuevo índice para cada elemento invirtiendo los bits en su índice anterior.
4. Elimine los espacios para que la lista vuelva a su tamaño original.

En orden ordenado, los índices de los elementos que están juntos suelen diferir solo en los bits más pequeños. Al invertir el orden de los bits, los nuevos índices para los elementos que están muy juntos difieren en los bits más grandes , por lo que terminarán muy separados.

 def bitreverse(x, bits): # reverse the lower 32 bits x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1) x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2) x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4) x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8) x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16) # take only the appropriate length return (x>>(32-bits)) & ((1<<bits)-1) def antisort(inlist): if len(inlist) < 3: return inlist inlist = sorted(inlist) #get the next power of 2 list length p2len = 2 bits = 1 while p2len < len(inlist): p2len *= 2 bits += 1 templist = [None] * p2len for i in range(len(inlist)): newi = i * p2len // len(inlist) newi = bitreverse(newi, bits) templist[newi] = inlist[i] return [item for item in templist if item != None] print(antisort(["a","b","c","d","e","f","g", "h","i","j","k","l","m","n","o","p","q","r", "s","t","u","v","w","x","y","z"]))

Producción:

 ['a', 'n', 'h', 'u', 'e', 'r', 'k', 'x', 'c', 'p', 'f', 's', 'm', 'z', 'b', 'o', 'i', 'v', 'l', 'y', 'd', 'q', 'j', 'w', 'g', 't']

Espero que este algoritmo funcione correctamente:

 unsorted_list = ['c', 'a', 'a', 'a', 'a', 'b', 'b'] d = {i: unsorted_list.count(i) for i in unsorted_list} print(d) # {'c': 1, 'a': 4, 'b': 2} d = {k: v for k, v in sorted(d.items(), key=lambda item: item[1], reverse=True)} print(d) # {'a': 4, 'b': 2, 'c': 1} result = [None] * len(unsorted_list) border_index_left = 0 border_index_right = len(unsorted_list) - 1 it = iter(d) def set_recursively(k, nk): set_borders(k) set_borders(nk) if d[k]: set_recursively(k, nk) def set_borders(key): global border_index_left, border_index_right if key is not None and d[key]: result[border_index_left] = key d[key] = d[key] - 1 border_index_left = border_index_left + 1 if key is not None and d[key]: result[border_index_right] = key d[key] = d[key] - 1 border_index_right = border_index_right - 1 next_element = next(it, None) for k, v in d.items(): next_element = next(it, None) set_recursively(k, next_element) print(result) # ['a', 'b', 'a', 'c', 'a', 'b', 'a']

Visualmente, parece caminar desde el borde hasta el medio:

 [2, 3, 3, 3, 1, 1, 0] [None, None, None, None, None, None, None] [3, None, None, None, None, None, None] [3, None, None, None, None, None, 3] [3, 1, None, None, None, None, 3] [3, 1, None, None, None, 1, 3] [3, 1, 3, None, None, 1, 3] [3, 1, 3, 2, None, 1, 3] [3, 1, 3, 2, 0, 1, 3]

Usé Google OR Tools para resolver este problema. Lo enmarqué como un problema de optimización de restricciones y lo modelé de esa manera.

 from collections import defaultdict from itertools import chain, combinations from ortools.sat.python import cp_model model = cp_model.CpModel() data = [ ('example.com', 'http://example.com/404'), ('test.com', 'http://test.com/404'), ('test.com', 'http://test.com/405'), ('example.com', 'http://example.com/405'), ('google.com', 'http://google.com/404'), ('example.com', 'http://example.com/406'), ('stackoverflow.com', 'http://stackoverflow.com/404'), ('test.com', 'http://test.com/406'), ('example.com', 'http://example.com/407') ] tmp = defaultdict(list) for (domain, url) in sorted(data): var = model.NewIntVar(0, len(data) - 1, url) tmp[domain].append(var) # store URLs as model variables where the key is the domain vals = list(chain.from_iterable(tmp.values())) # create a single list of all variables model.AddAllDifferent(vals) # all variables must occupy a unique spot in the output constraint = [] for urls in tmp.values(): if len(urls) == 1: # a single domain does not need a specific constraint constraint.append(urls[0]) continue combos = combinations(urls, 2) for (x, y) in combos: # create combinations between each URL of a specific domain constraint.append((x - y)) model.Maximize(sum(constraint)) # maximize the distance between similar URLs from our constraint list solver = cp_model.CpSolver() status = solver.Solve(model) output = [None for _ in range(len(data))] if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE: for val in vals: idx = solver.Value(val) output[idx] = val.Name() print(output) ['http://example.com/407', 'http://test.com/406', 'http://example.com/406', 'http://test.com/405', 'http://example.com/405', 'http://stackoverflow.com/404', 'http://google.com/404', 'http://test.com/404', 'http://example.com/404']

Aquí hay una puñalada, pero no estoy seguro de que no degenere un poco dados conjuntos de entrada particulares.

Elegimos el elemento encontrado con más frecuencia y agregamos su primera aparición a una lista. Luego lo mismo con el segundo más frecuente y así sucesivamente.

Repita la mitad del tamaño del elemento más encontrado. Esa es la mitad izquierda de la lista.

Luego, pasando de menos frecuente a más frecuente, elija el primer elemento y agregue sus valores. Cuando se encuentra un artículo a menos de la mitad del máximo, elige de qué lado quieres ponerlo.

Esencialmente, superponemos clave por clave y terminamos con elementos más frecuentes en las posiciones más a la izquierda y más a la derecha en la lista sin ordenar, dejando los menos frecuentes en el medio.

 def unsort(lst:list) -> list: """ build a dictionary by frequency first then loop thru the keys and append key by key with the other keys in between """ result = [] #dictionary by keys (this would be domains to urls) di = defaultdict(list) for v in lst: di[v].append(v) #sort by decreasing dupes length li_len = [(len(val),key) for key, val in di.items()] li_len.sort(reverse=True) #most found count max_c = li_len[0][0] #halfway point odd = max_c % 2 num = max_c // 2 if odd: num += 1 #frequency, high to low by_freq = [tu[1] for tu in li_len] di_side = {} #for the first half, pick from frequent to infrequent #alternating by keys for c in range(num): #frequent to less for key in by_freq: entries = di[key] #first pass: less than half the number of values #we don't want to put all the infrequents first #and have a more packed second side if not c: #pick on way in or out? if len(entries) <= num: #might be better to alternate L,R,L di_side[key] = random.choice(["L","R"]) else: #pick on both di_side[key] = "B" #put in the left half do_it = di_side[key] in ("L","B") if do_it and entries: result.append(entries.pop(0)) #once you have mid point pick from infrequent to frequent for c in range(num): #frequent to less for key in reversed(by_freq): entries = di[key] #put in the right half do_it = di_side[key] in ("R","B") if entries: result.append(entries.pop(0)) return result

Ejecutando esto obtuve:

 ([1, 1, 2, 3, 3], '2.00', '====>', [3, 1, 2, 1, 3], '3.41') ([1, 3, 2, 3, 1], '3.41', '====>', [3, 1, 2, 1, 3], '3.41') ([1, 2, 3, 0, 1, 2, 3], '6.00', '====>', [3, 2, 1, 0, 1, 2, 3], '5.86') ([3, 2, 1, 0, 1, 2, 3], '5.86', '====>', [3, 2, 1, 0, 1, 2, 3], '5.86') ([3, 2, 1, 3, 1, 2, 3], '6.88', '====>', [3, 2, 3, 2, 1, 3, 1], '5.97') ([1, 2, 3, 4, 5], '0.00', '====>', [5, 1, 2, 3, 4], '0.00')

Ah, y también agregué una assert para verificar que no se haya eliminado o alterado nada por la clasificación:

 assert(sorted(lst) == sorted(ulst))

enfoque alternativo?

Lo dejaré como una nota al pie por ahora, pero la idea general de no agrupar (no la aplicación específica del OP de no sobrecargar dominios) parece ser un candidato para un enfoque de fuerza repulsiva, donde los dominios idénticos tratarían de mantener tan lejos unos de otros como sea posible. es decir 1, 1, 2 => 1, 2, 1 porque los 1 se repelerían entre sí. Sin embargo, ese es un enfoque algorítmico completamente diferente.

En lugar de desordenar su lista de URL, ¿por qué no agruparlas por dominio, cada una en una cola, y luego procesarlas de forma asíncrona con un retraso (¿aleatorio?) en el medio?

Me parece menos complejo que lo que está tratando de hacer para lograr lo mismo y si tiene mucho dominio, siempre puede acelerar el número para ejecutarlo simultáneamente en ese punto.

Una manera fácil de codificar una lista es maximizar su puntuación de "clasificación" utilizando un algoritmo genético con un cromosoma de permutación. Pude piratear rápidamente una versión en R usando el paquete GA. No soy un usuario de Python, pero estoy seguro de que hay bibliotecas GA para Python que incluyen cromosomas de permutación. Si no, se puede adaptar una biblioteca GA general con cromosomas vectoriales de valor real. Simplemente usa un vector con valores en [0, 1] como un cromosoma y convierte cada vector a su índice de clasificación.

Cuando enfrenté un problema similar, así es como lo resolví:

1. Defina la "distancia" entre dos cadenas (URL en este caso) como su distancia de Levenshtein (el código para calcular este valor está disponible)
2. Adopte su algoritmo de vendedor ambulante favorito para encontrar la ruta más corta (aproximada) a través de su conjunto de cadenas (encontrar la ruta más corta exacta no es computacionalmente factible, pero los algoritmos aproximados son bastante eficientes)
3. Ahora modifique su métrica de "distancia" para invertirla, es decir, calcule la distancia entre dos cadenas (s1, s2) como MAX_INT - LevenshteinDistance(s1,s2)
4. Con esta modificación, el "camino más corto" a través de su conjunto es ahora realmente el camino más largo, es decir, el más desordenado.

Solo digo que poner un retraso de tiempo corto funcionaría bien. Creo que alguien ya lo mencionó. Es muy sencillo y muy fiable. Podrías hacer algo como:

 from random import sample from time import sleep import requests intervalList = list(range(0.1, 0.5)) error404 = [] connectionError = [] for i in your_URL_list: ststusCode = req.get(str(i)).status_code if ststusCode == 404: error404.append(i) sleep(sample(intervalList,1))

Salud