Jag skulle behöva lite input till ett problem: Nej, du ska kolla på kombinatorik; Intressant ämne. Tänker testa ditt problem. Igen. Testade VB programmet. Fråga okunskap. Det är alltså 7 personer som testar 3 maträtter var => 21 olika kombinationer (det kunden kallar "Serveringsordning") skall genereras. Jag skulle nog lösa det så här: Ja, det kan finnas fler kombinationer av mat än människor. Ibland kan det bli så att det är 5 personer som skall testa 10 maträtter..... Får se om jag tänker rätt. 3-7 Ja, alla personer skall testa alla maträtter - fast i olika ordning och varje enskild maträtt skall serveras lika många gånger (i så stor utsträckning som möjligt) som 1:a rätt, 2:a rätt osv... Ett sätt att få en skaplig fördelning över maträttsordning till varje person är att, Det här är inte alls något dumt förslag. Det enda som jag invänder är att det inte riktigt blir den jämna fördelning som kunden är ute efter: Kan man inte bara göra en klassisk förskjutningsmodell men med ändring av inbördes ordning mellan varje varv? Kenneth, Nope. Det här var det första alternativet jag levererade till kunden och den ratades fortare än jag kunde säga "Häpp!". De vill INTE att serveringsordningen skall vara identisk med endast en förskjuten startordning. Det måste vara viss mått av "slump" i det hela. Intressant. Jag skall definitivt testa. Slumpa ordningen de läggs ut på personer i slutändan? Jag vidhåller; det bästa alternativet är nog i det här fallet en enkel slumpning med kontroll istället. Ta startordningen, gör en slumpartad permutation, tilldela. När alla personer är tilldelade så kollar du ett antal variabler så att ordningen blir ok, jag skulle nog kolla på fördelningen av maträtt X på plats Y, och kolla standardavvikelsen för det. Skulle nog börja i andra änden. Kenneth, Riktigt trevligt resultat!Ett litet matematiskt problem... Generera en unik tabell...
Jag behöver generera en lista/tabell med samtliga möjliga kombinationer... Låt mig förklara närmare.
Om en kund har t.ex. 3 maträtter som skall provas och det är t.ex. 7 personer som testar, då skall serveringsordningen på dessa maträtter vara så unik som möjligt på samtliga personer. Eftersom det är 3 maträtter så kommer det att finnas 3!=6 olika kombinationer. 4 maträtter ger 4!=24 olika kombinationer osv... Om antalet kombinationer är mindre än antalet testpersoner så tar man och börjar om från början igen, vilket betyder att i det första fallet kommer 2 personer ha samma sorteringsordning medans övriga 5 har unika.
Hur löser jag detta programmatiskt? Just nu känns mina tankegångar blockerade och jag ser ingen väg ut. Hoppas på lite hjälp.
[Edit:] Jag kom på att det hela liknar ju faktiskt någon slags sudoku-tabell... Fast med valfritt antal siffror... Skall söka lite på det och se vad jag hittar!Sv: Ett litet matematiskt problem... Generera en unik tabell...
http://www.google.se/search?q=find+all+combinations+codeSv:Ett litet matematiskt problem... Generera en unik tabell...
Hittade detta VB anpassade.
http://www.planet-source-code.com/vb/scripts/ShowCode.asp?txtCodeId=62471&lngWId=1Sv: Ett litet matematiskt problem... Generera en unik tabell...
Citat:
<b>Om en kund har t.ex. 3 maträtter som skall provas och det är t.ex. 7 personer som testar</b>
Vilket är vilket ?
Things Taken
Possible Combinations fick 210 - 35 är det rätt ? på 3 - 7
Som jag då ser det skulle man kunna köra en Randomize Loop Until alla 210 kombinationerna är uppfyllda. Eller skall det vara tvärtom ?Sv:Ett litet matematiskt problem... Generera en unik tabell...
Om det är 10 personer som testar 8 maträtter så blir det => 80 olika kombinationer/serveringsordningar.
Jag börjar få till det där nu, men har stött på nästa problem. Nu har kunden ändrat kravspecen igen (*suck*) och lagt till att varje enskild maträtt skall vara jämt fördelad på varje enskild serveringsomgång.
Det betyder att maträtt A skall serveras som 1:a ungefär lika många gånger som maträtt B och C osv...
Hur löser man den problematiken? All permutationskod jag hittat genererar ju väldigt likadana sekvenser och således inte en jämn fördelning på de olika varianterna.Sv: Ett litet matematiskt problem... Generera en unik tabell...
1. Finns det fler kombinationer mat (N) än människor (n)?
om nej;
ta fram varje möjlig kombination, dela ut dem proportionerligt (n/N av varje "serveringsordning") .
om ja;
få tag i en kod där du kan skicka in en indikator på _vilken_ kombination du ska ha, och dela upp detta jämnt över alla (alltså anropa med N/n, 2*N/n, osv.)
Tyvärr är det ingen speciellt säker metod.
Det jag gissar skulle kunna funka är helt enkelt att köra en random sortering mellan varje.
Alltså:
1. Ta en lista {1, 2, 3, ... k}.
2. Blanda den slumpartat.
3. Ge den till första personen.
4. Upprepa.
I värsta fall kan du helt enkelt kolla fördelningen efteråt så att det inte blir för dåligt, och i så fall slumpa om. Jag tror faktiskt du får mest framgång med den här iden. (Men blanda smart!)Sv:Ett litet matematiskt problem... Generera en unik tabell...
Jag är definitivt inne på att helt enkelt slumpmässigt generera en unik serveringsordning som jag tilldelar respektive person och i efterhand kontrollerar fördelningen. Det verkar enklast just nu. Sv: Ett litet matematiskt problem... Generera en unik tabell...
Då kan det bli så att två kunder testar samma rätt. Men det får inte bli så att tre gör det ?
Eller är jag ute och cyklar !?
Edit:
Efter att tänkt ett tag till så skall det nog vara så att alla 7 kunderna någon gång testat 1 2 och 3. Eller ?
Random lösning är nog det effektivaste.Sv:Ett litet matematiskt problem... Generera en unik tabell...
Exempel:
Vi har Fyra maträtter som skall testas: Apelsin (A) , Banan (B), Citron (C) och Dadlar (D). Dessa fyra maträtter skall testas av Fyra personer: Adam, Bertil, Ceasar och David. Då skulle det bli en serveringsordning enligt följande:
Adam: A, B, C, D
Bertil: B, D, A, C
Ceasar:D, C, B, A
David: C, A, D, B
Varje person har då serverats alla rätter och i olika ordning och alla rätter har då förekommit lika många gånger på plats 1, 2, 3 och 4...
Det är ju inget svårt när det är så här få varianter. Problemet är när vi pratar 8, 9 eller 10 maträtter och 30 personer.......Sv: Ett litet matematiskt problem... Generera en unik tabell...
Skapa en array P med de personer som ska ingå, t ex 6 st
P(0) = A till P(5) = F
Skapa en sorterad array (t ex SortedList) M med alla matkombinationer (permutation), kom ihåg att med fakulteten blir det snabbt väldigt många alternativ.
T ex 4 maträtter ger 24 kombinationer (4!), från M(0) = 1234 till M(23) = 4321.
För att sedan sprida kombinationerna så bra som möjligt så räknar man fram matindex för varje person.
Mindex = int(Pindex / Pantal) * (Mantal-1)
eller
Mindex = int(Pindex / Pantal) * UBound(M)
(anledningen till att jag använder Pantal och inte UBound(P) ovan är att jag på så sett får en förskjutning i listan och verkar slippa upprepad matordning så lång som möjligt, t ex 1234 och 4123, där ordnigen 123 förekommer i bägge.)
Kör en loop för alla personer.
<code>
For Pindex = 0 TO UBound(P)
{
int Mindex = int(Pindex / UBound(P)) * UBound(M)
Debug.Print "Person " & P(Pindex) & " ska äta " & M(Mindex)
}
</code>
En permutation av fyra maträtter kan se ut så här
M(0) = 1234
M(1) = 1243
M(2) = 1324
M(3) = 1342
M(4) = 1423
M(5) = 1432
M(6) = 2134
M(7) = 2143
M(8) = 2314
M(9) = 2341
M(10)= 2413
M(11)= 2431
M(12)= 3124
M(13)= 3142
M(14)= 3214
M(15)= 3241
M(16)= 3412
M(17)= 3421
M(18)= 4123
M(19)= 4132
M(20)= 4213
M(21)= 4231
M(22)= 4312
M(23)= 4321
Det innebär att
P(0) äter int(0/6)*23 = 0: M(0) = 1234
P(1) äter int(1/6)*23 = 3: M(3) = 1342
P(2) äter int(2/6)*23 = 7: M(7) = 2143
P(3) äter int(3/6)*23 = 11: M(11)= 2431
P(4) äter int(4/6)*23 = 15: M(15)= 3241
P(5) äter int(5/6)*23 = 19: M(19)= 4132
Det är väl inte en perfekt metod och det finns säker flera invändningar mot den men det är ju i alla fall ett förslag till lösningSv:Ett litet matematiskt problem... Generera en unik tabell...
Tar du en titt på din lista så upptäcker du att maträtt '1' inte finns listad på plats 3 hos en enda person, och det kommer kunden definitvt att anmärka på.
Nästa problem som dyker upp är som du säger; Fakulteten på 11 maträtter blir några miljoner olika kombinationer och då riskerar programmet att ta grymt lång tid och jag är tveksam till om en array kan vara flera miljoner element...!
Nå, jag skall ta det här förslaget och jobba vidare på det! Tack!Sv: Ett litet matematiskt problem... Generera en unik tabell...
tex
pers 1: 1, 2, 3, 4
pers 2: 2, 3, 4, 1
pers 3: 3, 4, 1, 2
pers 3: 4, 1, 2, 3
--- Byt ordning ---
pers 5: 3, 2, 4, 1
pers 6: 2, 4, 1, 3
Pers 7: 4, 1, 3, 2
osv
Genom att hålla ordning på ursprungsordningarna och hålla koll på att de aldrig dyker upp igen på nåt vis så bör det väl fungera tycker jag.
/P-ESv: Ett litet matematiskt problem... Generera en unik tabell...
angående
"Tar du en titt på din lista så upptäcker du att maträtt '1' inte finns listad på plats 3 hos en enda person, och det kommer kunden definitvt att anmärka på."
i listan med permutationer såförekommer ju maträtt 1 på 3:e plats ett antal gånger sen om den dyker upp som 3:e rätt vid en matprovning beror ju på hur många personer det är som ska prova maten. Är det t ex 2 personer som ska prova 4 rätter så kan ju bara två av rätterna bli den 3:e som provas, liksom om det är 8 personer som ska prova 3 rätter så kommer ju några att ha exakt samma maträttsordning eftersom det bara finns 6 olika kombinationer för 3 rätter (3!).
Ett sätt att slippa en stor array är ju att först beräkna vilket index i permutaionslistan som gäller för respektive person, loopa igenom personerna och för varje person låter man permutationsprogrammet snurra utan att spara det i en array tills permutationsordningsnummret är de samma önskas fö aktuell person.
<code>
permutauionNr = -1;
permutationMax = Fakultet(antalrätter);
permutation; //kombination av maträtter.
For (personIdx = 0 to antalPersoner -1)
{
personMatIdx = int(personIdx / antalPersoner) * UBound(M);
While(permutationNr < permutationMax)
{
permutationNr++;
permutation = getNextPermutation();
if(personMatIdx != permutationNr)
{
person(personIdx).Maträtter = permutation;
Exit While
}
}
}
Next personIdx
</code>
Det blir ju fortfarande en massa permutationer vid många maträtter men de får väl äta mindre istället.
Sv:Ett litet matematiskt problem... Generera en unik tabell...
Sv:Ett litet matematiskt problem... Generera en unik tabell...
Sv: Ett litet matematiskt problem... Generera en unik tabell...
Slumpa startordningen på varje "grupp"?
På så vis kan du ju alltid lätt ha koll på att alla rätter kommer till alla personer etc
/P-ESv:Ett litet matematiskt problem... Generera en unik tabell...
Blir det för stort så försöker man en gång till.Sv: Ett litet matematiskt problem... Generera en unik tabell...
Slumpa ut maträtterna var för sig på personerna. Dvs slumpa ut maträtt 1 som första rätt på trettio personer. Hur många som får/ska maträtt 1 på position 1 beror ju på hur många maträtter. Det avgörs proportionerligt.
Därefter skulle jag göra samma sak med resterande maträtter.
Dvs koordinater: 2:2, 3:3 osv.
Sedan skulle jag slumpa på i de luckor som är kvar med kontroll för om kombinationen tidigare finns, alternativt hur många gånger den får finnas.
Inte testat och kan vara tankevurpa men jag skulle börja försöken i den änden.
//Ann
[edit 2008-05-19 12:50:50]
Skulle börja kontrollen redan vid slumpningen av koordinat 2:2 så att inte för många får 1,2 X X X X, om det bör vara ex max 3 med den kombinationen blir det nästa person som då har 0,2 i stället.
[/edit]Sv: Ett litet matematiskt problem... Generera en unik tabell...
Jag satt och funderade och testade lite ang ditt problem. Det som jag funderade på förut angående att räkna fram ett index från alla permutationer medförde i vissa fall att fördelningen inte belv särskilt bra.
Jag har dock gjort en annan lösning som du får här, hoppas koden är förklarande nog i sig själv.
Jag har t ex provat med 20 personer och 20 maträtter med en exekveringstid lång under sekunden och med i mitt tycke bra fördelning på rätterna.
Först en matprovs klass
<code>
public class Matprov
{
public void MatProv() { }
public string Person;
public List<String> Matlista;
}
</code>
Sedan en metod för att testa funktionen.
<code>
public void Test2MatPerPerson()
{
const int AntalPersoner = 7;
const int AntalMatratter = 11;
Random randObj = new Random();
//Initiera listan med maträtter
List<string> matratter = new List<string>();
for (int i = 1; i <= AntalMatratter; i++)
matratter.Add("Rätt" + i.ToString());
//Initiera listan med personer som ska genomföra matprovning
List<Matprov> prover = new List<Matprov>();
for (int i = 1; i <= AntalPersoner; i++)
{
Matprov prov = new Matprov();
prov.Person = "Person" + i.ToString();
prover.Add(prov);
}
//Bestämm i vilken ordning respektive person ska äta rätterna
long antalKombinationer = fakultet(matratter.Count);
double gruppstorlek = (double)antalKombinationer / (double)(prover.Count);
//Här börjar själva kombineringen av maträtter och personer
//Personerna fördelas jämnt över permutationslistan och inom varje persons
//del slumpas en maträttordning. Det inte är ordningen på maträtterna
//som slumpas utan det är indexet i den sorterade listan permutationer som slumpas.
//På så sätt säkerställs att flera personer inte får samma matordning såvida inte
//antalet personer överstiger antalet möjliga maträttskombinationer.
//Observera att jag inte skapar hela listan med permutationer utan jag skapar rätt
//permutaion "on the fly".
for (int i = 0; i < prover.Count; i++)
{
////Beräkna index för permutationslistan (ingen egentlig lista skapas)
long matIndex = (long)((i * gruppstorlek) + (randObj.NextDouble() * gruppstorlek));
//Hämta matlista för den aktuella personen
prover[i].Matlista = GetPermNoFor(matIndex, matratter);
}
//och här slutar kombineringen av maträtter och personer
//Skriv ut matlista för respektive person.
for (int i = 0; i < prover.Count; i++)
{
string matlista = String.Join(",", prover[i].Matlista.ToArray());
Debug.WriteLine(String.Format("{0} ska äta: {1}", prover[i].Person, matlista));
}
}
</code>
Här är metoden för att hämta önskad permutation
<code>
/// <summary>
/// Skapar den permNo "permutationen" utifrån givna alternativ.
/// Någon permuterad lista i egentlig mening skapas inte utan
/// via den rekursiva metoden byggs den kombination upp som hade haft
/// indexet permNo i en sorterad, permuterad lista utifrån de
/// alternativ komb som angetts. (hoppas ni förstår)
/// </summary>
/// <param name="permNo">anger vilken permutation i ordningen som ska skapas</param>
/// <param name="komb">Lista med de alternativ som finns</param>
/// <returns>En lista med en "permuterad ordning av de alternativ som skickades in.</returns>
public List<string> GetPermNoFor(long permNo, List<string> alternativ)
{
//Antal kombinationer, Fakultet(alternativ.Count)
long antalKomb = fakultet(alternativ.Count);
//Ant kombinationer med samma första alternativ
//Varje möjligt 1:a alternativ skapar en alternativgrupp
long antalKombMedSamma1aSiffra = antalKomb / alternativ.Count;
//Index på den grupp som 1:a alternativet motsvarar
//T ex med 3 olika alternativ.
//grupp 0 = 123,132; grupp 1 = 213, 231; grupp 2 0 312,321.
int alternativGruppIdx = (int)(permNo / antalKombMedSamma1aSiffra);
//Index som den sökta permutationen har inom gruppen
long idxIGruppen = permNo % antalKombMedSamma1aSiffra;
//Kopierar alla alternativ
List<string> altList = new List<string>(alternativ.Count);
altList.AddRange(alternativ);
if (permNo != 0)
{
//Hämta det alternativ som kommer först
string alternativ1 = alternativ[alternativGruppIdx];
//Ta bort det alternativet från listan
altList.RemoveAt(alternativGruppIdx);
if (idxIGruppen != 0)
//Om alternativet inte var först i gruppen anropas metoden
//rekursivt med resterande alternativ.
altList = GetPermNoFor(idxIGruppen, altList); //Rekursivt anrop
//Stoppa in det undansparade 1:a alternativet först i listan
altList.Insert(0, alternativ1);
}
return altList;
}
</code>
Och till sist en enkel metod för att beräkna fakultet (finss effektivare metoder)
<code>
public long fakultet(int n)
{
if (n > 0)
return n * fakultet(n - 1);
else if (n == 0)
return 1;
else
return 0;
}
}
</code>Sv:Ett litet matematiskt problem... Generera en unik tabell...
Tack så mycket för hjälpen allihopa. Jag kommer nog att leverera Jan Bulérs lösning till kunden och se vad de säger.