How to check that there is no more than a double in a list 
Author Message
 How to check that there is no more than a double in a list

Brest, le mercredi 21 novembre

Hi, I'd like to know what could be a quicker way to do that:

  max1double(X) :-
    select(A,X,Y),
    member(A,Y),!,
    \+(max1double(Y)).

I'm using GNU prolog, and I can't use features like list_to_set, etc.
My puropose is to see if there are two identical vars but no more
(not three identical, not several times two identical, etc.)
[0,0,1,2,3] is good
[0,0,1,1,2] is bad
[0,0,0,1,2] is bad
(the list can have very different lengths). Priority is quickness.

--
QlpoOTFBWSZTWcwiz1oAAC1fgHQTwOeABVAABAT7Zp4lMAC4hET1DQNGhoBoyGaQYyaZAyaG
QZGmBGDTJE01NMTJkZDQaAUhm7W8Wu9WYGQZg2Vd+s8PsaiAZJoF5jaDsEQUaCEQHgnxdw5H
siRDfoqLyg4gHe6/TCLCgm0gY3zjVSswgknIk85qBbV7GNcqz8yWcUOcrT4SlYICcQUgKxM2
gumlEIhPgCSCC4gUHVb3pREx/vdlGkW5r2P5Z+LuSKcKEhmEWetA | mimencode + bzip2



Mon, 10 May 2004 04:37:56 GMT  
 How to check that there is no more than a double in a list

Quote:
> Brest, le mercredi 21 novembre

> Hi, I'd like to know what could be a quicker way to do that:

>   max1double(X) :-
>     select(A,X,Y),
>     member(A,Y),!,
>     \+(max1double(Y)).

> I'm using GNU prolog, and I can't use features like list_to_set, etc.
> My puropose is to see if there are two identical vars but no more
> (not three identical, not several times two identical, etc.)
> [0,0,1,2,3] is good
> [0,0,1,1,2] is bad
> [0,0,0,1,2] is bad
> (the list can have very different lengths). Priority is quickness.

> --
> QlpoOTFBWSZTWcwiz1oAAC1fgHQTwOeABVAABAT7Zp4lMAC4hET1DQNGhoBoyGaQYyaZAyaG
> QZGmBGDTJE01NMTJkZDQaAUhm7W8Wu9WYGQZg2Vd+s8PsaiAZJoF5jaDsEQUaCEQHgnxdw5H
> siRDfoqLyg4gHe6/TCLCgm0gY3zjVSswgknIk85qBbV7GNcqz8yWcUOcrT4SlYICcQUgKxM2
> gumlEIhPgCSCC4gUHVb3pREx/vdlGkW5r2P5Z+LuSKcKEhmEWetA | mimencode + bzip2

Does the rubbish at the end of your messages have a purpose?

Daniel



Mon, 10 May 2004 05:00:55 GMT  
 How to check that there is no more than a double in a list


Quote:
> Brest, le mercredi 21 novembre

> Hi, I'd like to know what could be a quicker way to do that:

>   max1double(X) :-
>     select(A,X,Y),
>     member(A,Y),!,
>     \+(max1double(Y)).

Hi,
max1double(X,Count) :-
     select(A,X,Y),
     member(A,Y) ,
    Count is Count + 1,
( Count>0) -> "List is bad";
              max1double(Y,Count).

Bye

Quote:

> I'm using GNU prolog, and I can't use features like list_to_set, etc.
> My puropose is to see if there are two identical vars but no more
> (not three identical, not several times two identical, etc.)
> [0,0,1,2,3] is good
> [0,0,1,1,2] is bad
> [0,0,0,1,2] is bad
> (the list can have very different lengths). Priority is quickness.

> --
> QlpoOTFBWSZTWcwiz1oAAC1fgHQTwOeABVAABAT7Zp4lMAC4hET1DQNGhoBoyGaQYyaZAyaG
> QZGmBGDTJE01NMTJkZDQaAUhm7W8Wu9WYGQZg2Vd+s8PsaiAZJoF5jaDsEQUaCEQHgnxdw5H
> siRDfoqLyg4gHe6/TCLCgm0gY3zjVSswgknIk85qBbV7GNcqz8yWcUOcrT4SlYICcQUgKxM2
> gumlEIhPgCSCC4gUHVb3pREx/vdlGkW5r2P5Z+LuSKcKEhmEWetA | mimencode + bzip2



Mon, 10 May 2004 15:21:35 GMT  
 How to check that there is no more than a double in a list

Quote:

> Hi, I'd like to know what could be a quicker way to do that:

>   max1double(X) :-
>     select(A,X,Y),
>     member(A,Y),!,
>     \+(max1double(Y)).
> (the list can have very different lengths). Priority is quickness.

I don't know about speed, but you can certainly obtain a better complexity and if your
lists are very long, that might pay off: sort the list without removing duplicates, then scan
it once.
You might even modify a merge sort so that it detects early that there are too many
duplicates and gain speed.

Bart Demoen



Mon, 10 May 2004 16:06:57 GMT  
 How to check that there is no more than a double in a list
:  max1double(X) :-
:    select(A,X,Y),
:    member(A,Y),!,
:    \+(max1double(Y)).

Try sorting your list first (O(n log n)). Then, checking for more than 2
doubles can be done by traversing your list linearly (O(n)).

Remko



Mon, 10 May 2004 16:07:55 GMT  
 How to check that there is no more than a double in a list

Quote:
> Brest, le mercredi 21 novembre

> Hi, I'd like to know what could be a quicker way to do that:

>   max1double(X) :-
>     select(A,X,Y),
>     member(A,Y),!,
>     \+(max1double(Y)).

> I'm using GNU prolog, and I can't use features like list_to_set, etc.
> My puropose is to see if there are two identical vars but no more
> (not three identical, not several times two identical, etc.)
> [0,0,1,2,3] is good
> [0,0,1,1,2] is bad
> [0,0,0,1,2] is bad

If identical terms are always contiguous, as in your test data, you should
traverse the list, and fail as soon as a second pair of values is found:

max1double( [H|T] ) :-
    max1double1( T, H ).

max1double1( [H|T], X ) :-
    ( H == X ->
        max1double2( T, X )
    ; otherwise ->
        max1double1( T, H )
    ).

max1double2( [], _X ).
max1double2( [H|T], X ) :-
    H \== X,
    max1double2( T, H ).

If they're not contiguous, e.g. [0,1,2,3,0], you could use the built-in
sort:

max1double( X ) :-
    sort( X, Y ),
    shorter_by_one( Y, X ).

shorter_by_one( [], [_] ).
shorter_by_one( [_|T0], [_|T1] ) :-
    shorter_by_one( T0, T1 ) .

--
Regards

John Fletcher



Mon, 10 May 2004 17:22:38 GMT  
 
 [ 8 post ] 

 Relevant Pages 

1. I am using activex and everytime I save my vi it doubles in size

2. Checking AM or PM

3. I am stuk CHECK my Code - access.txt (0/1)

4. Double-checking a Program

5. Double list

6. Double list -Reply

7. Clarion Magazine Goes To Double Opt-In Email List

8. Removin doubles from a list

9. Queue (double linked list?)

10. Can double-linked lists be implemented in scheme?

11. How to remove doubles in a list ?

12. Need guide on double linked list.

 

 
Powered by phpBB® Forum Software