generate all the possible pairings of elements (a, b), where a is from set A and b is from set B in prolog

user_10361238 0
Viewed 50

Currently I am trying to generate all the possible pairings of elements (a, b), where a is from set A and b is from set B in prolog. For example given:

A = {1 ,2, 3} B = {a, b, c}

One possible set of pairings would be {(1,a), (2,b), (3,c)}

I want to find all unique sets of pairings for a and b. I believe that the number of possible pairings should be n!.

Here is my attempt. (In my case set A is a list of Employer names and set B is a list of Student names).

generateMatching(Matching, [], [], Matching). 
generateMatching(Matches, Employers(A), Students(B), Result) :- member(S, Students), member(E, Employers), 
delete(Students, S, Students1), delete(Employers, E, Employers1), 
generateMatching([(E, S)|Matches], Employers1, Students1, Result).

and I call it like 

generateMatching([], Employers, Students, Matching)

Essentially on each call I am picking some member of the set of Students (S) and some member of the set of Employers (E) and then adding them to the current set of matches (Pairings). I then deleting them from the sets from which they were picked so that they cannot be picked again. I keep doing this until I have 2 empty lists and I know I have found a possible set of pairings.

The problem I is that the solution I have will consider {(1,a), (2,b), (3,c)} and {(1,a), (3,c), (2,b)} to be different pairings, and as a result computation is very slow.

How can I improve this?

EDIT: What I actually want to get after the query is this. To be more clear, a solution is a set of pairing where each element from A is paired with exactly 1 from B and vice-versa

Matching = [(1,a), (2, b), (3, c)] ; 
Matching = [(1,a), (2, c), (3, b)] ;
Matching = [(1,b), (2, c), (3, a)] ;
Matching = [(1,b), (2, a), (3, c)] ;
Matching = [(1,c), (2, b), (3, a)] ;
Matching = [(1,c), (2, a), (3, b)] ;
False.
prolog
1 Answers

Assuming the de facto standard select/3 predicate is available:

pairs([], [], []).
pairs([E1| R1], L2, [E1-E2| R]) :-
    select(E2, L2, R2),
    pairs(R1, R2, R).

Sample call:

| ?- pairs([1,2,3],[a,b,c],L).

L = [1-a,2-b,3-c] ? ;
L = [1-a,2-c,3-b] ? ;
L = [1-b,2-a,3-c] ? ;
L = [1-b,2-c,3-a] ? ;
L = [1-c,2-a,3-b] ? ;
L = [1-c,2-b,3-a] ? ;
no

Also, as a general style guideline rule, prefer Key-Value as a pair representation.

user_6346290
Related