Supongamos que tiene un conjunto de conjuntos de enteros. Es posible que algunos de los conjuntos se superpongan (es decir, compartan elementos). Puede deshacerse de las superposiciones eliminando elementos de los conjuntos, pero luego algunos de ellos pueden terminar vacíos; Eso sería una verguenza. ¿Podemos hacer que todos los conjuntos sean disjuntos sin vaciar ninguno de ellos?
Tenga en cuenta que en esta situación, nunca hay ninguna razón para dejar múltiples elementos en un conjunto, por lo que este problema siempre se puede resolver reduciendo cada conjunto a un solo elemento. Esa es la versión del problema que estamos resolviendo aquí.
La tarea
Escriba un programa o función, como sigue:
Entrada : una lista de conjuntos de enteros.
Salida : una lista de enteros, de la misma longitud que la entrada, para los cuales:
- Todos los enteros en la salida son distintos; y
- Cada número entero en la salida es un elemento del conjunto correspondiente de la entrada.
Aclaraciones
- Puede representar un conjunto como una lista si lo desea (o lo que sea apropiado para su idioma), sin tener en cuenta el orden de los elementos.
- No tiene que manejar el caso donde no existe una solución (es decir, siempre habrá al menos una solución).
- Puede haber más de una solución. Su algoritmo siempre debe producir una solución válida, pero puede ser no determinista (es decir, está bien si elige una solución válida diferente cada vez que se ejecuta).
- El número de enteros distintos que aparecen en la entrada, n , será igual al número de conjuntos en la entrada, y por simplicidad, serán los enteros de 1 a n inclusive (ya que sus valores reales no importan). Depende de usted si desea explotar este hecho o no.
Casos de prueba
[{1,2},{1,3},{1,4},{3,4}] -> [2,3,1,4] or [2,1,4,3]
[{1,3},{1,2,4},{2,3},{3},{2,3,4,5}] -> [1,4,2,3,5]
[{1,3,4},{2,3,5},{1,2},{4,5},{4,5}] -> [1,3,2,4,5] or [3,2,1,4,5] or [1,3,2,5,4] or [3,2,1,5,4]
Condición de victoria
Un programa requiere una complejidad de tiempo óptima para ganar, es decir, si se encuentra un algoritmo con una complejidad de tiempo mejor, descalifica todas las entradas más lentas. (Puede suponer que los componentes internos de su idioma se ejecutan lo más rápido posible, por ejemplo, puede suponer que un componente interno de clasificación se ejecuta en el tiempo O (n log n). Del mismo modo, suponga que todos los enteros de tamaño comparable a n pueden agregarse, multiplicarse, etc. . en tiempo constante.)
Debido a que una complejidad de tiempo óptima es bastante fácil de obtener en la mayoría de los idiomas, el ganador será el programa más corto entre aquellos con la complejidad de tiempo ganadora, medida en bytes.
fuente
Respuestas:
Jalea , 8 bytes
Pruébalo en línea!
Explicación
Extremadamente ineficiente. Asintótico a
ϴ(n^(n+1))
según Misha Lavrov; Creo que esta bien.fuente
unique
función @HyperNeutrino en la verificación deO(n)
contención de uso de Jelly (x in s
), cada uno debe tomar deO(n)
acuerdo con esta página , por lo queQ
debe tomar laO(n^2)
peor complejidad de tiempo / caso promedio. Por lo tanto, el algoritmo esO(n^(n+2))
. (único puede serO(n)
en caso de que todos los elementos son iguales, donde cada uno de carreras de verificación de contención enO(1)
) --- En una nota sin relación, es posible poner en prácticaunique
enO(n)
el uso de Python incorporadaset
estructura de datos que es de hash-set. De todos modos, Jelly no está diseñada para ser eficiente.Wolfram Language (Mathematica) , 87 bytes y ϴ (n 3 )
Pruébalo en línea!
Construye un gráfico bipartito cuyos vértices en un lado son los conjuntos (indexados por
-1,-2,...,-n
) y cuyos vértices en el otro lado son los elementos1,2,...,n
, con un borde de-i
aj
cuandoj
está contenido en eli
conjunto -ésima. Encuentra una coincidencia perfecta en este gráfico utilizando un incorporado. Luego enumera los elementos correspondientes-1,-2,...,-n
en ese orden en la combinación perfecta.Mathematica
FindIndependentEdgeSet
es el cuello de botella aquí; todo lo demás requiere operaciones O (n 2 ) para hacer. Mathematica probablemente usa el algoritmo húngaro , por lo que supongo que se ejecuta en el tiempo ϴ (n 3 ) , aunque es posible que Mathematica tenga una implementación ingenua con complejidad O (n 4 ).fuente
Haskell , 48 bytes
-1 byte gracias a nimi.
Pruébalo en línea!
fuente
mapM id
en lugar desequence
Mathematica 39 Bytes
Sobre el tema de la complejidad, creo que depende mucho de la longitud de cada sublista, así como también de la medida de la desunión de las sublistas.
Entonces, creo que este algoritmo es O (n Log n + n ^ 2 Log m) donde m es aproximadamente la longitud promedio de cada sublista.
Algo como esto tendría una complejidad O (a ^ n) donde a> 1 es una medida de la superposición en las sublistas:
Es difícil decir cuál es realmente más rápido sin conocer las propiedades de las posibles entradas.
fuente
DeleteDuplicates /@ Tuples@#
paso lleva tiempo ϴ (n ^ (n + 1)) por los mismos argumentos que en las otras soluciones. LuegoUnion
tiene una lista de longitud n ^ n para ordenar, que toma O (n ^ (n + 1) log (n)) tiempo, ¡pero tal vez sea más rápido ya que a lo sumo 2 ^ nn! los elementos en esa lista son distintos. De cualquier manera, la complejidad es ϴ (n ^ (n + 1)) hasta un factor log (n).Tuples@#
tiene un tamaño 2 ^ n, por lo que su primera estimación asintótica no puede ser cierta.05AB1E , 13 bytes, O (n! * N)
Pruébalo en línea! Explicación:
fuente
Casco , 5 bytes
Pruébalo en línea!
Explicación
Acabo de ver el tema de la complejidad: como suele ser el caso con la solución de idiomas de golf, no son muy eficientes; este tiene la complejidad O (n · nⁿ).
fuente
Pyth , 9 bytes (ϴ (n n + 1 ))
Dado que esto funciona exactamente como la solución Jelly, lo más probable es que tenga la misma complejidad.
Pruébalo aquí!
¿Cómo?
fuente
JavaScript (ES6),
7473 bytes1 byte guardado, gracias a @Neil.
Recurre iterativamente a través de la matriz buscando una solución.
Sin golf:
Casos de prueba:
Mostrar fragmento de código
fuente
a?a.map(
...)&&S:s
?Python3,
9384 bytes-9 bytes gracias a caird coinheringaahing
Pruébalo en línea!
fuente