Hacer conjuntos disjuntos sin vaciarlos

8

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.

Fred Russell
fuente
Si no tiene sentido, ¿por qué es que lo entendieron aquí dreamincode.net/forums/topic/…
fred russell
@fredrussell tal vez, solo tal vez, se trata de cómo lo explicas, y no de, por ejemplo, la notación en la imagen.
NieDzejkob
77
@fredrussell su explicación del "desafío" no está clara y no está formateada. En este sitio, generalmente encontrará preguntas ordenadas y con el formato adecuado, por ejemplo, siguiendo un diseño como "Entrada; Salida; Reglas; Casos de prueba", pero no proporciona nada de eso. Además, no tiene un criterio ganador que pueda determinar un ganador. Y después de su insulto, no creo que nadie esté dispuesto a resolver la pregunta ahora. Incluso en SO, siempre debe tener en cuenta que las personas que responden están haciendo esto en su tiempo libre, por lo que no debe ser grosero de esa manera.
Luca H
1
El código más rápido de @Arnauld implicaría que si ambos escribimos algoritmos O (n), pero el suyo es 100 veces más rápido, entonces usted gana. Si solo requerimos una complejidad de tiempo óptima, entonces está bien si mi código es 100 veces más lento, siempre que sea un byte más pequeño. Pero este desafío bien podría contar como el algoritmo más rápido .
Misha Lavrov
2
Este es exactamente el problema de encontrar una coincidencia completa en un gráfico bipartito. Las complejidades de tiempo de los algoritmos más conocidos dependen de qué tan grandes se comparen los conjuntos con el número de conjuntos. Desafío relacionado.
Zgarb

Respuestas:

2

Jalea , 8 bytes

Œp⁼Q$ÐfḢ

Pruébalo en línea!

Explicación

Œp⁼Q$ÐfḢ  Main Link
Œp        Cartesian Product of the elements; all possible lists
     Ðf   Filter; keep elements that are
  ⁼Q$     Equal to themselves uniquified
      Ḣ   Take the first one

Extremadamente ineficiente. Asintótico a ϴ(n^(n+1))según Misha Lavrov; Creo que esta bien.

Hiperneutrino
fuente
Creo que esto es al menos Ω (n ^ n): el tamaño máximo posible del producto cartesiano.
Misha Lavrov
Más precisamente, ϴ (n ^ (n + 1)), ya que la verificación "igual a sí mismo no especificado" debe ser el tiempo ϴ (n).
Misha Lavrov
@MishaLavrov Ah, bien, gracias.
HyperNeutrino
La uniquefunción @HyperNeutrino en la verificación de O(n)contención de uso de Jelly ( x in s), cada uno debe tomar de O(n)acuerdo con esta página , por lo que Qdebe tomar la O(n^2)peor complejidad de tiempo / caso promedio. Por lo tanto, el algoritmo es O(n^(n+2)). (único puede ser O(n)en caso de que todos los elementos son iguales, donde cada uno de carreras de verificación de contención en O(1)) --- En una nota sin relación, es posible poner en práctica uniqueen O(n)el uso de Python incorporada setestructura de datos que es de hash-set. De todos modos, Jelly no está diseñada para ser eficiente.
usuario202729
2

Wolfram Language (Mathematica) , 87 bytes y ϴ (n 3 )

-Range[n=Length@#]/.Rule@@@FindIndependentEdgeSet[Join@@Table[-i->j,{i,n},{j,#[[i]]}]]&

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 elementos 1,2,...,n, con un borde de -ia jcuando jestá contenido en el iconjunto -ésima. Encuentra una coincidencia perfecta en este gráfico utilizando un incorporado. Luego enumera los elementos correspondientes -1,-2,...,-nen ese orden en la combinación perfecta.

Mathematica FindIndependentEdgeSetes 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 ).

Misha Lavrov
fuente
Bueno ... Mathematica es malo en la complejidad restringida , no por primera vez.
usuario202729
2

Haskell , 48 bytes

-1 byte gracias a nimi.

import Data.List
head.filter((==)<*>nub).mapM id

Pruébalo en línea!

totalmente humano
fuente
2
mapM iden lugar desequence
nimi
1

Mathematica 39 Bytes

Last@Union[DeleteDuplicates/@Tuples@#]&

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:

(For[x={1,1},!DuplicateFreeQ@x,x=RandomChoice/@#];x)&

Es difícil decir cuál es realmente más rápido sin conocer las propiedades de las posibles entradas.

Kelly Lowder
fuente
2
El DeleteDuplicates /@ Tuples@#paso lleva tiempo ϴ (n ^ (n + 1)) por los mismos argumentos que en las otras soluciones. Luego Uniontiene 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).
Misha Lavrov
Creo que este problema requiere una definición multivariada de notación O grande para tener algún significado práctico. Obviamente, la longitud de las sublistas es increíblemente importante.
Kelly Lowder
1
Mi interpretación del enunciado del problema es que solo importa la dependencia de n (el número de sublistas), y asumimos el peor de los casos sobre la longitud de las sublistas. En cualquier caso, incluso si cada sublista tiene una longitud 2, Tuples@#tiene un tamaño 2 ^ n, por lo que su primera estimación asintótica no puede ser cierta.
Misha Lavrov
¿Eh? ¿Por qué es problemático BigO multivariante? Se hace todo el tiempo.
usuario202729
1

05AB1E , 13 bytes, O (n! * N)

āœʒ‚øε`QO}P}н

Pruébalo en línea! Explicación:

ā               Make a range 1..n
 œ              Generate all permutations
  ʒ        }    Filter
   ‚ø           Zip with input
     ε   }      Loop over sets
      `QO       Check each element for membership
          P     All sets must match
            н   Take the first result
Neil
fuente
1

Casco , 5 bytes

►oLuΠ

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ⁿ).

►(Lu)Π  -- input as a list of lists, for example: [[1,2],[1,3],[1,4],[3,4]]
     Π  -- cartesian product: [[1,1,1,3],...,[2,3,4,4]]
►(  )   -- maximum by the following function (eg. on [1,1,1,3]):
   u    --   deduplicate: [1,3]
  L     --   length: 2
ბიმო
fuente
0

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.

h{I#.nM*F

Pruébalo aquí!

¿Cómo?

h {I # .nM * F | Programa completo

       * F | Doblar el producto cartesiano.
    .nM | Aplane cada uno.
   # | Guarde esos:
 {I Eso es invariante sobre la eliminación de elementos duplicados.
h | Toma el primer elemento.
Sr. Xcoder
fuente
0

JavaScript (ES6), 74 73 bytes

1 byte guardado, gracias a @Neil.

f=([a,...A],s=[],S)=>a?a.map(c=>s.includes(c)||(S=S||f(A,[...s,c])))&&S:s

Recurre iterativamente a través de la matriz buscando una solución.

Sin golf:

f=(
   [a, ...A],                        //a is the first array, A is the rest
   s = [],                           //s is the current trial solution
   S                                 //S holds the solution (if one exists) at this branch
  )=>
     a ? a.map(                      //if we're not done, iterate through a
           c => s.includes(c) ||     //  if this element already exists, short-circuit
                (S = S ||            //  else if S has a solution, keep it
                 f(A, [...s, c])     //  else look for a solution down this branch
                )
         ) && S                      //return S

Casos de prueba:

Rick Hitchcock
fuente
¿Por qué no a?a.map(... )&&S:s?
Neil
@Neil, porque Duh. ¡Gracias!
Rick Hitchcock
0

Python3, 93 84 bytes

-9 bytes gracias a caird coinheringaahing

lambda I:next(filter(lambda x:len(x)==len({*x}),product(*I)))
from itertools import*

Pruébalo en línea!

Setop
fuente
1
84 bytes
caird coinheringaahing