| Autor | Zpráva | ||
|---|---|---|---|
| panterek Profil |
#1 · Zasláno: 3. 6. 2010, 13:52:10
Zdravím,
už 2 dny se patlám s nějakým skriptem na rovnoměrné rozdělování, ale nic mě kurňa nenapadá, tak žádám o pomoc :( Chci rozdělit týmy lidí na nějakou hru, třeba hokej...máme 10lidí a chci je rozdělit 5 na 5. Mám k tomu nějakou hodnotu 1-10, kde hodnota určuje, kdo je jak dobrý (1 špatný, 10 nejlepší)...a chci udělat skript, který mi bude rozdělovat tyto týmy na základě těch dovednostních hodnot Např: Martin - 8 Petr - 6 Ocas - 9 Ichtyl - 6 ....a skript by to měl rozdělit nějak takhle: tým 1: Martin, Petr tým2: Ocas, Ichtyl není ale vždy 10lidí, bude jich třeba 9 nebo 7 a on to musí vypočítat tak, aby to bylo prostě vyrovnané. I přes lichý počet, kde bude logicky v jednom týmu o jednoho víc, tak v tomto týmu musí být hráči o něco horší, než v týmu, kde jich bude víc..K tomuto rozdělení by měly posloužit ty hodnoty..Je možné mít u každého hráče dvoje hodnoty - hlavní bude dovednost (1-10), sekundární může být třeba počet vstřelených gólů, takže při lichém dorozdělování by mohla hrát roli ta sekundární hodnota...ale taky nemusí, to je jedno :) Měl by někdo nějaký nápad? |
||
| _es Profil |
#2 · Zasláno: 3. 6. 2010, 15:35:38
panterek:
Riešenie je jednoduché. Máš celkový počet hráčov n,
k je n/2 zaokrúhlené na celé číslo dole.
Pre každú kombináciu bez opakovania k-tej triedy z n prvkov vyrátaš súčet koeficientov.
Kombináciu, ktorá sa rovná, alebo sa najviac blíži 1/2 celkového súčtu koeficientov použiješ na výber hráčov jedného družstva.
|
||
| panterek Profil |
#3 · Zasláno: 3. 6. 2010, 16:46:27
_es:
No tak to je velká paráda... princip jsem i kupodivu pochopil a moc se mi zamlouvá. Ze školy jsem sice už hodně dlouho, ale nějak to zpatlám dohromady...díky za navedení |
||
| Keeehi Profil |
#4 · Zasláno: 3. 6. 2010, 16:58:11
princip jsem sice nepochopil, ale logickou úvahou jsem dospěl k tomuto: Seřadit je podle výkonnosti a pak 1. a poslední do družstva A, 2. a předposlední do družstva B 3. a předpředposlední do družstva A atd. Nakonec zbyde 0-3 hráči zprostředka, a to už by neměl být takový problém je přiřadit
|
||
| Laman Profil |
#5 · Zasláno: 3. 6. 2010, 17:15:57
Keeehi:
způsobem, co napsal _es, prostě vyzkoušíš všechny možné kombinace (sestavy) a vybereš tu, jejíž součet sil je nejblíž polovině celkového součtu sil. jinými slovy to najde nejlepší možné řešení. dokud nemáš testovaných prvků moc, aby to nešlo rozumně prozkoušet, je to špička :) |
||
| _es Profil |
#6 · Zasláno: 3. 6. 2010, 17:24:29
Keeehi:
„ale logickou úvahou jsem dospěl k tomuto:“ Ak sa nad tou svojou úvahou lepšie zamyslíš, aké ti to dá rozdelenie pre 10, 8, 8, 5, 5, 5, 5, 5?
Prvé družstvo: 10, 8, 5, 5 Druhé družstvo: 8, 5, 5, 5 Podľa môjho návrhu by bolo: Prvé družstvo: 10, 5, 5, 5 Druhé družstvo: 8, 8, 5, 5 |
||
| Keeehi Profil |
#7 · Zasláno: 3. 6. 2010, 17:30:37
Laman:
To jistě, nechtěl bych ale vidět, jak by se to pokoušelo rozdělit třeba všechny lidi v ČR, ale to myslím nehrozí. Takže ta první metoda je jistě lepší. _es: Věděl jsem, že rozhodně není ideání, že při určitých vstupech to nebude vyrovnané, ale zas až tak špatný výsledek by to nebyl. Je to však metoda rychlá a použitelná i tam, kde už by ta tvoje byla velmi časově náročná. |
||
| _es Profil |
#8 · Zasláno: 3. 6. 2010, 17:32:13
Laman:
„dokud nemáš testovaných prvků moc, aby to nešlo rozumně prozkoušet“ Sú to len jednoduché cykly. Ak to bude dobre naprogramované, nie je dôvod, prečo by to malo trvať viac ako okamih. Navyše, môže potom spraviť aj takúto úlohu: Rozdeliť 100 hráčov na 10 družstiev s 10 hráčmi tak, aby boli družstvá čo najviac vyrovnané. |
||
| panterek Profil |
#9 · Zasláno: 3. 6. 2010, 17:36:02
Metoda _es je opravdu supr a chtěl bych jí dosáhnout..už jsem i zjistil, že ten vykřičník u konstant značí faktoriál :)) Ale...mám problém vymyslet funkci, která mi zobrazí nejen počet kombinací, ale konkrétně jaké, abych pak mohl dál pracovat s koeficientama..
|
||
| _es Profil |
#10 · Zasláno: 3. 6. 2010, 17:51:43
panterek:
Neviem v akom programovacom jazyku to chceš robiť, no základný návrh vidím asi takto: V nejakom poli budú uložené koeficienty hráčov. Spravíš si funkciu, nejakú všeobecnejšiu, aby si mohol robiť aj trebárs to rozdelenie na 10 družstiev. Ak dáš rozdelenie na dve družstvá, tak tá funkcia by mala vrátiť v nejakom tvare dve kombinácie. Ak dáš rozdelenie na 10 družstiev, tak tá funkcia by mala vrátiť v nejakom tvare 10 kombinácií. V JavaScripte by som to asi vedel napísať za chvíľu, sú to len jednoduché cykly. |
||
| panterek Profil |
#11 · Zasláno: 3. 6. 2010, 17:57:55
Chci to normálně na web, takže php, javascript...jen teda u sebe to vidím spíš na to php, javascriptu zas moc nehovím...nicméně někdy s tím začít musím..
Nejdřív bych to asi udělal jednoduše, ať se to na tom naučím a pak bych to mohl udělat všeobecně, to zní taky dobře... Do pole jsem si koeficienty dal. Na začátek jsem si dal 6hodnot. Teď, podle nějakého klíče by měl vytvořit ty dvě trojice - ten klíč, tady zatím bádám |
||
| _es Profil |
#12 · Zasláno: 3. 6. 2010, 18:15:12
panterek:
Ešte ma napadol iný algoritmus, vylepšenie niečoho na spôsob Keeehiho popisu. Na začiatku sa podľa nejakého priamočiareho spôsobu rozdelia hráči na požadovaný počet družstiev. A potom sa z družstva do družstva navzájom prehadzujú hráči dovtedy, dokiaľ to nie je maximálne vyrovnané. Takýto algoritmus by sa dal asi tiež spraviť. No nechcem dávať hotové riešenia. Niekedy má človek väčšiu radosť z vlastného riešenia, než len z prevzatia iného kompletného riešenia. |
||
| panterek Profil |
#13 · Zasláno: 3. 6. 2010, 18:22:21
Jasný, to chápu, já se rád učím, takže bych si to chtěl sám i udělat..nicméně bez kopanců se to asi neobejde, tak ještě žádám strpení :) Pojďme se teda bavit o konkrétní věci, k čemu to potřebuju...Hráváme Counter-Strike a pořád bývají dohady, kdo s kým :)) Já vím, je to blbost, ale tohle to kráásně vyřeší...takže řekněme, že máme 6 hráčů, strany v této hře jsou dvě, takže chci 3 hráče na každou stranu...data (jméno, koeficient - nebo-li "skill") tahám z DB...zatím mám něco takového:
$pocet = Mysql_Query ("SELECT jmeno,skill FROM cs WHERE stav1!='' AND jmeno!=''");
$num = Mysql_Num_Rows ($pocet);
for ($i=1; $i<=$num; $i++):
$sql = Mysql_Query ("SELECT jmeno,skill FROM cs WHERE stav1!='' AND jmeno!='' ORDER BY skill DESC LIMIT '$i','3'");
endfor;Cílem by mělo být to, že zjistím počet lidí, kteří budou hrát + jejich skill (koeficient). Cyklus for by měl zajistit výběr 3 lidí, jen ještě musím domyslet tu konstantu $i...takhle by to totiž nešlo. Samozřejmě to nic nedělá, to jen, jestli jdu správným směrem :) |
||
| Laman Profil |
#14 · Zasláno: 3. 6. 2010, 18:38:41
taky si teď lámu hlavu nad výpisem všech možných kombinací... už to skoro mám, jen to ještě přepsat do kódu...
například všechny kombinace 3 prvků ze 6: máš pole o 3 prvcích: (3,2,1), v každém kroku první číslo zvedneš o 1. když přesáhne 6, zvedneš o 1 druhé číslo a první nastavíš na druhé+1. točíš to pořád dokola, když druhé číslo přesáhne 5, zvedneš třetí, druhé=třetí+1, první=druhé+1 a pořád dál. jede to, dokud nemáš pole (6,5,4) |
||
| panterek Profil |
#15 · Zasláno: 3. 6. 2010, 18:42:14
Tak zatím jsem zjistil, že to, co jsem napsal je úplná blbost :))
|
||
| Keeehi Profil |
#16 · Zasláno: 3. 6. 2010, 23:09:42
Takže vyzkoušel jsem obě metody a tady je závěr:
1) Metoda od _es najde vždy nejlepší kombinaci. Nevýhoda je, že při 20ti hráčích (to skoro na fotbal) musí projít 184756 kombinací. To je poměrně náročné. Odhadem při 50ti hráčích se rozdělení nedá stihnout v přijatelném čase. Mojí metodu jsem ještě trochu upravil. 3. místo aby šel do A jde do B a obráceně u 4. Při 12ti hráčích bude v týmu A 1., 4., 5., 8., 9., 12. Pokud jsem testoval můj algoritmus, na 20ti hráčích s ohodnocením 0-10, nepřesáhla odchylka od ideálu (součet všech/2) 4%. Myslím si, že je to slušný výsledek. Nehledě k tomu že 1) Algoritmus je jednodušší, 2) časová náročnost je malá (500000 hráčů zvládá bez obtíží) Můj závěr: _esovou metodou vždy získáme ten nejlepší výsledek, který můžeme dosáhnout. S přibývajícím množstvím prvků (hráčů) je čím dál více náročná na čas. Hodí se proto na malé množiny. Moje metoda není vždy tak přesná, dosahuje však uspokojivých výsledků. Hodí se i pro velké množiny. Z pozorování jsem nabyl dojmu, že jí nejvíce vyhovují velké množiny s malým rozsahem obodování jednotlivých členů. |
||
| _es Profil |
#17 · Zasláno: 3. 6. 2010, 23:54:17
Keeehi:
„S přibývajícím množstvím prvků (hráčů) je čím dál více náročná na čas. Hodí se proto na malé množiny.“ To, že sa dosiahne najlepšia kombinácia alebo kombinácie - pre viac ako dve družstvá, neznamená, že sa museli overiť úplne všetky kombinácie. Napadol ma istý algoritmus, do ktorého je zarátaná aj náhodnosť losovania, lebo pri viac hráčoch je viac pravdepodobné, že bude ideálnych kombinácií, alebo skoro ideálnych kombinácií viac. Ten by mohol byť pre takéto účely užitočný, hlavne to, že nebude isté vylosovanie, no pritom bude možno len skoro "ideálne", čo zvýši atraktivitu vylosovania. Bol by vhodný aj na väčšie množiny aj na viac ako dve družstvá. Ak sa mi bude chcieť, tak ho napíšem v JS a dám sem. |
||
| panterek Profil |
#18 · Zasláno: 4. 6. 2010, 12:33:54
To by bylo supr :) Právě, že těch možnosti rovnoměrného rozdělení může být opravdu víc, což by bylo pro tyto účely to nejlepší ..zatím si zkouším tu úplně první metodu a už jsem se malinko pohnul
|
||
| Laman Profil |
#19 · Zasláno: 4. 6. 2010, 14:48:40
tak se mi to nakonec podařilo sesmolit dohromady (v php). vypadá to funkčně, i když si nedělám iluze o eleganci a čistotě své implementace, za to se omlouvám (a ocením každé vylepšení mého kódu)
<?
function fact($n){ //jen pro výpočet faktoriálu, pro zjištění počtu opakování
if ($n == 0){return 1;}
else{return $n * fact($n - 1);}
}
function rust($p,$pole,$pocet){ //pro přehazování čísel při generování kombinací
if($pole[$p]>$pocet-$p-1){
$pole[$p+1]++;
for($j=$p+1;$j>0;$j--){$pole[$j-1]=$pole[$j]+1;}
$pole=rust($p+1,$pole,$pocet);
}
return $pole;
}
$sily=array();
for($i=0;$i<11;$i++){$sily[$i]=rand(0,9)+rand(0,9);} // jen náhodný vstup pro ukázku
sort($sily);
$ideal=array_sum($sily)/2;
$bestRes=$ideal*2;
$reseni=array();
$pocet=count($sily);
$pole=array();
$pulka=floor($pocet/2);
$celkem=fact($pocet)/fact($pulka)/fact($pocet-$pulka); // počet opakování
for($i=0;$i<$pulka;$i++){$pole[$i]=$pulka-$i-1;}
for($i=0;$i<$celkem;$i++){ //generuje kombinace a zkouší, jak se hodí pro rozdělení
$soucet=0;
foreach($pole as $cislo){$soucet+=$sily[$cislo];}
if(abs($soucet-$ideal)<=abs($bestRes-$ideal)){
$bestRes=$soucet;
$reseni=$pole;
}
$pole[0]++;
$pole=rust(0,$pole,$pocet);
}
$prvniTym=array(); //odsud už v podstatě jen výstup
$druhyTym=array();
for($i=0;$i<$pocet;$i++){
if(array_search($i,$reseni)!==false){array_push($prvniTym,$sily[$i]);}
else{array_push($druhyTym,$sily[$i]);}
}
echo(implode(" + ",$prvniTym)." vs ".implode(" + ",$druhyTym)."<br>\n".array_sum($prvniTym)." vs ".array_sum($druhyTym));
?> |
||
| panterek Profil |
#20 · Zasláno: 4. 6. 2010, 15:01:37
To vážně funguje...kurňa klobouk dolů..už to jen přetvořit k mým účelům, ale to je teda to nejmenší...
A ani se necítím blbě, že jsem to sám neudělal...na tohle bych sám asi vážně nepřišel Moc díky všem..a kdo hrajete Countera, tak se klidně přidejte :)) http://danger.bobinka.eu/cs.php |
||
| panterek Profil |
#21 · Zasláno: 6. 6. 2010, 10:47:29 · Upravil/a: panterek
Kdyby někdo potřeboval, tak tady je kód pro rozdělení týmu od uživatele "Laman", jen jsem ho poupravil na výběr lidí z DB, výpis jejich jmen + součet celkových "skillů" každého týmu. K rozdělení týmu dojde v momentě, až je přihlášeno na zápas více jak 5 lidí... Při výpisu jmen to má ale jednu chybku, výpis dělám dle skillů, takže jakmile budou mít dva lidi stejný "skill", tak to vypíše vždy stejné jedno jméno...než to doupravím to ale takhle stačí. Ještě jednou velký dík za pomoc..
<?
function fact($n){ //jen pro výpočet faktoriálu, pro zjištění počtu opakování
if ($n == 0){return 1;}
else{return $n * fact($n - 1);}
}
function rust($p,$pole,$pocet){ //pro přehazování čísel při generování kombinací
if($pole[$p]>$pocet-$p-1){
$pole[$p+1]++;
for($j=$p+1;$j>0;$j--){$pole[$j-1]=$pole[$j]+1;}
$pole=rust($p+1,$pole,$pocet);
}
return $pole;
}
function rozdeleni() {
include ("config/config.php");
$pole = test();
$test = $pole;
foreach ($test as $val) {
$sily=array();
$sql = Mysql_Query ("SELECT skill FROM cs WHERE $val!='' AND jmeno!='' LIMIT 10");
$num = Mysql_Num_Rows ($sql);
while ($row=mysql_fetch_assoc($sql)) { $sily[]=$row["skill"]; }
if ($val == "stav1") echo "<h3>Pondělí</h3>";
elseif ($val == "stav2") echo "<h3>Středa</h3>";
elseif ($val == "stav3") echo "<h3>Neděle</h3>";
$reseni=array();
$pole=array();
sort($sily);
$ideal=array_sum($sily)/2;
$bestRes=$ideal*2;
$pocet=count($sily);
$pulka=floor($pocet/2);
$celkem=fact($pocet)/fact($pulka)/fact($pocet-$pulka); // počet opakování
for($i=0;$i<$pulka;$i++) { $pole[$i]=$pulka-$i-1; }
for($i=0;$i<$celkem;$i++){ //generuje kombinace a zkouší, jak se hodí pro rozdělení
$soucet=0;
foreach($pole as $cislo) { $soucet+=$sily[$cislo]; }
if(abs($soucet-$ideal)<=abs($bestRes-$ideal)){
$bestRes=$soucet;
$reseni=$pole;
}
$pole[0]++;
$pole=rust(0,$pole,$pocet);
}
$prvniTym=array(); //odsud už v podstatě jen výstup
$druhyTym=array();
$prvniNum=array();
$druhyNum=array();
for($i=0;$i<$pocet;$i++){
if (array_search($i,$reseni)!==false) {
$prvni = $sily[$i];
$sql2 = Mysql_Query ("SELECT jmeno FROM cs WHERE skill='$prvni'");
$res = Mysql_Result($sql2, 0);
array_push($prvniNum,$sily[$i]);
array_push($prvniTym,$res);
}
else {
$druhy = $sily[$i];
$sql3 = Mysql_Query ("SELECT jmeno FROM cs WHERE skill='$druhy'");
$res2 = Mysql_Result($sql3, 0);
array_push($druhyNum,$sily[$i]);
array_push($druhyTym,$res2);
}
}
?>
<table border="0">
<tr style='color: darkblue'>
<?echo "<td>Tým 1 k CT:</td> ";
echo "<td>"; echo (implode(", ",$prvniTym)); echo "</td><td><b> - Skill - "; echo array_sum($prvniNum); echo "</b></td>";?>
</tr>
<tr style='color: darkgreen'>
<?echo "<td>Tým 2 k T:</td>";
echo "<td>"; echo (implode(", ",$druhyTym)); echo "</td><td><b> - Skill - "; echo array_sum($druhyNum); echo "</b></td>";?>
</tr>
</table>
<?
}
}
function test() {
include ("config/config.php");
$testStav=Array();
for ($i=1; $i<=3; $i++) {
$sql = Mysql_Query ("SELECT id FROM cs WHERE stav$i!='' AND jmeno!='' LIMIT 10");
$num = Mysql_Num_Rows ($sql);
$prom = "stav$i";
if ($num > 5) $promt = array_push($testStav,$prom);
}
$pole = $testStav;
return $pole;
}
?>
|
||
| _es Profil |
#22 · Zasláno: 6. 6. 2010, 16:53:34 · Upravil/a: _es
Tak ja tu dám tiež nejaký skript v JS a HTML.
Podstata spočíva v: 1) Hráči sa náhodne rozdelia na dve skupiny. 2) V zadanom počte cyklov sa, ak to prospeje k menšej rozdielnosti v skupinách, vzájomne prehodia hráči na tom istom mieste v skupine. 3) Pred ďalším cyklom sa hráči v každej skupine náhodne zoradia. <!DOCTYPE HTML>
Vstupne pole: <br>
<textarea rows=6 cols=100 id=vstupne>58,95,68,47,68,91,24,57,94,38,27,91,27,75,85,99,67,54</textarea>
<br>Pocet cyklov: <input type=text value=10 size=6 id=cyklov><input type=button value=Vyrataj id=vyrataj><hr>
Zoradene pole: <br>
<textarea rows=6 cols=100 id=zoradene></textarea>Celkovy sucet: <input type=text value=1 size=10 id=sucet>
<br>Prve druzstvo:<br>
<textarea rows=4 cols=100 id=prve></textarea>Celkovy sucet: <input type=text size=10 id=sucet1>
<br>Druhe druzstvo:<br>
<textarea rows=4 cols=100 id=druhe></textarea>Celkovy sucet: <input type=text size=10 id=sucet2>
<script>
document.getElementById("vyrataj").onclick = function(){
var p = document.getElementById("vstupne").value.split(",");
var n = p.length, t;
var n1 = Math.floor(n/2), n2 = Math.ceil(n/2);
var p1 = new Array(n1), p2 = new Array(n2);
for(var i = 0; i < n; ++i) p[i] = Number(p[i]);
document.getElementById("zoradene").value = p.sort(z);
var c = Number(document.getElementById("cyklov").value);
for(var i = 0; i < n1; ++i) p1[i] = p.splice(Math.floor(Math.random() * (n - i)), 1)[0];
for(var i = 0; i < n2; ++i) p2[i] = p.splice(Math.floor(Math.random() * (n2 - i)), 1)[0];
var s1 = 0, s2 = 0;
for(var i = 0; i < n1; ++i) s1 += p1[i];
for(var i = 0; i < n2; ++i) s2 += p2[i];
var d = s1 - s2, s = s1 + s2;
for(var j = 0; j < c; ++j){
if (j) {
t = new Array(n1);
for(var i = 0; i < n1; ++i) t[i] = p1.splice(Math.floor(Math.random() * (n1 - i)), 1)[0];
p1 = t; t = new Array(n2);
for(var i = 0; i < n2; ++i) t[i] = p2.splice(Math.floor(Math.random() * (n2 - i)), 1)[0];
p2 = t; t = void 0;
}
for(var i = 0; i < n1; ++i) {
if (Math.abs( d + 2 * (p2[i] - p1[i]) ) < Math.abs(d)) {
d = d + 2 * (p2[i] - p1[i]); t = p1[i]; p1[i] = p2[i]; p2[i] = t;
}
}
}
document.getElementById("sucet").value = s;
document.getElementById("prve").value = p1.sort(z);
document.getElementById("sucet1").value = (s + d) / 2;
document.getElementById("druhe").value = p2.sort(z);
document.getElementById("sucet2").value = (s - d) / 2;
}
function z(a,b) {return b-a; }
</script> |
||
| panterek Profil |
#23 · Zasláno: 7. 6. 2010, 06:57:34
Noo, tady to udělá i víc alternativ, hodně praktické řešení ..v JS je ten kód jakýsi malý, bych se v něm možná mohl naučit dělat :)
THX |
||
|
Časová prodleva: 14 let
|
|||
0