recursief zoeken
Ik wil php tegenstanders laten berekenen maar ik kom er niet uit.
Eerst heb ik data. Komt normaal uit de database maar om hier te posten even json gebruikt. De spelers zijn gesorteerd op hun punten.
Code (php)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
[
{"id":"147","naam":"Philippe","punten":"2048","wit":"2","zwart":"2"},
{"id":"122","naam":"Thomas","punten":"2030","wit":"1","zwart":"1"},
{"id":"117","naam":"Freddy","punten":"2028","wit":"2","zwart":"2"},
{"id":"115","naam":"Eddy","punten":"2020","wit":"2","zwart":"2"},
{"id":"119","naam":"Jan","punten":"2016","wit":"2","zwart":"2"},
{"id":"123","naam":"Yvonne","punten":"1984","wit":"1","zwart":"2"},
{"id":"148","naam":"Pierre Matthys","punten":"1922","wit":"2","zwart":"1"},
{"id":"126","naam":"Jacques","punten":"1920","wit":"2","zwart":"1"}
]
//wit en zwart is het aantal keren met respectievelijke kleur gespeeld
{
"147":{"id":"147","naam":"Philippe","aantaltegenstanders":3,"punten":"2048","tegenstanders":{"115":1,"117":0,"119":1,"122":0,"123":0,"126":1,"147":0,"148":0}},
"122":{"id":"122","naam":"Thomas","aantaltegenstanders":2,"punten":"2030","tegenstanders":{"115":1,"117":0,"119":0,"122":0,"123":0,"126":1,"147":0,"148":0}},
"117":{"id":"117","naam":"Freddy","aantaltegenstanders":3,"punten":"2028","tegenstanders":{"115":0,"117":0,"119":1,"122":0,"123":0,"126":1,"147":0,"148":1}},
"115":{"id":"115","naam":"Eddy","aantaltegenstanders":3,"punten":"2020","tegenstanders":{"115":0,"117":0,"119":0,"122":1,"123":1,"126":0,"147":1,"148":0}},
"119":{"id":"119","naam":"Jan","aantaltegenstanders":4,"punten":"2016","tegenstanders":{"115":0,"117":1,"119":0,"122":0,"123":1,"126":0,"147":1,"148":1}},
"123":{"id":"123","naam":"Yvonne","aantaltegenstanders":3,"punten":"1984","tegenstanders":{"115":1,"117":0,"119":1,"122":0,"123":0,"126":0,"147":0,"148":1}},
"148":{"id":"148","naam":"Pierre","aantaltegenstanders":3,"punten":"1922","tegenstanders":{"115":0,"117":1,"119":1,"122":0,"123":1,"126":0,"147":0,"148":0}},
"126":{"id":"126","naam":"Jacques","aantaltegenstanders":3,"punten":"1920","tegenstanders":{"115":0,"117":1,"119":0,"122":1,"123":0,"126":0,"147":1,"148":0}}
}
//het nummer bij tegenstanders is het aantal al keren tegen elkaar gespeeld.
{"id":"147","naam":"Philippe","punten":"2048","wit":"2","zwart":"2"},
{"id":"122","naam":"Thomas","punten":"2030","wit":"1","zwart":"1"},
{"id":"117","naam":"Freddy","punten":"2028","wit":"2","zwart":"2"},
{"id":"115","naam":"Eddy","punten":"2020","wit":"2","zwart":"2"},
{"id":"119","naam":"Jan","punten":"2016","wit":"2","zwart":"2"},
{"id":"123","naam":"Yvonne","punten":"1984","wit":"1","zwart":"2"},
{"id":"148","naam":"Pierre Matthys","punten":"1922","wit":"2","zwart":"1"},
{"id":"126","naam":"Jacques","punten":"1920","wit":"2","zwart":"1"}
]
//wit en zwart is het aantal keren met respectievelijke kleur gespeeld
{
"147":{"id":"147","naam":"Philippe","aantaltegenstanders":3,"punten":"2048","tegenstanders":{"115":1,"117":0,"119":1,"122":0,"123":0,"126":1,"147":0,"148":0}},
"122":{"id":"122","naam":"Thomas","aantaltegenstanders":2,"punten":"2030","tegenstanders":{"115":1,"117":0,"119":0,"122":0,"123":0,"126":1,"147":0,"148":0}},
"117":{"id":"117","naam":"Freddy","aantaltegenstanders":3,"punten":"2028","tegenstanders":{"115":0,"117":0,"119":1,"122":0,"123":0,"126":1,"147":0,"148":1}},
"115":{"id":"115","naam":"Eddy","aantaltegenstanders":3,"punten":"2020","tegenstanders":{"115":0,"117":0,"119":0,"122":1,"123":1,"126":0,"147":1,"148":0}},
"119":{"id":"119","naam":"Jan","aantaltegenstanders":4,"punten":"2016","tegenstanders":{"115":0,"117":1,"119":0,"122":0,"123":1,"126":0,"147":1,"148":1}},
"123":{"id":"123","naam":"Yvonne","aantaltegenstanders":3,"punten":"1984","tegenstanders":{"115":1,"117":0,"119":1,"122":0,"123":0,"126":0,"147":0,"148":1}},
"148":{"id":"148","naam":"Pierre","aantaltegenstanders":3,"punten":"1922","tegenstanders":{"115":0,"117":1,"119":1,"122":0,"123":1,"126":0,"147":0,"148":0}},
"126":{"id":"126","naam":"Jacques","aantaltegenstanders":3,"punten":"1920","tegenstanders":{"115":0,"117":1,"119":0,"122":1,"123":0,"126":0,"147":1,"148":0}}
}
//het nummer bij tegenstanders is het aantal al keren tegen elkaar gespeeld.
De bedoeling is dat je pas tegen elkaar gaat spelen als je nog niet tegen elkaar of zo weining mogelijk tegen elkaar al gespeeld hebt.
In bijgevoegde data is het dus mogelijk om te komen tot resultaat
Quote:
Philippe-Thomas
Freddy-eddy
Jan-Pierre
Yvonne-Jacques
Freddy-eddy
Jan-Pierre
Yvonne-Jacques
Wat ik echter bedenk als code het komt nooit uit.
Manueel lukt het me wel dus zou ik het ook moeten kunnen schrijven in php toch zou je denken maar dus niet :(.
Hopelijk heeft iemand een ideetje om te helpen.
Jan
Gewijzigd op 13/12/2021 08:05:41 door Jan R
Code (php)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
<?php
$ids = array_keys($data); //$data is die 2e tabel
$default_scores = array_fill_keys($ids,0); //standaard tegen niemand gespeeld
foreach($data as $id => $player){ //per speler gaan bekijken
$scores = $player['tegenstanders'];
unset($scores['totaal']);
$scores = array_merge($default_scores,$scores); //nu voor iedereen een score
asort($scores); //sorteren op score (minste vooraan)
$opponents = array_keys($scores); //tegenstanders geordend
$opponent = array_shift($opponents); //tegenstander met minste partijen
//verder afhandelen/opslaan/enz
}
?>
$ids = array_keys($data); //$data is die 2e tabel
$default_scores = array_fill_keys($ids,0); //standaard tegen niemand gespeeld
foreach($data as $id => $player){ //per speler gaan bekijken
$scores = $player['tegenstanders'];
unset($scores['totaal']);
$scores = array_merge($default_scores,$scores); //nu voor iedereen een score
asort($scores); //sorteren op score (minste vooraan)
$opponents = array_keys($scores); //tegenstanders geordend
$opponent = array_shift($opponents); //tegenstander met minste partijen
//verder afhandelen/opslaan/enz
}
?>
Dan moet je verderop wel controleren dat zowel $id als $opponent niet meer aan iemand anders gekoppeld kunnen worden (een lijstje met $fulfilled bijhouden, en daarvoor de $id's overslaan, en deze uit $opponents halen).
Of is het dan nog weer de bedoeling dat als A tegen B of C kan spelen (beiden nog nooit tegen gespeeld), maar D al wel tegen C heeft gespeeld, dat ie dan ook nog zo wijs is om A aan C te koppelen, zodat B dan tegen D kan?
Juist dat je Totaal verwijderd. Stond op verkeerde plaats.
oorspronkelijke data aangepast.
Je basis is ongeveer hetzelfde als ik had echter ik blijf vastlopen.
ik heb ofwel onvolledige data, niet alle spelers gevonden, of kom in een eindeloze lus.
Code (php)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
<?php
$ids = array_keys($partijen);//partijen oorspronkelijke data
{
foreach($ids as $id) {//niemand speelt
$speelt[$id]=false;
}
$i=$j=0;
while ($i<count($ids)) {//loop door alle spelers
$id1=$ids[$i];
if(!$speelt[$id1]) {
$j=0;
while ($j<count($ids)) {//zoek tegestander
$id2=$ids[$j];
if(!$speelt[$id2]) {
if($id1!=$id2) {/niet tegen jezelf
if($partijen[$id1]['tegenstanders'][$id2]<=$verschilWZ) {// aantal parttijen < max toegelaten
$stappen[] = array($i,$j);//bewaar stappen om terug te keren indien lus niet volledig ok
$speelt[$id1]=$speelt[$id2]=true;//deze 2 spelers spelen nu wel
$borden[] = array($partijen[$id1],$partijen[$id2]);//bepaal bord. exact 2 spelers
if(alltrue($speelt)) {//eenvoudige lus welke kijkt of alle items in array true zijn
break 2;// spring uit de 2 lussen
}
break;//ga naar volgende speler
}
}
}
$j++;
}
$j=0;
}
if($i==(count($ids)-1)) {//net voor einde kijken alles OK
if(alltrue($speelt)) {
break;//OK dus uit lus
}else{
$a = end($stappen);// niet ok stap terug
$i=($a[0]-1);
$j=($a[1]+1);
$speelt[$ids[$a[0]]] = $speelt[$ids[$a[0]]] = false;//spelers apelen toch niet
array_pop($borden);//verwijder bord
}
}
$i++;
}
}
var_dump($borden);//wordt later opnieuw uitgewerkt :)
?>
$ids = array_keys($partijen);//partijen oorspronkelijke data
{
foreach($ids as $id) {//niemand speelt
$speelt[$id]=false;
}
$i=$j=0;
while ($i<count($ids)) {//loop door alle spelers
$id1=$ids[$i];
if(!$speelt[$id1]) {
$j=0;
while ($j<count($ids)) {//zoek tegestander
$id2=$ids[$j];
if(!$speelt[$id2]) {
if($id1!=$id2) {/niet tegen jezelf
if($partijen[$id1]['tegenstanders'][$id2]<=$verschilWZ) {// aantal parttijen < max toegelaten
$stappen[] = array($i,$j);//bewaar stappen om terug te keren indien lus niet volledig ok
$speelt[$id1]=$speelt[$id2]=true;//deze 2 spelers spelen nu wel
$borden[] = array($partijen[$id1],$partijen[$id2]);//bepaal bord. exact 2 spelers
if(alltrue($speelt)) {//eenvoudige lus welke kijkt of alle items in array true zijn
break 2;// spring uit de 2 lussen
}
break;//ga naar volgende speler
}
}
}
$j++;
}
$j=0;
}
if($i==(count($ids)-1)) {//net voor einde kijken alles OK
if(alltrue($speelt)) {
break;//OK dus uit lus
}else{
$a = end($stappen);// niet ok stap terug
$i=($a[0]-1);
$j=($a[1]+1);
$speelt[$ids[$a[0]]] = $speelt[$ids[$a[0]]] = false;//spelers apelen toch niet
array_pop($borden);//verwijder bord
}
}
$i++;
}
}
var_dump($borden);//wordt later opnieuw uitgewerkt :)
?>
Jan
In je voorbeeld zeg je "wit en zwart is het aantal keren met respectievelijke kleur gespeeld", en "het nummer bij tegenstanders is het aantal al keren tegen elkaar gespeeld".
Kijk ik naar Philippe, dan heeft hij 2x met wit gespeeld en 2x met zwart, dus 4x in totaal.
Maar als ik naar de tweede helft kijk, dan zie ik dat hij maar 3x heeft gespeeld, met ID's 115, 119, 126.
Hoe zit dat?
De berekening start enkel als het aantal spelers paar is.
Code (php)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
-- SQL dump van testdatabase
CREATE TABLE `speler` (
`id` int(10) UNSIGNED NOT NULL COMMENT 'ID',
`naam` text NOT NULL COMMENT 'Naam',
`punten` int(10) UNSIGNED NOT NULL DEFAULT 0 COMMENT 'Punten'
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COMMENT='Spelers';
INSERT INTO `speler` (`id`, `naam`, `punten`) VALUES
(115, 'Eddy', 2020),
(117, 'Freddy', 2028),
(119, 'Jan', 2016),
(122, 'Thomas', 2030),
(123, 'Yvonne', 1984),
(126, 'Jacques', 1920),
(147, 'Philippe', 2048),
(148, 'Pierre Matthys', 1922);
CREATE TABLE `wedstrijd` (
`id` int(10) UNSIGNED NOT NULL COMMENT 'ID',
`wit` int(10) UNSIGNED NOT NULL DEFAULT 0 COMMENT 'Wit',
`zwart` int(10) UNSIGNED NOT NULL DEFAULT 0 COMMENT 'Zwart'
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COMMENT='Wedstrijden';
INSERT INTO `wedstrijd` (`id`, `wit`, `zwart`) VALUES
(1, 147, 115),
(2, 147, 126),
(3, 122, 115),
(4, 122, 126),
(5, 117, 119),
(6, 117, 148),
(7, 115, 123),
(8, 119, 147),
(9, 119, 148),
(10, 123, 119),
(11, 148, 123),
(12, 126, 117);
ALTER TABLE `speler`
ADD PRIMARY KEY (`id`);
ALTER TABLE `wedstrijd`
ADD PRIMARY KEY (`id`),
ADD KEY `wedstrijd_speler_wit` (`wit`),
ADD KEY `wedstrijd_speler_zwart` (`zwart`);
ALTER TABLE `speler`
MODIFY `id` int(10) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 'ID', AUTO_INCREMENT=149;
ALTER TABLE `wedstrijd`
MODIFY `id` int(10) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 'ID', AUTO_INCREMENT=13;
ALTER TABLE `wedstrijd`
ADD CONSTRAINT `wedstrijd_speler_wit` FOREIGN KEY (`wit`) REFERENCES `speler` (`id`) ON UPDATE CASCADE,
ADD CONSTRAINT `wedstrijd_speler_zwart` FOREIGN KEY (`zwart`) REFERENCES `speler` (`id`) ON UPDATE CASCADE;
CREATE TABLE `speler` (
`id` int(10) UNSIGNED NOT NULL COMMENT 'ID',
`naam` text NOT NULL COMMENT 'Naam',
`punten` int(10) UNSIGNED NOT NULL DEFAULT 0 COMMENT 'Punten'
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COMMENT='Spelers';
INSERT INTO `speler` (`id`, `naam`, `punten`) VALUES
(115, 'Eddy', 2020),
(117, 'Freddy', 2028),
(119, 'Jan', 2016),
(122, 'Thomas', 2030),
(123, 'Yvonne', 1984),
(126, 'Jacques', 1920),
(147, 'Philippe', 2048),
(148, 'Pierre Matthys', 1922);
CREATE TABLE `wedstrijd` (
`id` int(10) UNSIGNED NOT NULL COMMENT 'ID',
`wit` int(10) UNSIGNED NOT NULL DEFAULT 0 COMMENT 'Wit',
`zwart` int(10) UNSIGNED NOT NULL DEFAULT 0 COMMENT 'Zwart'
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COMMENT='Wedstrijden';
INSERT INTO `wedstrijd` (`id`, `wit`, `zwart`) VALUES
(1, 147, 115),
(2, 147, 126),
(3, 122, 115),
(4, 122, 126),
(5, 117, 119),
(6, 117, 148),
(7, 115, 123),
(8, 119, 147),
(9, 119, 148),
(10, 123, 119),
(11, 148, 123),
(12, 126, 117);
ALTER TABLE `speler`
ADD PRIMARY KEY (`id`);
ALTER TABLE `wedstrijd`
ADD PRIMARY KEY (`id`),
ADD KEY `wedstrijd_speler_wit` (`wit`),
ADD KEY `wedstrijd_speler_zwart` (`zwart`);
ALTER TABLE `speler`
MODIFY `id` int(10) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 'ID', AUTO_INCREMENT=149;
ALTER TABLE `wedstrijd`
MODIFY `id` int(10) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 'ID', AUTO_INCREMENT=13;
ALTER TABLE `wedstrijd`
ADD CONSTRAINT `wedstrijd_speler_wit` FOREIGN KEY (`wit`) REFERENCES `speler` (`id`) ON UPDATE CASCADE,
ADD CONSTRAINT `wedstrijd_speler_zwart` FOREIGN KEY (`zwart`) REFERENCES `speler` (`id`) ON UPDATE CASCADE;
Daarin kan je met een query een ranking maken van spelercombinaties die de minste wedstrijden hebben gespeeld:
Code (php)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
WITH `geselecteerd` AS (
SELECT 147 AS `id`
UNION SELECT 122
UNION SELECT 117
UNION SELECT 115
UNION SELECT 119
UNION SELECT 123
UNION SELECT 148
UNION SELECT 126
)
SELECT DISTINCT
LEAST(`speler`.`id`, `tegenstander`.`id`) AS `speler_id`,
GREATEST(`speler`.`id`, `tegenstander`.`id`) AS `tegenstander_id`,
COUNT(`wedstrijd`.`id`)
OVER (PARTITION BY `speler`.`id`, `tegenstander`.`id`) AS `wedstrijden`
FROM `geselecteerd` AS `speler`
JOIN `geselecteerd` AS `tegenstander`
ON `speler`.`id` != `tegenstander`.`id`
LEFT JOIN `wedstrijd`
ON (`wedstrijd`.`wit` = `speler`.`id`
AND `wedstrijd`.`zwart` = `tegenstander`.`id`)
OR (`wedstrijd`.`wit` = `tegenstander`.`id`
AND `wedstrijd`.`zwart` = `speler`.`id`)
ORDER BY `wedstrijden`;
SELECT 147 AS `id`
UNION SELECT 122
UNION SELECT 117
UNION SELECT 115
UNION SELECT 119
UNION SELECT 123
UNION SELECT 148
UNION SELECT 126
)
SELECT DISTINCT
LEAST(`speler`.`id`, `tegenstander`.`id`) AS `speler_id`,
GREATEST(`speler`.`id`, `tegenstander`.`id`) AS `tegenstander_id`,
COUNT(`wedstrijd`.`id`)
OVER (PARTITION BY `speler`.`id`, `tegenstander`.`id`) AS `wedstrijden`
FROM `geselecteerd` AS `speler`
JOIN `geselecteerd` AS `tegenstander`
ON `speler`.`id` != `tegenstander`.`id`
LEFT JOIN `wedstrijd`
ON (`wedstrijd`.`wit` = `speler`.`id`
AND `wedstrijd`.`zwart` = `tegenstander`.`id`)
OR (`wedstrijd`.`wit` = `tegenstander`.`id`
AND `wedstrijd`.`zwart` = `speler`.`id`)
ORDER BY `wedstrijden`;
Ik was begonnen met recursief zoeken in MySQL maar de mogelijkheden zijn beperkter dan in andere databases als PostgreSQL en het is toch nog even puzzelen. Misschien is het laatste stukje logica eenvoudiger te maken in PHP.
Overigens zijn er meer mensen die dit probleem hebben willen oplossen in SQL.
sql loopt al vast op 1° woord. 'with'
WITH is onderdeel van een CTE, MySQL loopt daarmee achter. Je moet minimaal MySQL 8 hebben, anders moet je de query op de ouderwetse manier herschrijven, en jezelf herhalen in het FROM statement (dat kan dan wel weer beter met PHP):
Code (php)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
SELECT DISTINCT
LEAST(`speler`.`id`, `tegenstander`.`id`) AS `speler_id`,
GREATEST(`speler`.`id`, `tegenstander`.`id`) AS `tegenstander_id`,
COUNT(`wedstrijd`.`id`)
OVER (PARTITION BY `speler`.`id`, `tegenstander`.`id`) AS `wedstrijden`
FROM
( SELECT 147 AS `id`
UNION SELECT 122
UNION SELECT 117
UNION SELECT 115
UNION SELECT 119
UNION SELECT 123
UNION SELECT 148
UNION SELECT 126
) AS `speler`
JOIN
( SELECT 147 AS `id`
UNION SELECT 122
UNION SELECT 117
UNION SELECT 115
UNION SELECT 119
UNION SELECT 123
UNION SELECT 148
UNION SELECT 126
) AS `tegenstander`
ON `speler`.`id` != `tegenstander`.`id`
LEFT JOIN `wedstrijd`
ON (`wedstrijd`.`wit` = `speler`.`id`
AND `wedstrijd`.`zwart` = `tegenstander`.`id`)
OR (`wedstrijd`.`wit` = `tegenstander`.`id`
AND `wedstrijd`.`zwart` = `speler`.`id`)
ORDER BY `wedstrijden`;
LEAST(`speler`.`id`, `tegenstander`.`id`) AS `speler_id`,
GREATEST(`speler`.`id`, `tegenstander`.`id`) AS `tegenstander_id`,
COUNT(`wedstrijd`.`id`)
OVER (PARTITION BY `speler`.`id`, `tegenstander`.`id`) AS `wedstrijden`
FROM
( SELECT 147 AS `id`
UNION SELECT 122
UNION SELECT 117
UNION SELECT 115
UNION SELECT 119
UNION SELECT 123
UNION SELECT 148
UNION SELECT 126
) AS `speler`
JOIN
( SELECT 147 AS `id`
UNION SELECT 122
UNION SELECT 117
UNION SELECT 115
UNION SELECT 119
UNION SELECT 123
UNION SELECT 148
UNION SELECT 126
) AS `tegenstander`
ON `speler`.`id` != `tegenstander`.`id`
LEFT JOIN `wedstrijd`
ON (`wedstrijd`.`wit` = `speler`.`id`
AND `wedstrijd`.`zwart` = `tegenstander`.`id`)
OR (`wedstrijd`.`wit` = `tegenstander`.`id`
AND `wedstrijd`.`zwart` = `speler`.`id`)
ORDER BY `wedstrijden`;