Mappatura delle combinazioni di abbinamenti in un numero intero

0

Prima di tutto, voglio dire che non ero sicuro di dover postare questo qui o in math.stackexchange ma io pensa che la domanda sia troppo legata alla programmazione per appartenere a quest'ultima comunità. Sicuramente non una domanda SO, però.

Una breve introduzione del mio programma: sto sviluppando un programmatore per eventi sportivi usando CSP. Ogni evento può avere diverse categorie, ad esempio, in un evento di tennis potresti avere un pareggio maschile, un pareggio femminile e un pareggio doppio. In un torneo di calcio potresti avere il gruppo A, il gruppo B, il gruppo C ... Nell'evento del tennis, però, possiamo avere giocatori che giocano contemporaneamente in diverse categorie. Il mio solver ha questo in mente.

Per uno scopo specifico, devo monitorare quali combinazioni di abbinamenti sono già state provate. Per una "combinazione match-up" comprendiamo una combinazione specifica di match-up predefiniti tra giocatori. Ad esempio, nel torneo di tennis, una combinazione specifica potrebbe essere:

Men's draw -> [Man1, Man6], [Man3, Man5], [Man2, Man4]

Women's draw -> [Woman3, Woman4], [Woman6, Woman2], [Woman1, Woman5]

Double's draw -> [Man6, Woman4, Woman1, Man3], [Man2, Man1, Woman2, Woman5],
   [Man4, Woman3, Woman6, Man5], [Man7, Woman8, Woman7, Man8]

(Penso che non mi sia sfuggita nessuna combinazione, ma spero che tu abbia capito l'idea)

Questa combinazione è creata da un pool di giocatori definiti per ogni categoria che compone il torneo. Quanto segue rappresenta tutti i giocatori che giocano in ciascuna categoria:

Men's draw -> [Man1, Man2, Man3, Man4, Man5, Man6]

Women's draw -> [Woman1, Woman2, Woman3, Woman4, Woman5, Woman6]

Double's draw -> [Man1, Man2, Man3, Man4, Man5, Man6, Woman1, Woman2, 
    Woman3, Woman4, Woman5, Woman6, Man 7, Man8, Woman7, Woman8]

Se il processo di risoluzione non funziona per una combinazione specifica, che è stata generata casualmente, andiamo avanti e proviamo con una combinazione generata casualmente. Ripetiamo finché non troviamo una soluzione.

Ora, tenere traccia delle combinazioni visitate significherebbe un enorme costo nell'utilizzo della memoria, a causa di tutte le informazioni da memorizzare. Dubito che la memoria di un normale PC possa gestire la quantità di combinazioni in un torneo moderatamente grande.

Penso che il modo corretto per farlo sia, invece di memorizzare l'intera combinazione, possiamo memorizzare un numero intero che rappresenta una combinazione unica.

Quindi, ad esempio, la combinazione sopra corrisponde al numero intero 1 , e così via. Potremmo facilmente memorizzare un insieme di numeri interi. E per le prossime combinazioni potremmo controllare l'identificatore della combinazione generata con il contenuto di quell'intervallo impostato per vedere se è già stato visitato.

Tuttavia, non riesco a pensare a un algoritmo che rappresenti una combinazione con un numero intero univoco. Questo potrebbe essere fatto? È più facile da fare di quanto suoni? È una buona idea fare ciò che sto suggerendo?

    
posta dabadaba 04.04.2016 - 15:39
fonte

1 risposta

1

Rappresentare una combinazione di due valori richiede tanti bit quanti rappresentano quei due valori, sommati insieme. Se i tuoi "giocatori" sono rappresentati come interi a 32 bit, puoi averne 2 ^ 32.

Se si debbano memorizzare combinazioni tentate come interi effettivi (facendo uso della rappresentazione bit codificata nel proprio linguaggio di programmazione) o come bit grezzi (se il proprio linguaggio di programmazione ha campi di bit incorporati) dipende da cosa è più efficiente da programmare ed eseguire nel tuo particolare ambiente. In ogni caso, leggi le operazioni bit a bit, in particolare i bit shift, per imparare come memorizzare due valori in un valore più grande.

(Nota che se l' ordine di un match-up non ha importanza - O'Sullivan che gioca a Higgins equivale a Higgins che gioca a O'Sullivan - quindi tecnicamente hai bisogno di un bit in meno, ma è probabilmente non vale la pena inventare uno schema di archiviazione più efficiente in termini di spazio perché è più complicato da implementare.)

    
risposta data 04.04.2016 - 15:47
fonte