5 replies to this topic

[itsbrian]

In testing if one set is a subset of another (with duplicate elements) i have:

?- subset([119, 101, 101], [119, 101, 108, 108]).


Yes

Since there are two occurences of '101' in the first set but only one occurence of '101' in second set, i require a test to fail this situation. It's true that the first set is a subset of second set however, i wish to add a clause so it fails for a situation such as this. The number of occurences of each element in first set must match the number of occurences in second set.

The psuedo code below for 'unique_element_count(A, B)'
is where some good code is needed:

test_subset(A, B) :-

  subset(A, B),

  length(A, C),

  length(B, D),

  successor(C, D),

  unique_element_count(A, B).


% List B is one element longer than List A

successor(A, B) :-

  B is A+1.


unique_element_count(A, B) :-

% the number of occurences of any particular element in A must not be

% greater than the number of occurences of that particular element also

% found in B.


% i.e. for each unique element identified in A the count is not > count of

% that particular element also found in B

Perhaps there's already an inbuilt predicate that im unaware of? If i work it out in the meantime ill post my own solution, but i've been programming for hours without a break and then just when my program seemed to be working fine i realized this problem and now i'm too weary and can't think clearly! :sleep:

Thanks for helping me out.

[pater]

I think the only way to solve this problem is to go through the first list element by element and remove each element from the second list. If at one point, you can't find a matching element in B, the test fails, if A gets empty before this happens, the subset condition is met. The task will be simpler if you can assume both lists are sorted (but I doubt you can...).
BTW: Why do you check for the size of the lists? Is it part of the exercise that B always has one element more than A?

[itsbrian]

pater said:

I think the only way to solve this problem is to go through the first list element by element and remove each element from the second list. If at one point, you can't find a matching element in B, the test fails, if A gets empty before this happens, the subset condition is met. The task will be simpler if you can assume both lists are sorted (but I doubt you can...).
BTW: Why do you check for the size of the lists? Is it part of the exercise that B always has one element more than A?

That would do it and yes the lists will not be sorted as they arrive, but a sorting tast could be implemented if necessary and since it's only a test condition the sorting would not make any permanenet changes to the lists, although i guess it may slow it down a very tiny fraction. The reason i check for the size of the list is for another condition (not necessary to solve this task, yet it's a necessary condition in the overall program so i thought mentioning it may make things clearer).

Thanks for your thoughts it all helps.


Here's the code so far, it's almost there apart from the problem of unsorted lists, if it weren't for that i think the following code would be ok. (Note 'move' is the real name of the predicate 'test_subset' was the name used before and element_count is not a good name but will do for now).

move(A, B) :-

  subset(A, B),

  length(A, C),

  length(B, D),

  successor(C, D),

  element_count(A, B).


element_count(A, B) :-

  subtract(B, A, Result),

  length(Result, L),

  L is 1.


% subtract(+Set, +Delete, -Result)

%     Delete  all  elements  of set  `Delete'  from  `Set' and  unify  the

%     resulting set with `Result'.

Some other variations with unsorted problems (for a general picture) are:

alt_element_count(A, B) :-

  member(X, A),

  member(X, B),

  delete(A, X, Y),

  delete(B, X, Z),

  length(Y, Ly),

  length(Z, Lz),

  Ly is 0,

  Lz is 1.


% delete(+List1, ?Elem, ?List2)

%     Delete all members  of List1 that simultaneously unify with Elem and

%     unify the result with List2.

....or this:

alt2_element_count([], B) :-

  length(B, L),

  L is 1.


alt2_element_count(A, B) :-

  member(X, A),

  remove(B, X, ResultB),

  remove(A, X, ResultA),

  alt2_element_count(ResultA, ResultB).


% remove(X,L,R)  :<=> by removing one occurrence of X

%                     from L one obtains R

The last two versions don't work as they are (something wrong in my logic), the first version 'subtract' seems more promising, it uses sets and seems much more elegant (apart from unordered/unsorted lists problem), if i could sort that problem out it would be nice; then again perhaps the last two will end up convincing me they are more on track?

Here's the output of first version which tests the difference between sets:

?- element_count([119, 101, 101], [119, 101, 101, 108]).


Yes

?- element_count([119, 101, 108], [119, 101, 101, 108]).


No.........order matters

Any more help appreciated.

Thanks

[itsbrian]

New approach: Combinatorics to the rescue once again!

Using 'varia(Length_subWord, Word, Subword)', tests weather or not
'SubWord' can be created from 'Word'; if it can be then it's true that 'SubWord' exists in 'Word'.

varia(0, _, []).

varia(A, C, [B|F]) :-

  A>0,

  D is A-1,

  delete(B, C, E),

  varia(D, E, F).


?- varia(2, [a,b,c], X).


X = [a, b] ;


X = [a, c] ;


X = [b, a] ;


X = [b, c] ;


X = [c, a] ;


X = [c, b] ;


No


% For example: To test if 'b r i a n' exists in 'b a r i n y':


?- varia(5, [b, a, r, i, n, y], [b, r, i, a, n]).


Yes

Basically my problem is solved it's just a matter of implementing this, since varia is already in my code it should be no problem.

Therefore my original problem (passed the test when not required to do so):

?- subset([119, 101, 101], [119, 101, 108, 108]).


Yes

Can rather be tested using the following (fails the test as required to do so).

?- varia(3, [119, 101, 108, 108], [119, 101, 101]).


No

Similarly tests which aught to pass do:

?- varia(3, [119, 101, 108, 108], [119, 101, 108]).


Yes

But if anyone solves it another way i'm interested to see it, because i think my way is going to slow down my program a hell of a lot!

cheers :yes:

[Trap D]

Do you use SWI-Prolog ?
In SWI-Prolog, sets don't have duplicates, so the predicates on sets don't work there.
A solution, already given by pater, could be that :

my_subset([], _) :- !.


my_subset([H | T], L1) :-

	member(H, L1), !,

	select(H, L1,L2),

	my_subset(T,L2).


my_subset(_,_) :- fail.

[itsbrian]

Yes i'm using SWI-Prolog. Thanks for pasting your code i prefer it to mine, it's working fine. It's also interesting how the 'select(H, L1,L2)' clause handles duplicates. My program is working almost 100% but has a few bugs to sort out in the overall frame. Each predicate works fine alone but together becomes more difficult to find bugs for example invalid input etc (which im working on). I don't have much experience with debuggers.

Hopefully soon i will have it ready enough so that i may implement a java to prolog interface (JPL). I've tried the examples provided in the JPL package and with some carefull thought of how i might better separate the application logic from the user view logic that i should be able to implement it. It's a worthwhile learning experience i think.

http://www.swi-prolo.../jpl/index.html

http://optusnet.dl.s...pl-1.0.1.tar.gz