Tutte le combinazioni valide di punti, nel modo più efficace (velocità)

Question

So che ci sono alcune domande là fuori sulla generazione di combinazioni di elementi, ma penso che questo abbia una certa svolta per meritare una nuova domanda:

Per un progetto per animali da compagnia, devo precalcolare molto stato per migliorare il comportamento di runtime dell'applicazione in un secondo momento. Uno dei passi che faccio è:

Dato N tuple di due numeri interi (chiamiamoli punti da qui in poi, anche se non sono nel mio caso d'uso. Sono approssimativamente X/Y correlati, però) I è necessario calcolare tutte le combinazioni valide per una determinata regola.

La regola potrebbe essere qualcosa di simile

• "Ogni punto incluso esclude ogni altro punto con la stessa coordinata X"
• "Ogni punto incluso esclude ogni altro punto con una X strano punto"

Spero e aspetto che questo fatto porti ad un miglioramento nel processo di selezione, ma le mie abilità matematiche sono appena resuscitate mentre scrivo e non riesco a trovare un algoritmo elegante.

• L'insieme dei punti (N) inizia piccola, ma diventa troppo grande per 64 presto (per la "uso a lungo come maschera di bit" soluzioni)
• sto facendo questo in C#, ma le soluzioni in qualsiasi lingua dovrebbe andare bene se spiega l'idea sottostante

Grazie.

---

Aggiornamento in risposta alla risposta di Vlad:

Forse la mia idea di generalizzare la questione era uno cattivo. Le mie regole sopra sono state inventate al volo e solo segnaposto. Una regola realistica sarebbe simile a questa:

• "Ogni punto incluso esclude ogni altro punto nel triagle al di sopra del punto scelto"

Con questa regola e scegliendo (2,1) che avevo escludere

• (2,2) - direttamente sopra
• (1,3) (2,3) (3,3) - riga successiva
• e così via

Quindi le regole sono fisse, non generali. Sono sfortunatamente più complessi dei campioni X/Y che inizialmente ho dato.

Answer 1

Per alcuni tipi di regole speciali il tuo compito sembra essere semplice. Ad esempio, per il tuo esempio regola # 1 è necessario scegliere un sottoinsieme di tutti i possibili valori di X, e che per ogni valore dal sottoinsieme assegna un Y. arbitraria

Per generici regole Dubito che sia possibile costruire un algoritmo efficiente senza alcuna intelligenza artificiale.

Answer 2

La mia comprensione del problema è: Dato un metodo bool property(Point x) const, trovare tutti i punti il ​​set per cui property() è true. È ragionevole?

L'approccio forza bruta consiste nell'eseguire tutti i punti tramite property() e memorizzare quelli che restituiscono true. La complessità temporale di questo sarebbe O(N) dove (a) N è il numero totale di punti e (b) il metodo property() è O(1). Immagino tu stia cercando miglioramenti da O(N). È giusto?

Per determinati tipi di proprietà, è possibile migliorare da O(N) a condizione che venga utilizzata una struttura dati adeguata per memorizzare i punti e che venga eseguito un precalcolo adeguato (ad esempio l'ordinamento). Tuttavia, questo potrebbe non essere vero per qualsiasi proprietà arbitraria.

Answer 3

Come su "la coordinata x di ogni punto incluso è la somma esatta di qualche sottoinsieme delle coordinate y degli altri punti inclusi". Se riesci a trovare un algoritmo veloce per quel problema di vincolo dichiarato semplicemente, diventerai molto famoso.

Il mio punto è che il problema, come affermato, è così vago da ammettere problemi NP-completi o NP-hard. I problemi di ottimizzazione dei vincoli sono incredibilmente difficile; se non si riesce a porre limiti estremamente stretti al problema, allora molto rapidamente non diventa analizzabile dalle macchine in tempo polinomiale.