Todas las combinaciones válidas de puntos, de la manera más efectiva (velocidad)

Question

Sé que hay bastantes preguntas por ahí sobre la generación de combinaciones de elementos, pero creo que éste tiene un cierto giro para valer una nueva pregunta:

Para un proyecto de mascota, tengo que precomprobar una gran cantidad de estados para mejorar el comportamiento del tiempo de ejecución de la aplicación más adelante. Uno de los pasos con los que lucho es este:

Dadas N tuplas de dos enteros (vamos a llamarlos puntos desde aquí, aunque no están en mi caso de uso. Sin embargo, están relacionados con X/Y) I necesita calcular todas las combinaciones válidas para una regla dada.

La regla podría ser algo así como

• "Cada punto incluido excluye todos los demás puntos con la misma coordenada X"
• "Todos los puntos incluidos excluye todos los demás puntos con una X extraña coordenada"

Espero y espero que este hecho conduzca a una mejora en el proceso de selección, pero mis habilidades matemáticas se resucitan a medida que escribo y no puedo encontrar un algoritmo elegante.

• El conjunto de puntos (N) comienza pequeña, pero crece más 64 pronto (para la "utilización siempre y cuando máscara de bits" soluciones)
• que estoy haciendo esto en C#, pero las soluciones en cualquier idioma debe estar bien si explica la idea subyacente

Gracias.

---

actualización en respuesta a la respuesta de Vlad:

Tal vez mi idea de generalizar la cuestión era una mala. Mis reglas anteriores fueron inventadas sobre la marcha y solo marcadores de posición. Una regla realista se vería así:

• "Todos los puntos incluidos excluye cualquier otro punto en el triagle por encima del punto elegido"

Por esa regla y por la elección (2,1) que había excluir

• (2,2) - directamente por encima de
• (1,3) (2,3) (3,3) - línea siguiente
• y así sucesivamente

Entonces las reglas son fijas, no generales. Desafortunadamente son más complejas que las muestras X/Y que di inicialmente.

Answer 1

Para algunos tipos de reglas especiales, su tarea parece ser simple. Por ejemplo, por su ejemplo la regla # 1 tiene que elegir un subconjunto de todos los valores posibles de X, y que para cada valor del subconjunto asigna una Y. arbitraria

para reglas genéricas Dudo que es posible construir un algoritmo eficiente sin ningún AI.

Answer 2

Mi comprensión del problema es: dado un método bool property(Point x) const, encuentre todos los puntos del conjunto para el cual la propiedad() es true. Es eso razonable?

El enfoque de fuerza bruta consiste en ejecutar todos los puntos a través de property(), y almacenar los que devuelvan verdadero. La complejidad temporal de esto sería O(N) donde (a) N es el número total de puntos, y (b) el método property() es O(1). Supongo que estás buscando mejoras en O(N). ¿Está bien?

Para cierto tipo de propiedades, es posible mejorar a partir de O(N), siempre que se utilice una estructura de datos adecuada para almacenar los puntos y se realice una precomputación adecuada (por ejemplo, clasificación). Sin embargo, esto puede no ser cierto para cualquier propiedad arbitraria.

Answer 3

¿Qué tal "la coordenada x de cada punto incluido es la suma exacta de algún subconjunto de las coordenadas y de los otros puntos incluidos". Si puedes encontrar un algoritmo rápido para ese problema de restricción simplemente declarado, entonces serás muy famoso.

Mi punto es que el problema es tan vago como para admitir problemas NP-completos o NP-duros. Los problemas de optimización de restricción son increíblemente difíciles; si no puede establecer límites extremadamente estrechos sobre el problema, rápidamente las máquinas no lo pueden analizar en tiempo polinomial.