Trovare il numero massimo di numeri congruenti

Question

Trovare il numero massimo di numeri congruenti

#1 da (1 voti)

4

Diciamo che abbiamo un multiset (impostato con possibili duplicati) di numeri interi. Vorremmo trovare la dimensione del sottoinsieme più grande del multiset in modo tale che tutti i numeri nel sottoinsieme siano congruenti tra loro modulo alcuni m > 1.

Ad esempio:
1 4 7 7 8 10

per m = 2 i sottoinsiemi sono: (1, 7, 7) e (4, 8, 10), entrambi con dimensione 3.
per m = 3 i sottoinsiemi sono: (1, 4, 7, 7, 10) e (8), il più ampio set di dimensioni 5.
per m = 4 i sottoinsiemi sono: (1), (4, 8), (7, 7), (10), il più grande set di dimensioni 2.
In questo momento è evidente che la risposta migliore è 5 per m = 3.

Dato m possiamo trovare la dimensione del sottoinsieme più grande in tempo lineare.

Poiché la risposta è sempre uguale o superiore alla metà della dimensione del set, è sufficiente controllare i valori di m upto-median del set.

Inoltre ho notato che è necessario verificare solo i valori primi di m.

Tuttavia, se i valori nell'insieme sono grandi, l'algoritmo è ancora piuttosto lento.

Qualcuno ha qualche idea su come migliorarlo?

algorithms math

posta Stefan Czarnecki 27.05.2013 - 16:02

fonte

1 risposta

Leggi altre domande sui tag algorithms math

Best practice per il calcolo dei dati in applicazioni Web simili a GIS Controllo dei cookie con molte schede

score 1 · Answer 1

Potrebbe esserci un modo per valutare i risultati per diversi valori di m con un solo passaggio attraverso il multiset, possibilmente anche tutti loro, anche se significa derivare un'altra raccolta (si spera piccola) di partizioni da scorrere.

Prendi i primi tre valori di m - come devi considerare solo i numeri primi, ovvero 2, 3 e 5. Il prodotto di questi è 30. Quindi partiziona il multiset in classi di equivalenza modulo 30.

Ora puoi determinare le dimensioni / sottoinsiemi per m=2 , m=3 e m=5 relativamente facilmente. Ogni sottoinsieme m=2 è costituito da ogni altra partizione da quelli 30, ogni sottoinsieme m=3 è costituito da ogni terza partizione e ogni sottoinsieme m=5 è costituito da ogni quinta partizione. Con una serie di 30 partizioni (ad esempio teste di liste collegate) da considerare, è molto meno lavoro rispetto al partizionamento dell'intero multiset iniziale per tre volte. Invece di fare le classificazioni PN, si fa n + pq dove p è il numero di numeri primi per il passaggio (3 qui) e q è il prodotto di quei numeri primi (30 per 2, 3 e 5). Se n è abbastanza grande e q è abbastanza piccolo, questo dovrebbe essere un guadagno netto, ma q cresce rapidamente all'aumentare del numero / della dimensione dei primi.

Man mano che q diventa più grande, può essere possibile ridurre la parte +pq rintracciando quale dei valori del modulo effettivamente si è verificato nel ciclo iniziale - ad es. costruire una lista collegata. Ad essere onesti, però, sospetto che la complessità aggiunta supererebbe qualsiasi guadagno.

Non sono sicuro che ci sia un'idea utile in questo o no - anche se è possibile costruire qualcosa che funzioni, è probabile che un algoritmo più complesso sarà più lento. Ma forse c'è il nucleo di un'idea qui.