Find all possible pairs
Nick
I wrote this code to identify all possible pairs present in a set.
For example, if I have List = [1,2,3,4,5] then i want to get this:
PairsList = [ [1-2], [1-3], [1-4], [1-5],
[2-3], [2-4], [2-5],
[3-4], [3-5],
[4-5]
]
The code is:
--------------------------------------------------
possible_pairs( List, PairsList) :-
possible_pairs(List, List, [], PairsList).
% if there are at least 3 elements in the list
possible_pairs( [Elem1, Elem2|Tail], List, PairsListTmp, PairsL ):-
length(Tail, Len),
Len > 0,
append( PairsListTmp, [ [Elem1, Elem2] ], PairsList ),
append( [Elem1], Tail, NewList ),
possible_pairs( NewList, List, PairsList, PairsL ).
%if there are 2 elements in the list
possible_pairs([SecondLastElem, LastElem|Tail], List, PairsListTmp,
PairsL):-
length(Tail, Len),
Len is 0,
append( PairsListTmp, [ [SecondLastElem, LastElem] ], PairsList),
% remove the first element
nth0( 0, List, FirstElem ),
select( FirstElem, List, NewSmallerList),
possible_pairs( NewSmallerList, NewSmallerList, PairsList, PairsL).
% if there is 1 element in the list
possible_pairs( List, _, PairsListTmp, PairsL ):-
length(List, Len),
Len is 1,
possible_pairs( [], PairsListTmp, PairsL ).
--------------------------------------------------------
Is there a better way to find all the pairs without using length?
Thanks in advance and sorry for my english
Chip Eastham
The example suggests you want the unordered pairs
(any two "distinct" items, provided all the items
in the list are different). findall/3 can be used
to collect them into a list, if that's desired.
How about something like:
splitSet(List,[A,B],_)
where:
/* splitSet/3 splits a list into two sublists */
splitSet([ ],[ ],[ ]).
splitSet([H|T],[H|L],R) :-
splitSet(T,L,R).
splitSet([H|T],L,[H|R]) :-
splitSet(T,L,R).
This allows you to get distinct triples, etc.
by the same method. If you're only interested
in distinct pairs with infix "-", you could do:
pairs([A|T],[A-B]) :- member(B,T).
pairs([_|T],[A-B]) :- pairs(T,[A-B]).
regards, chip
Nick
no, i don't want to use the infix "-", it's has been my mistake...so
the outcome should be:
PairsList = [ [1,2], [1,3], [1,4], [1,5],
[2,3], [2,4], [2,5],
[3,4], [3,5],
[4,5]
]
...
but ...could you explain better the use of spiltSet? i don't
understand how i could use that in my problem:(
thanks again
afa
This can be easily done using list comprehension in B-Prolog:
?- List=[1,2,3,4,5], Pairs @= [[I-J] : I in List, J in List, I<J]
List = [1,2,3,4,5]
Pairs = [[1-2],[1-3],[1-4],[1-5],[2-3],[2-4],[2-5],[3-4],[3-5],[4-5]]
Cheers,
Neng-Fa
Nick
i'm using Swi-prolog... :(
Chip Eastham
I did the following experiment with SWI-Prolog.
Start SWI-Prolog's console, and from "top level"
enter consult mode for the [user] module. Cut
and paste the splitSet/3 predicate definition
given above, and then type Ctrl-D to exit the
consulting mode.
Now give as our first goal:
?- splitSet([1,2,3,4,5],[A,B],_).
Type semicolon repeatedly with each "success"
to verify the ten solutions for pairs A,B.
Now give as our second goal:
?- findall([X,Y],splitSet([1,2,3,4,5],[X,Y],_),List),
write(List).
and verify that the resulting List contains all
ten solution pairs [1,2] through [4,5] as
desired.
regards, chip
Jan Wielemaker
The above is (AFAIK), syntactic sugar for the following traditional
Prolog program:
pairs_in(Set, Pairs) :-
findall(Pair, pair_in(Set, Pair), Pairs).
pair_in(Set, I-J) :-
member(I, Set),
member(J, Set),
I<J.
This is the readable variation. If you want the short one:
?- List = [1,2,3,4,5], findall(I-J, (member(I,List), member(J,List), I<J), Pairs).
If I add
:- op(500, xfx, in).
in(E,List) :- member(E,List).
This becomes pretty close to the B-Prolog code:
?- List = [1,2,3,4,5], findall(I-J, (I in List, J in List, I<J), Pairs).
We've seen a lot of these syntactical layers lately, but personally I
still prefer the first alternative. It reads comfortably, if anything
weird happens you can more easily debug pair_in/2 and finally you can
use pair_in/2 directly instead of being tempted to use the list
comprehension followed by a member/2 call.
Cheers --- Jan
Mats Carlsson
> On 25 Nov, 18:59, Chip Eastham <hardm...@gmail.com> wrote:
>
>
>
> > On Nov 25, 11:44 am, Nick <nicola1...@tiscalinet.it> wrote:
>
> > > Hello everyone,
>
> > > I wrote this code to identify all possible pairs present in a set.
> > > For example, if I have List = [1,2,3,4,5] then i want to get this:
> > > PairsList = [ [1-2], [1-3], [1-4], [1-5],
> > > [2-3], [2-4], [2-5],
> > > [3-4], [3-5],
> > > [4-5]
> > > ]
>
> no, i don't want to use the infix "-", it's has been my mistake...so
> the outcome should be:
>
> PairsList = [ [1,2], [1,3], [1,4], [1,5],
> [2,3], [2,4], [2,5],
> [3,4], [3,5],
> [4,5]
> ]
> ...
Here is how to solve it with logical loops (ECLiPSe/SICStus):
all_pairs(L) -->
( fromto(L,[X|R],R,[_])
do ( foreach(Y,R),
param(X)
do [[X,Y]]
)
).
| ?- all_pairs([1,2,3,4,5], Pairs, []).
Pairs = [[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5],[3,4],[3,5],
[4,5]] ?
yes
--Mats
Colin Barker
"Nick" <nicol...@tiscalinet.it> a écrit dans le message de
news:3a20b60f-2e86-43e3...@r21g2000pri.googlegroups.com...
the outcome should be:
PairsList = [ [1,2], [1,3], [1,4], [1,5],
[2,3], [2,4], [2,5],
[3,4], [3,5],
[4,5]
]
Here's a version that doesn't use findall/3, but does use difference lists,
and is tail-recursive:
% e.g. pairs([1,2,3,4,5],X)
% gives X=[[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5],[3,4],[3,5],[4,5]]
pairs(Xs, Ys):-pairs_1(Xs, Ys-[]).
pairs_1([], Ys-Ys).
pairs_1([X|Xs], Ys-As):-
pairs_2(Xs, X, Ys-Bs),
pairs_1(Xs, Bs-As).
pairs_2([], _, Zs-Zs).
pairs_2([X|Xs], Y, [[Y,X]|Zs]-As):-
pairs_2(Xs, Y, Zs-As).
If you don't like the "-" in the clauses, replace tham by ",".
--
Colin
Nick
> % e.g. pairs([1,2,3,4,5],X)
> % gives X=[[1,2],[1,3],[1,4],[1,5],[2,3],[2,4],[2,5],[3,4],[3,5],[4,5]]
> pairs(Xs, Ys):-pairs_1(Xs, Ys-[]).
>
> pairs_1([], Ys-Ys).
> pairs_1([X|Xs], Ys-As):-
> pairs_2(Xs, X, Ys-Bs),
> pairs_1(Xs, Bs-As).
>
> pairs_2([], _, Zs-Zs).
> pairs_2([X|Xs], Y, [[Y,X]|Zs]-As):-
> pairs_2(Xs, Y, Zs-As).
>
> If you don't like the "-" in the clauses, replace tham by ",".
> --
> Colin
thanks to all for the replies!
Last question: i don't know the use of "-" in the cluases (e.g.
pairs_2(Xs, X, Ys-Bs)). What is "-"?
afa
Yes, the foreach in B-Prolog is a kind of syntax sugar, but it is
translated into tail-recursive predicates not failure-driven loops.
There are two problems with failure-driven loops: first, it's not
efficient and using findall makes it even worse; and second, it's
impossible to retain bindings of variables (variables shared by all
iterations). I like list comprehension better than the logical loops
in ECLiPSe/SICStus because list comprehension is similar with the the
set-builder notation and everybody is familiar with it already.
Cheers,
Neng-Fa
Colin Barker
Last question: i don't know the use of "-" in the cluases (e.g.
pairs_2(Xs, X, Ys-Bs)). What is "-"?
I believe that historically "-" was used to indicate that Ys and Bs
represent a difference list. I will leave it to someone else to say whether
or not Ys-Bs is exactly equivalent to Ys,Bs in this context.
--
Colin
Nick
> I believe that historically "-" was used to indicate that Ys and Bs
> represent a difference list. I will leave it to someone else to say whether
> or not Ys-Bs is exactly equivalent to Ys,Bs in this context.
> --
> Colin
I tried to replace "-" with "," and it works good
Markus Triska
> If you don't like the "-" in the clauses, replace tham by ",".
Or use DCG notation and leave the representation to the system:
pairs([]) --> [].
pairs([L|Ls]) --> pairs_(Ls, L), pairs(Ls).
pairs_([], _) --> [].
pairs_([R|Rs], L) --> [[L,R]], pairs_(Rs, L).
Example:
%?- phrase(pairs([a,b,c]), Ps).
%@ Ps = [[a, b], [a, c], [b, c]].
--
comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/
Jan Wielemaker
> On Nov 26, 4:13 am, Jan Wielemaker <j...@nospam.ct> wrote:
>> On 2010-11-25, Nick <nicola1...@tiscalinet.it> wrote:
>>
>> > On 25 Nov, 21:27, afa <neng.z...@gmail.com> wrote:
>> >> On Nov 25, 1:51 pm, Nick <nicola1...@tiscalinet.it> wrote:
>>
>> >> This can be easily done using list comprehension in B-Prolog:
>>
>> >> ?- List=[1,2,3,4,5], Pairs @= [[I-J] : I in List, J in List, I<J]
...
>> This becomes pretty close to the B-Prolog code:
>>
>> ?- List = [1,2,3,4,5], findall(I-J, (I in List, J in List, I<J), Pairs).
>>
>> We've seen a lot of these syntactical layers lately, but personally I
>> still prefer the first alternative. It reads comfortably, if anything
>> weird happens you can more easily debug pair_in/2 and finally you can
>> use pair_in/2 directly instead of being tempted to use the list
>> comprehension followed by a member/2 call.
>>
>> Cheers --- Jan
>
> Yes, the foreach in B-Prolog is a kind of syntax sugar, but it is
> translated into tail-recursive predicates not failure-driven loops.
> There are two problems with failure-driven loops: first, it's not
> efficient and using findall makes it even worse; and second, it's
> impossible to retain bindings of variables (variables shared by all
> iterations). I like list comprehension better than the logical loops
> in ECLiPSe/SICStus because list comprehension is similar with the the
> set-builder notation and everybody is familiar with it already.
I think your arguments make sense. Well, there is no fundamental
reason while failure driven loops must be slow, but findall does
involve copying. Sometimes the compiler should be able to avoid
the actual copying, but in general that is very hard.
I like the syntax (at least for this case), though it makes one think
about findall/backtracking.
Is there a free implementation of the translator?
Cheers --- Jan