How to check that there is no more than a double in a list
| Author |
Message |
|
Thomas Baruch
#1 / 8
|
 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 |
|
 |
|
Daniel Dudle
#2 / 8
|
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 |
|
|
|
Katiusci
#3 / 8
|
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 |
|
|
|
Bart Demoe
#4 / 8
|
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 |
|
|
|
Remko Tronco
#5 / 8
|
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 |
|
|
|
John Fletche
#6 / 8
|
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 |
|
| |
|
