Declaratieve Talen/oplossingenTeam

Zijn al deze oplossingen foutief?

• de regel "twee studenten mogen gedurende heel hun opleiding maar 1 keer in hetzelfde team zitten" wordt in geen van de oplossingen nagekeken. Er wordt slechts gekeken naar dat er geen teams dubbel zijn.

Voor alle oplossingen hieronder zal gelden:

verdeling(2,3,Teams).
Teams = [[1, 2, 3], [4, 5, 6]] ;
Teams = [[1, 2, 4], [3, 5, 6]] ;
...

Die eerste twee teams bevatten dus al een paar van studenten twee keer. Ik denk dat dit niet aan het licht is gekomen omdat verdeling(2,2,X) perongeluk wel juiste resultaten geeft, en enkel hiermee getest is geweest. --Vincent.goossens 18 jan 2012 07:03 (CET)

---

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:

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:

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)

Andere mogelijke oplossing (alleen deel 1)

verdeling(T,S,Verdeling) :-
    AantalStudenten is T * S,
    numlist(1, AantalStudenten, LijstStudenten),
    generate_teams(S, LijstStudenten, Verdeling).
  
% generate_teams(StudentenPerTeam, LijstStudenten, Teams)
generate_teams(_, [], []).
generate_teams(S, LijstStudenten, [Team | Teams]) :-
    generate_team(S, LijstStudenten, Rest, Team),
    generate_teams(S, Rest, Teams).

generate_team(N, [H|T], Lijst_out, [H |Team]) :-
    New_N is N - 1,
    generate_team_rec(New_N, T, Lijst_out, Team).

generate_team_rec(N, L, L, []) :-
    N =< 0. 
generate_team_rec(N, [H|T], Lijst_out, [H |Team]) :-
    N > 0,
    New_N is N - 1,
    generate_team_rec(New_N, T, Lijst_out, Team).
generate_team_rec(N, [H|T], [H | Lijst_out], Team) :-
    N > 0,
    generate_team_rec(N, T, Lijst_out, Team).