Declaratieve Talen/oplossingenTeam

LET OP Deze oplossing werkt alleen voor groepjes van 2 omdat het alle groepen genereerd die mogelijk zijn, duurt het te lang om grotere groepen te maken

Belangrijk

Het is een goed idee om eerst de verdelingen te gaan sorteren, en dan pas de dubbels te verwijderen. Dit dient te gebeuren op basis van:

- studenten in de teams: [2,1] moet [1,2] worden - teams op zich: [[3,4],[1,2]] moet gesorteerd worden tot [[1,2],[3,4]]

De gehele lijst van oplossingen zal op zich gesorteerd zijn door de manier waarop permutaties berekend worden.

Achteraf is het dan mogelijk om dubbele oplossingen te verwijderen. Zonder sortering zou je oplossing [[3,4],[1,2]] en [[1,2],[3,4]] gekregen hebben. Mits die beide gesorteerd zullen zijn, krijg je gewoon twee maal [[1,2],[3,4]] en kan je dus dubbels herkennen. Dit is een eenvoudigere strategie dan, alvorens te sorteren, op zoek te gaan naar dubbels.

Beschrijving predikaten

maakTeam geeft telkens S elementen uit de lijst terug. Stel lijst = [1,2,3,4] en we nemen S=2, dan zal de output [1,2] [1,4] [2,3] zijn.

maakTeams geeft telkens een combinatie van S elementen terug uit de lijst. Stel lijst = [1,2,3,4] en S=2, dan zal de output [[1,2],[3,4]],[[1,3],[2,4]],[[2,3],[1,4]],... zijn.

maak_schedule geeft W keer een uniek element uit de verdeling terug. Stel W=3, dan is de output een lijst met 3 elementen, namelijk 3 combinaties gegenereerd uit de verdeling.

aantalwerkjes telt de mogelijke lengtes van de verdelingen lijst, maakt er een lijst van en neemt een willekeurig element uit de lijst (elke verdeling is even lang).

% T teams en in elk team moeten S studenten
% Deel1: verdeling(T,S,Verdeling)

verdeling(T,S,Verdeling):- X is T*S,
	                   numlist(1,X,List),
			   findall(List2,(maakTeams(List,S,List2)),List3),				   list_to_set(List3,List4),
			   sorteer(List4,List5),
			   list_to_set(List5,List6),
			   member(Verdeling,List6).

maakTeams([],_,[]).
maakTeams(List,S,[TeamS|Teams]):-maakTeam(List,S,Team1),
			               sort(Team1,TeamS),
				       findall(X,(member(X,List),\+member(X,TeamS)),Overige),
      				       maakTeams(Overige,S,Teams).

maakTeam(_,0,[]).
maakTeam(List,S,[A|Team]):-
	               S>0,
		       T is S-1,
		       maakTeam(List,T,Team),
		       member(A,List),
	               \+ member(A,Team).

sorteer([X],[X]).
sorteer([X,Y|Xs],[[L1|L2]|List]):-sort(X,[L1|L2]),
	                          sort(Y,[M1|M2]),
				  (
				  (L1==M1;(member(M,L2),(member(M,M2))))->
			            sorteer([[L1|L2]|Xs],List)
				   ;
			            sorteer([[M1|M2]|Xs],List)
			           ).

%Deel 2
groepeer(T,S,W,Schedule):-
	findall(Schedule2,(maak_schedule(T,S,W,[],Schedule1),sort(Schedule1,Schedule2)),Schedule3),
	list_to_set(Schedule3,Schedule4),
	member(Schedule,Schedule4).

%Deel 3
maak_schedule(_,_,0,S,S).
maak_schedule(T,S,W,HSchedule,[Sch|Schedule]):-
	verdeling(T,S,Sch),
	\+member(Sch,HSchedule),
	NewW is W-1,
	maak_schedule(T,S,NewW,[Sch|HSchedule],Schedule).

aantalwerkjes(T,S,W):-
	findall(Y,(verdeling(T,S,List),length(List,X),Y is X+1),List2),
	list_to_set(List2,Set),
	member(W,Set).

--Greet

Andere mogelijke oplossing: FOUT

Deze oplossing is fout:
* S en T uit de opgave worden omgewisseld (no biggy)
* Er komen dubbele teams in voor. Met het eerste puntje verbetert zijn de eerste twee resultaten voor T = 2, S = 3
Teams = [[1, 2, 3], [4, 5, 6]] ;
Teams = [[1, 2, 4], [3, 5, 6]] ;
Welke dus al overeenkomstige paren hebben. Hier wordt nooit op gecheckt.
Ik vrees dat dit niet zal gaan zonder findall.
 - Vincent Goossens


verdeling(0, _, []).
verdeling(Teams, Studenten, MogelijkeTeams):-
	AantalStudenten is Teams*Studenten,
	numlist(1, AantalStudenten, StudentenLijst),
	permutation(StudentenLijst, MogelijkePermutatie),
	maakteams(MogelijkePermutatie, Teams, MogelijkeTeams),
	aanvaardbareteams(MogelijkeTeams).

maakteams([], _, []).
maakteams(Permutatie, AantalTeams, [Team|OverigeTeams]):-
	length(Team, AantalTeams),
	append(Team, PermutatieRest, Permutatie),
	maakteams(PermutatieRest, AantalTeams, OverigeTeams).

aanvaardbareteams(MogelijkeTeams):-
	sorteerdeellijsten(MogelijkeTeams, DeelsGesorteerd),
	sort(DeelsGesorteerd, GesorteerdeMogelijkeTeams),
	lijstengelijk(MogelijkeTeams, GesorteerdeMogelijkeTeams).

sorteerdeellijsten([], []).
sorteerdeellijsten([Lijst|Rest], [GesorteerdeLijst|GesorteerdeDeelLijsten]):-
	sort(Lijst, GesorteerdeLijst),
	sorteerdeellijsten(Rest, GesorteerdeDeelLijsten).

lijstengelijk([], []).
lijstengelijk([El1|Rest1], [El2|Rest2]):-
	El1 == El2,
	lijstengelijk(Rest1, Rest2).

--Harm.de.weirdt 12 jan 2012 14:22 (CET)

Andere mogelijke oplossing: OOK FOUT

Zelfde fouten als hierboven.
Plus, geeft de verdelingen allemaal in één keer terug. (kan simpel opgelost worden met member).
 - Vincent

maakTeams(Teams,[Perm|Rest],[Team|TRest]):-
	maakTeam(Teams,Perm,Team),
	maakTeams(Teams,Rest,TRest).
maakTeams(_,[],[]).

maakTeam(_,[],[]).
maakTeam(Teams,Perm,[Team|TRest]):-
	length(Team,Teams),
	append(Team,Restperm,Perm),
	maakTeam(Teams,Restperm,TRest).


verdeel(T,S,Verdeling):-
	Aantal is T * S,
	numlist(1,Aantal,Studenten),
	findall(X, permutation(Studenten,X),Permutaties),
	maakTeams(T,Permutaties,Teams),
	sorteer(Teams,STeams),
	verwijderDubbels(STeams,Verdeling).
	

sorteer([],[]).
sorteer([Teams|Rest],[S|Sr]):-
	sorteerTeam(Teams,Temp),
	sort(Temp,S),
	sorteer(Rest,Sr).

sorteerTeam([],[]).
sorteerTeam([A|As],[B|Bs]):-
	sort(A,B),
	sorteerTeam(As,Bs).



verwijderDubbels([],[]).
verwijderDubbels([Teams|Rest],[GoedTeam|Grest]):-
	not(dubbel(Teams,Rest)) -> (GoedTeam = Teams, verwijderDubbels(Rest,Grest));
	verwijderDubbels(Rest,[GoedTeam|Grest]).

dubbel(Team,[Team|_]).
dubbel(Team,[_|Xs]):- dubbel(Team,Xs).
		

--Gebruiker:Laurent Indekeu 15 jan 2012 22:49 (CET)