Supongamos que hay n conjuntos de números reales: S[1], S[2], ..., S[n] . Sabemos dos cosas acerca de estos conjuntos:
Cada conjunto S[i] tiene exactamente 3 elementos.
Todos los elementos en cada uno de los conjuntos S[i] son números reales en el rango [0, 1]. (Sin embargo, no sé si este detalle puede ser útil para la solución).
Consideremos un conjunto T de todos los números que se pueden representar como p[1] * p[2] * p[3] * ... * p[n] donde p[i] es un elemento de S[i]. Este conjunto T , obviamente, tiene 3^n elementos.
Mi pregunta es, dados los conjuntos S[1], S[2], ..., S[n] (1 <= n <= 30) y algo de 1 <= k <= 10 como entrada, ¿podemos encontrar el k-ésimo número más grande en T más rápido que en O(3^n) tiempo? Es importante que no solo necesito el k-ésimo número más grande, sino también los números correspondientes ( p[1], p[2], p[3], ... , p[n] ) que lo producen.
Incluso si la respuesta es no, agradecería alguna pista sobre cómo resolvería este problema aproximadamente, tal vez, utilizando algunas heurísticas. Conozco la búsqueda por haz , pero tal vez podría sugerir algo más. E incluso para la búsqueda de haz, no está muy claro cómo implementarlo aquí de la mejor manera.
Si la respuesta exacta se puede obtener algorítmicamente en menos de O(3^n) tiempo, le agradecería enormemente que me señalara la solución.
Bueno, sabes que el producto más grande es el que usa el factor más grande de cada conjunto.
Además, cualquier otro producto se puede formar comenzando con uno más grande y luego disminuyendo el factor elegido en exactamente un conjunto.
Eso lleva a una búsqueda simple:
Coloque el producto más grande en una cola de máxima prioridad.
Repetir k veces:
un. Eliminar el producto más grande p de la cola de prioridad
B. Para cada conjunto que tenga un número menor que el seleccionado en p, genere el producto formado por la disminución de ese número al siguiente más bajo en ese conjunto. Si esta selección de factores no se ha visto antes, agréguela a la cola de prioridad.
Los productos se eliminarán de la cola en orden decreciente, por lo que el k-ésimo que saque es el k-ésimo más grande.
La complejidad se trata de N*(k log kN), dependiendo de cómo implemente las cosas.
Tenga en cuenta que puede haber múltiples formas de seleccionar los factores que producen el mismo producto. Esta solución considera que esas vías son productos distintos, es decir, cada vía se cuenta al encontrar la k-ésima mayor. Eso puede o no ser lo que quieres.
Para poner la discusión anterior en código podemos hacer lo siguiente:
import operator from functools import partial, reduce import heapq def prod_by_data(tup, data): return reduce(operator.mul, (datum[t] for t, datum in zip(tup, data)), 1) def downset(tup): return [ tuple(t - (1 if j == i else 0) for j, t in enumerate(tup)) for i in range(len(tup)) if tup[i] > 0 ] data = [ [1, 2, 3], [4, 2, 1], [8, 1, 3], [1, 1, 2], ] data = [sorted(d) for d in data] prod = partial(prod_by_data, data=data) k_smallest = [tuple(len(dat) - 1 for dat in data)] possible_k_smallest = [] while len(k_smallest) < 10: new_possible = sorted(downset(k_smallest[-1]), key=prod, reverse=True) possible_k_smallest = heapq.merge(possible_k_smallest, new_possible, key=prod, reverse=True) k_smallest.append(next(possible_k_smallest)) print(k_smallest) print([prod(tup) for tup in k_smallest])Mantenemos un montón de los elementos más pequeños. Después de sacar el más pequeño, debemos verificar todo si está al revés (tuplas que difieren exactamente en una posición), porque esas tuplas podrían ser el siguiente elemento más pequeño.
Vemos que miramos a través k - 1 veces clasificando O(n) elementos cada vez con una clave que en sí misma es O(n). Debido a la clave, esto debería hacer que la clasificación tome O (n ^ 2) en lugar de O (n log n). heapq es perezoso y, por lo tanto, salir de él es en realidad O (k). La clasificación y preparación inicial también debe ser O(n). En general, creo que esto hace que todo sea O (kn ^ 2).