Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

How to calculate a union

• To: mathgroup at smc.vnet.net
• Subject: [mg104434] How to calculate a union
• From: Ramiro <ramiro.barrantes at gmail.com>
• Date: Sat, 31 Oct 2009 01:54:00 -0500 (EST)

Hi,

I am trying to compute the probability of a union, the formula
requires to sum and subtract all possible combinations of
intersections for all pairs, triplets, etc.  When n is big, getting
all the terms is a challenge.  Otherwise, I can easily compute any
given intersection.

ex. P(AUBUC) = P(A) + P(B) + P(C) - (P(A,B)+P(A,C)+P(B,C)) + P(A,B,C)

(you can see the idea of the general formula in
http://mathworld.wolfram.com/Inclusion-ExclusionPrinciple.html )

If I try to compute this directly, I run out of memory given the large
number of terms.
My approach was to write all possible combinations in a file or files:
all duplets, all triplets, all quadruplets, etc.   Then read each line
sequentially and calculate as well add or subtract the intersection of
each tuple as necessary.  Does anybody have any other suggestions?  I
hope that I am explaining myself, I am a bit afraid too that there are
just too many terms.

Question:
I am trying to export strings into different files.  It looks that
when Export is within a loop, the files are not actually created until
the loop is finished.  Is there a way the files can be written
immediately?

MORE DETAILS IF NEEDED
My logic is as follows:

i=1, list = {1,2,3,....n}
for i>1
    read previous list of tuples of length (i-1)
    for each tuple, append values greater than the value in the last
position of the tuple and thus create a new list of tuples of size i
    write a file with the results
    do the same for i+1

example (n=5):
for i=2
{1, 2} {1, 3} {1, 4} {1, 5} {2, 3} {2, 4} {2, 5} {3, 4} {3, 5} {4, 5}

i=3
{1, 2, 3} {1, 2, 4} {1, 2, 5} {1, 3, 4} {1, 3, 5} {1, 4, 5} {2, 3, 4}
{2, 3, 5} {2, 4, 5} {3, 4, 5}


Code:
sendToFile[val_, i_] := Module[{str},
   Export[ToString[i + 1] <> ".list", val, "List"];
   ];
u = Range[5];
sendToFile[{#} & /@ u, 0];
addGreater[u_, i_] :=
 With[{z = Select[u, # > i[[-1]] &]}, Append[i, #] & /@ z]
createList[n_, u_] :=
 Module[{l = ReadList[ToString[n - 1] <> ".list"]},
  With[{k = Flatten[addGreater[u, #] & /@ l, 1]}, sendToFile[k, n -
1]]
  ]
For[i = 2, i <= Length[u], i++, createList[i, u]]