Conoscete il nome di questo algoritmo? (ciclo con la storia?)

Question

Conoscete il nome di questo algoritmo? (ciclo con la storia?)

#1 da (1 voti)

0

Contesto : sono uno studente IT che sta tentando di implementare una piccola applicazione per la mia famiglia. Ogni anno ci offriamo regali. Ognuno di noi sceglie un nome di un membro della famiglia in un cappello e deve offrirgli un regalo. Il problema è che abbiamo sempre qualche problema a farlo:

Problema 1: Quando selezioniamo, a volte qualcuno sceglie il proprio nome e dobbiamo ricominciare da capo.

Problema 2: alcune persone offrono per due (o tre) anni consecutivi alla stessa persona

Algoritmo

Sto cercando un modo in cui posso risolvere il problema sopra menzionato. Stavo pensando che il principio è organizzare i punti in un ciclo. Ma considererebbe il suo storico per evitare la ripetizione del modello.

A -> B -> C -> D -> E -> A ...

Voglio evitare che A diventi il diretto figlio di D di nuovo, e B di A ecc. per esempio il prossimo risultato sarà

B -> A -> D -> C  -> E -> B

(nessun punto è il genitore diretto dell'ultimo ciclo)

La terza volta, voglio che A eviti di essere il figlio diretto di E (primo ciclo) e B (secondo ciclo) ecc ...

A -> E -> C -> B -> D -> A

I punti non devono formare un singolo ciclo, purché i problemi descritti sopra non siano garantiti.

algorithms terminology

posta goto 29.12.2015 - 14:48

fonte

1 risposta

Leggi altre domande sui tag algorithms terminology

Design pattern per un generatore di filtri dinamico Modo sicuro per autenticare le credenziali durante la lettura di un file xml dall'esterno

score 1 · Answer 1

In sostanza stai eseguendo una verifica che l'array ricevente che riceve sia un cosiddetto array di Costas (cioè una matrice di valori binari in cui ogni colonna e ogni riga contiene esattamente 1 valore).

Assumendo lo stesso insieme di membri della famiglia anno dopo anno, puoi costruire un array con valori binari (riga = donatore, colonna = ricevitore) delle combinazioni non consentite. Vuoi anche disabilitare la combinazione auto-auto diagonale. L'inversione dell'array ti offre le combinazioni consentite (1 = permesso).

Usando l'array di combinazioni consentite, hai alcune scelte:

Enumera tutti i valori possibili dei bit liberi che definiscono le combinazioni consentite. Controlla se l'array risultante è un array Costas. Se è così, la combinazione è consentita.
Metti in coda i donatori di regali e una singola serie di ricevitori di regali. Per ogni donatore, scegli un ricevitore autorizzato (dalla matrice). Per aiutare questo processo l'ordine dei donatori di regali dovrebbe essere dal più piccolo numero di possibili ricevitori al più grande.

In entrambi gli approcci di cui sopra, potresti scoprire che in realtà non hai una soluzione, nel qual caso vorresti rilassare alcuni dei precedenti criteri (ad esempio, rimuovere il divieto per l'ultimo anno) pur conservando altri (es. qualcuno non può essere dato a se stesso.).