OT: construct list of literals from a set of literal pairs

[Hugo Ferreira]

Hello,

I have a seemingly very simple problem which I think has
a solution, but I cannot seem to solve this. Here
it is:

Assume we have a clause consisting of the literals:

p1(X), p1(Y), p2(X,Y)

I have decomposed this clause into
all its n(n-1)/2 pairs:

p1(X), p1(Y)
p1(X), p2(X,Y)
p1(Y), p2(X,Y)

Now I would like to use the above pairs
to reconstruct my original clause.

Question: How may one do this?

I have been looking at this for several
weeks and am truly stumped. Simply matching
the literals with unification won't work.

Any help is greatly appreciated.

TIA,
Hugo F.



_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Bart Demoen-2]

[on purpose (partially) quoting you in a different order than you wrote it]

> n(n-1)/2 pairs:
>
> p1(X), p1(Y)
> p1(X), p2(X,Y)
> p1(Y), p2(X,Y)
>
> Now I would like to use the above pairs
> to reconstruct my original

If there were no variables involved, like in

   a,b
   a,c
   b,c

would you be able to reconstruct (a,b,c) ?

If yes: get rid of the notion of variables (by grounding* for instance)
    and use your method
If no: why not ?

Can you state the problem more generally than "we have a clause
consisting of the literals" ? It feels like you have C_n^2 of tuples
and want to construct a set (or must it be a sequence ?) of n
elements - maybe stating the problem in a more general setting could
help to solve it ? [read Polya if you have weeks to spare]

*grounding can be done with numbervars

BTW, the problem you show us, is interesting and not trivial - can you
tell us also where it comes from ?

Cheers

Bart Demoen

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Hugo Ferreira]

Hello,

Bart Demoen wrote:

> [on purpose (partially) quoting you in a different order than you wrote it]
>
>> n(n-1)/2 pairs:
>>
>> p1(X), p1(Y)
>> p1(X), p2(X,Y)
>> p1(Y), p2(X,Y)
>>
>> Now I would like to use the above pairs
>> to reconstruct my original
>
> If there were no variables involved, like in
>
>    a,b
>    a,c
>    b,c
>
> would you be able to reconstruct (a,b,c) ?
>

Yes. Start with any pair as an initial result.
Scan all other pairs. Each time we add a new pair
attempt to match one of its members to an existing
element in the result. We have the following cases:
a) We match the first element -> add the second to the result
b) We match the second element -> add the first to the result
c) Both are matched -> do nothing

Example:

              b, c
+ a, c   ->  b, c, a
+ a, b   ->  b, c, a (do nothing)


> If yes: get rid of the notion of variables (by grounding* for instance)
>     and use your method

Cannot seem to do this.

> If no: why not ?
>

More general explanation is required.

> Can you state the problem more generally than "we have a clause
> consisting of the literals" ? It feels like you have C_n^2 of tuples
> and want to construct a set (or must it be a sequence ?) of n
> elements - maybe stating the problem in a more general setting could
> help to solve it ?

I have a list of clauses. Each clause expresses a state transition.
I want to convert this data into a list of pairs that allows me to
perform frequency/support counting of any possible subsets of literals
that occurs in this list. Example: what is the frequency of <a,b> in
the clauses [a,b,c], [b,c], [a,c] (in this case 1). For <a> we have 2.

In addition to this, each clause may have repeated propositions.
Example: [a, a, b, b]. The support <a,b> in this case is 2.

Now the reason for the variables....

Assume we have a state transition:

[ a(X,Y), a(X',Y'), b(X,Y), b(X',Y') ]

I can express any such clause compactly:
- By generating all n(n-1)/2 pairs
- I only retain pairs that are linked
   (related via at least one variable)
   (I don't need all n^2 pairs because
    link relation is symmetrical)
- The frequency of any subset is equal to the
   frequency of all pairs that make it up

So I can express the above transition as:

- a(X,Y), b(X,Y) with 2 occurrences
- Note that I store the variants only to allow for compact storage
- To count the subset a(X,Y), b(X,Y) I need only determine in
   what transition this pair occurs and how many times.
- Subsets may consist of several such pairs

So I cannot get rid of the variables.

> [read Polya if you have weeks to spare]
>

Its on my to-do list for several years no 8-(

> *grounding can be done with numbervars
>
> BTW, the problem you show us, is interesting and not trivial - can you
> tell us also where it comes from ?
>

Data mining for my PhD work. I need an efficient way of determining the
frequency of any subset of literals that occur in the list of clauses.
The issue here is that this data has many of the same sub-sets within
each clause repeated many times. The objective is to compactly store
this information as pairs. Mine the most frequent pairs and then convert
the result back to a set of (most frequent) literals as expressed in the
original data set.

Thank you for the feedback.
Any comments or suggestion appreciated.

Regards,
Hugo F.

> Cheers
>
> Bart Demoen
>
> Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
> _______________________________________________
> SWI-Prolog mailing list
> SWI-Prolog@...
> https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog
>

_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Bart Demoen-2]

> > If yes: get rid of the notion of variables (by grounding* for instance)
> >     and use your method
>
> Cannot seem to do this.

numbervars/3

> a) We match the first element -> add the second to the result
> b) We match the second element -> add the first to the result
> c) Both are matched -> do nothing

Make sure you use the first and the second, even if also the third
applies, otherwise you will not be able to reconstruct a,a,a
from a,a and a,a

Cheers

Bart Demoen

Disclaimer: http://www.kuleuven.be/cwis/email_disclaimer.htm
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Richard O'Keefe]

On Oct 11, 2009, at 6:32 AM, Hugo Ferreira wrote:

> Assume we have a clause consisting of the literals:
>
> p1(X), p1(Y), p2(X,Y)
>
> I have decomposed this clause into
> all its n(n-1)/2 pairs:
>
> p1(X), p1(Y)
> p1(X), p2(X,Y)
> p1(Y), p2(X,Y)
>
> Now I would like to use the above pairs
> to reconstruct my original clause.
>
> Question: How may one do this?

Would you get the same set of pairs from
p1(Y), p1(X), p2(X, Y)?

If so, you can't.

On the other hand, if the process of taking a clause and returning
a collection of pairs (a) preserves order and (b) doesn't remove
duplicate pairs, so that write(*), write(*), write(*) is OK, then
it's clear that there is only a finite number of ways to recombine
the pairs without introducing new pairs, so it can be done.

However, it's also clear that it's going to take exponential time.

So the obvious question is "why are you doing this?"
And another is like it "Are there any additional constraints you
could take advantage of?"


_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Hugo Ferreira]

Hello,

Richard O'Keefe wrote:

>
> On Oct 11, 2009, at 6:32 AM, Hugo Ferreira wrote:
>> Assume we have a clause consisting of the literals:
>>
>> p1(X), p1(Y), p2(X,Y)
>>
>> I have decomposed this clause into
>> all its n(n-1)/2 pairs:
>>
>> p1(X), p1(Y)
>> p1(X), p2(X,Y)
>> p1(Y), p2(X,Y)
>>
>> Now I would like to use the above pairs
>> to reconstruct my original clause.
>>
>> Question: How may one do this?
>
> Would you get the same set of pairs from
> p1(Y), p1(X), p2(X, Y)?
>

Yes, in a different order.

> If so, you can't.
>

In other words if for any given set of pairs I can generate two or
more valid results and I cannot discern between them which is the
original then I cannot reconstruct the it. The above is not a
valid counter example though, they are variants.

> On the other hand, if the process of taking a clause and returning
> a collection of pairs (a) preserves order and

It does.

> (b) doesn't remove duplicate pairs, so that
 > write(*), write(*), write(*) is OK,

It doesn't remove duplicates.

> then it's clear that there is only a finite number of ways to recombine
> the pairs

Clear.

> without introducing new pairs, so it can be done.
>

Not clear. How can we show this?

> However, it's also clear that it's going to take exponential time.
>
> So the obvious question is "why are you doing this?"

To be honest I figured the inverse transform could be done in
polynomial time if I kept the order of the process. This is
not the case.

Later I figured an exponential search may be viable via pruning
by searching for clauses with a minimum of literals and
variables (branch and bound). This may not be true. A trivial
solution may be possible other than the intended original.
I am still looking at this.

> And another is like it "Are there any additional constraints you
> could take advantage of?"
>

Unfortunately not. The unknown clause is just a conjunct
of literals.

Thank you for the feedback,
Hugo F.


>
> _______________________________________________
> SWI-Prolog mailing list
> SWI-Prolog@...
> https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog
>

_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog