🚀 go-pugleaf

From article <1992Oct29.140104.7751@coli.uni-sb.de>, by ulma@coli.uni-sb.de (Ulrich Mayring):
> Hello netters, I have a problem:
> 
> I have a list and need to recursively pick two elements out of it. I need
> every pair of elements in every order, however the order of the pair itself
> is not important. It should also be possible to pick an element and the []
> as a pair, thus guaranteeing that in the end I will have every pair and
> every single element. Then I will test the pair (or single) and if it doesn't
> suit my purpose I want to go back into the recursion to get the next one.
> 
> 
> Thanx a lot if you can help,
> 
> 
>      Ulrich Mayring
> 
>        - Also wir waren mit grau eigentlich sehr zufrieden -     


% no substitute for simplicity, i always say...

twins(L,X) :- 	subset(L,X), (X = [_,_] | X = [_] | X = []).

subset([],[]).
subset([H|T],[H|REST]) :- subset(T,REST).
subset([H|T],REST) :- subset(T,REST).   
                                          
% twins([a,b,c],Twins)?
%
% Twins = [a, b]
% 
% Twins = [a, c]
% 
% Twins = [a]
% 
% Twins = [b, c]
%
% Twins = [b]
% 
% Twins = [c]
% 
% Twins = []

--
  ^       Tim Menzies (a 1/2 doctor)              | 
 /"\__/\  AI Lab, Computer Science, Uni. NSW      | "Scientific progress
*       \ P.O. Box 1, Kensington, Australia, 2033 |  goes 'BOINK' ? "
 \  _  _/ +61-2-663-4576 (fax) +61-2-697-3940 (w) |    -- Hobbes
  \| ""   timm@cs.unsw.oz.au                      |            

>>>>> On 1 Nov 92 05:36:12 GMT, timm@spectrum.cs.unsw.oz.au (Tim
TM> Menzies) said: Nntp-Posting-Host: sienna.spectrum.cs.unsw.oz.au

In article <1992Nov1.053612.7414@usage.csd.unsw.OZ.AU> timm@spectrum.cs.unsw.oz.au (Tim Menzies) writes:

TM> From article <1992Oct29.140104.7751@coli.uni-sb.de>, by ulma@coli.uni-sb.de (Ulrich Mayring):
> Hello netters, I have a problem:
> 
> I have a list and need to recursively pick two elements out of it. I
> need every pair of elements in every order, however the order of the
> pair itself is not important. It should also be possible to pick an
> element and the [] as a pair, thus guaranteeing that in the end I
> will have every pair and every single element. Then I will test the
> pair (or single) and if it doesn't suit my purpose I want to go back
> into the recursion to get the next one.
> 
> 
> Thanx a lot if you can help,
> 
> 
>      Ulrich Mayring
> 
>        - Also wir waren mit grau eigentlich sehr zufrieden -     


TM> % no substitute for simplicity, i always say...

TM> twins(L,X) :- 	subset(L,X), (X = [_,_] | X = [_] | X = []).

TM> subset([],[]).
TM> subset([H|T],[H|REST]) :- subset(T,REST).
TM> subset([H|T],REST) :- subset(T,REST).   

Hi Tim,

On the other hand, if the set is large, then the amount of
backtracking that you will do will be horrendous, generating all
3,4,5,6,7,8... elements subsets, only to discard them later.

How about?

twins(L, pair(A,B)) :-
	member(A, L),
	member(B,L).
twins(L, pair(A,[])) :-
	member(A, L).

member(X, [X|_]).
member(X, [_|T]) :- member(X, T).

ulma@coli.uni-sb.de (Ulrich Mayring) writes:

>Hello netters, I have a problem:

>I have a list and need to recursively pick two elements out of it. I need
>every pair of elements in every order, however the order of the pair itself
>is not important. It should also be possible to pick an element and the []
>as a pair, thus guaranteeing that in the end I will have every pair and
>every single element. Then I will test the pair (or single) and if it doesn't
>suit my purpose I want to go back into the recursion to get the next one.

Well, since so many of you have answered, let me introduce the solution I
have finally decided on. Since I am a beginner it may not work in all circum-
stances, but it seems to in mine.

select(X,[X|R]),R).
select(X,[H|T],[H|R]) :- select(X,T,R).
select([],List,List).

Then my predicate goes something like select List A, select List B and then
append List A and List B. The last line in the select predicate appears to
generate the [] only when all other elements have been selected. When I 
have the pairs I test them and if they suit my purpose I append them to my
"Solution List", which is the reason why it is possible to have a pair of
the form (List,[]) represent only List, which has one element.

Thanx again to everybody,


     Ulrich Mayring

       - Also wir waren mit grau eigentlich sehr zufrieden -     

In article <PLUMMER.92Nov1091801@nutmeg.cs.swarthmore.edu> plummer@cs.swarthmore.edu (David Barker-Plummer) writes:

The original poster (Ulrich Mayring) wrote:
   > Hello netters, I have a problem:
   > 
   > I have a list and need to recursively pick two elements out of it. I
   > need every pair of elements in every order, however the order of the
   > pair itself is not important. It should also be possible to pick an
   > element and the [] as a pair, thus guaranteeing that in the end I
   > will have every pair and every single element. Then I will test the
   > pair (or single) and if it doesn't suit my purpose I want to go back
   > into the recursion to get the next one.
   > 
   > 
   > Thanx a lot if you can help,
   > 
   > 
   >      Ulrich Mayring
   > 
   >        - Also wir waren mit grau eigentlich sehr zufrieden -     

To this Tim Menzies replied:

   TM> % no substitute for simplicity, i always say...

   TM> twins(L,X) :- 	subset(L,X), (X = [_,_] | X = [_] | X = []).

   TM> subset([],[]).
   TM> subset([H|T],[H|REST]) :- subset(T,REST).
   TM> subset([H|T],REST) :- subset(T,REST).   


Of which David Barker-Plummer had the following to say:
   On the other hand, if the set is large, then the amount of
   backtracking that you will do will be horrendous, generating all
   3,4,5,6,7,8... elements subsets, only to discard them later.

   How about?

   twins(L, pair(A,B)) :-
           member(A, L),
           member(B,L).
   twins(L, pair(A,[])) :-
           member(A, L).

   member(X, [X|_]).
   member(X, [_|T]) :- member(X, T).


Now I say:

This will cause every pair to occur twice, since the order of the pair
was not important. A modified version:

   twins(L, pair(A,B)) :-
           member(A, L, RestOfL),
           member(B, RestOfL).
   twins(L, pair(A,[])) :-
           member(A, L).

   member(X, [X|_]).
   member(X, [_|T]) :- member(X, T).

   member(X, [X|Rest], Rest).
   member(X, [_|T],    Rest) :- member(X, T, Rest).

/Andreas
--
----------------------------------- < * > ------------------------------------
Andreas Kagedal                           Internet: andka@IDA.LIU.SE
Dep. of Computer and information science  UUCP: {uunet,mcsun,...}!liuida!andka
University of Linkoping, Sweden           BITNET: andka@SELIUIDA

In article <ANDKA.92Nov2103650@aste12.IDA.LiU.SE> andka@IDA.LiU.SE (Andreas Kagedal) writes:

AK> In article <PLUMMER.92Nov1091801@nutmeg.cs.swarthmore.edu> plummer@cs.swarthmore.edu (David Barker-Plummer) writes:

AK> The original poster (Ulrich Mayring) wrote:
UM> > Hello netters, I have a problem:
UM> > 
UM> > I have a list and need to recursively pick two elements out of it. I
UM> > need every pair of elements in every order, however the order of the
UM> > pair itself is not important. It should also be possible to pick an

AK> Now I say:

AK> This will cause every pair to occur twice, since the order of the pair
AK> was not important. A modified version:

Your criticism is completely correct, and your code works, although
the conventional name for your member/3 predicate is select/3.  I
interpreted "every pair of elements in every order" to mean that (a,b)
and (b,a) should both appear, although on closer insepection this
appears to be contradicted by the clause "the order of the pair itself
is not important".  I read this latter as meaning that it didn't
matter what order the pairs were produced.

-- Dave

In article <1992Oct29.140104.7751@coli.uni-sb.de> ulma@coli.uni-sb.de
(Ulrich Mayring) writes:

%  I have a list and need to recursively pick two elements out of it.  I
%  need every pair of elements in every order, however the order of the
%  pair itself is not important.  It should also be possible to pick an
%  element and the [] as a pair

The following code will do what you want.  The final requirement strikes
me as unusual; could you not extract single elements with member/2
(below) and if none of them suits you, get pairs with the first clause
only of pair/3 (below) ?

I have assumed that you don't want pairs such as (a,a) unless there are
actually two or more `a's in the list. 

Sample invocation

| ?- pair([a,b,c],A,B).

     A=a
     B=b ;

     A=a
     B=c ;

     A=b
     B=a ;

     A=b
     B=c ;

     A=c
     B=a ;

     A=c
     B=b ;

     A=a
     B=[] ;

     A=b
     B=[] ;

     A=c
     B=[] ;
no
| ?-

% ------------------------------------------------------------------------
%  Code: Ken Johnson, November 1992.  You may use and distribute this code
%  freely, but if you sell copies at a profit, I want a share. 

pair(L,A,B) :-
	member(A,L,L1),
	member(B,L1).
pair(L,A,[]) :-
        member(A,L).


member(X,[X|_]).
member(X,[_|T]) :-
	member(X,T).

member(X,[X|T],T).
member(X,[H|T],[H|U]) :-
	member(X,T,U).


-- 
//// Advice to dieters:         ////  Ken Johnson, A I Applications Institute
////   Never eat more than      ////       80 South Bridge, EDINBURGH EH1 1HN
////   you can carry.           ////                 E-mail ken@aiai.ed.ac.uk
////              -- Miss Piggy ////     phone 031-650 2756  fax 031-650 6513

In article <PLUMMER.92Nov2210156@nutmeg.cs.swarthmore.edu> plummer@cs.swarthmore.edu (David Barker-Plummer) writes:

	[About selecting pairs, using member/2 or select/3.]

   Your criticism is completely correct, and your code works, although
   the conventional name for your member/3 predicate is select/3.  I
   interpreted "every pair of elements in every order" to mean that (a,b)
   and (b,a) should both appear, although on closer insepection this
   appears to be contradicted by the clause "the order of the pair itself
   is not important".  I read this latter as meaning that it didn't
   matter what order the pairs were produced.

More significantly (perhaps!) Dave's code would produce pair(X,X) for
every X that appeared just once in the list, whereas the select-based code
wouldn't.

Who knows which the original poster wanted!

--
				Bernard Silver
				GTE Laboratories
				bsilver@gte.com
				(617) 466-2663