2

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.
Carlisle Manson
  • 217
  • 1
  • 4
  • 8
  • Does this answer your question? [Combinations of multiple lists - Prolog](https://stackoverflow.com/questions/60580822/combinations-of-multiple-lists-prolog) – Guy Coder Mar 27 '20 at 00:38
  • what you describe is `foo(A,B,C) :- permutation(B, P), maplist(p, A, P, C).` with a suitable definition for `p`, e.g. `p(X, Y, X-Y).`. – Will Ness Mar 28 '20 at 09:47

1 Answers1

2

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.

Paulo Moura
  • 18,373
  • 3
  • 23
  • 33