Håller på med ett program som ska para ihop kamrater så att alla kamrater ska få välja 3 stycken som de kan tänkas vara med. Sedan ska programett para ihop så många par som möjligt där båda valt varandra.
Jag har gått och klurat på det i några dagar men inte hittat någon lösning.

Det är skapat i excel och använder sig av makron i VB.

Jag har kommit så långt att den kollar vilka som kan tänkas vara med varje person och på vilket av alternativen (se bifogad fil). Problemet är att jag inte kan komma på något sätt att kolla hur många par som går att göra. Jag kan köra igen uppifrån och ner men då kommer det inte att bli så många som möjligt.

www.ploxit.com/Kompisar.xls

Testa att köra det befintliga makrot och se vad som händer. Sedan kommer problemet hu ska man med så lite kod som möjligt fixa så att det blir så många par som möjligt?

Tacksam för hjälp!

Det du i princip behöver göra är en uttömmande sökning. Låt säga att du har Arne, Bengt, Calle och David.
Sen så representerar du hela par-strukturen genom att skriva alla personer i rad, men de två första är ett par, de två andra är ett, osv.

Då har du först
ABCD, dvs Arne med Bengt och Calle med David.

Sen får du göra nästa försök
(ABDC, samma som första)

ACBD
(ACDB)

ADBC
(ADCB)

Sen får du ge varje kombination ett värde utifrån hur bra det är, och till sist välja det bästa.
Du kan stryka typ hälften av alla kombinationer, men du får ändå ett ganska rejält problem. Skulle väl tro att det är NP-komplett.

Detta är det riktiga sättet att lösa problemet på, alla andra sätt ger approximationer.

Om du bara är intresserad av paren som är "bra", så skulle en bra heuristisk metod kunna vara något i stil med:
1. Börja med en person P.
2. Gå igenom den personens kompisar, "asigna" en av dem (som inte är upptagen) i sänder till personen.
3. Ta en ny person av de som är kvar, och upprepa från 2.

Alltså:
A gillar B, C och D
B gillar A, C och E
C gillar A, B och E
...

Börja med A. Testa med B, A gillar B och B gillar A. Välj en ny - C. C gillar A, B och E, men A och B är upptagna, testa alltså med E, osv.

Hej,

Jag skulle nog göra så att jag poängsätter varje person.

Om person A gillar person B, E och F så skulle dessa få vars en poäng från A osv. På så sätt får man fram vem som är mest och minst populär och därmed lätthet att kombinera.

Nästa steg skulle vara att börja med lägsta poängen först eftersom de är svårast att placera och sedan avsluta med de högsta poängen.

Om det nu visar sig att det inte går att lösa så att alla paras ihop med någon som de aktivt gillar så är det ändå så att det är de mest populära personerna kvar på slutet och borde sannolikt ändå vara lätta att placera eftersom de troligtvis skulle hamna som nästan favoriter hos de andra som är kvar.

// Johan

Tack så hemskt mycket för hjälpen. Den som niklas skrev är den som jag också tänkte på först men kom fram till att den inte fixade så många par som möjligt utan körde dom bara i en lista uppifrån och ner.
Om jag har uppfattat vad du menar korrekt.

Johans har jag dock inte testa så jag ska sätta mig och testa om det fungerar bra.

Men tack för hjälpen!

/Patrick

<b>>utan körde dom bara i en lista uppifrån och ner.
Om jag har uppfattat vad du menar korrekt.</b>

Njae... Jag tänker något i stil med att du testar alla möjliga kompis-kombinationer.

Sen är det inte helt specificerat heller.
Det finns tre sorters par:
1. Båda gillar varandra
2. Bara ena gillar den andra
3. Ingen gillar den andra

Vilka av dessa anser du vara "bra par"?

Mitt mål är att sätta upp par där båda gillar varandra, om det är någon som ingen annan gillar så struntar vi i honom, men jag tror att jag vet hur jag ska fixa det nu men jag återkommer om det skulle bli några problem.

Men tack för hjälpen iaf

/Patrick