Vlad,
Thanks for your below reply of Tue 10/21/2008 2:17 PM. I have spend hours trying to understand your explanation, and I now think I understand much of it, but not all of it. I have copied much of it word for word below and have inserted my questions about its various portions. If you could answer the following questions I might understand all of it. If your formula works, it is important, and if possible I would like to understand it Thank you! =========quote from Vlad's reply with my comments============ =====Vlad================ C(N,S) is the total number of assemblies of size S that fit in the N nodes, if you forget about overlaps. Each assembly overlaps in X places with other C(S,X)*C(N-S,S-X) assemblies: if another assembly overlaps with our assembly in X places, then X nodes are inside S nodes of our assembly, which gives C(S,X) possible combinations, [=====EWP================: --I understand this --- for any first given set of S nodes, there would be C(S,X) different sub-combinations of X node from that given set of S nodes] =====Vlad================ and the remaining S-X of the nodes are outside the assembly, in remaining N-S nodes, which gives C(N-S,S-X) combinations, [EWP================: --I interpret this as saying: for a given fixed sub-combination of X nodes from the many possible such subcombinations C(S,X), let us determine the number of combinations C(N-S, S-X) of length S-X that can be created from the N nodes minus the S nodes in the first given set, and that can be added to said given combination of X nodes to create different sets of length S --- is this correct?] =====Vlad================ totaling to C(S,X)*C(N-S,S-X). [=====EWP================: --I interpret this as saying: --sum the following over each of the sub-combinations C(S,X) of length X that can be selected from the first given set of S nodes, -----the number of each possible combination C(N-S,S-X) of length S-X, described above, that when added to the X nodes from a given one of such sub-combinations would form another set of length S --this was counter intuitive to me at first, because I subconsciously rejected the notion that each sub-combination of X nodes from the first given set of length S could occur in all C(N-S,S-X) possible complimentary combinations of length S-X, so I kept thinking there must be something wrong with it, but now I realize there is no reason they shouldn't be allowed to --For each given sub-combination of X node in the first given set of length S, all other sets of length S are complementary and include the same sub-combination of X nodes. --Am I correct in assuming that over all possible sub-combinations of X nodes in the first given set of length S, all possible sets of length S that have an exact overlap of length X with the first given set will be counted?] =====Vlad================ Thus, the total number of assemblies that overlap with our assembly in O to S places (including our assembly itself) is T(N,S,O)= C(S,S)*C(N-S,S-S)+ C(S,S-1)*C(N-S,S-(S-1))+ ..+C(S,O)*C(N-S,S-O) [=====EWP================: --this is equivalent to the formula for T(N,S,O) that I used in my spread sheet that I derived from your email of Thu 10/16/2008 7:50 pm, after having switched the positions of the combination function variables --I have rewriten this formula below to make its structure easier to see at a glance T(N,S,O)= +C(S, S-0)*C(N-S, 0) (= 1) +C(S, S-1)*C(N-S, 1) +C(S, S-2)*C(N-S, 2) +... +C(S, O)*C(N-S, S-O) OR T(N,S,O) = SUM FROM X = 0 TO S-O OF C(S, S-X)*C(N-S, X) Comparing this to C(S,X)*C(N-S,S-X) --- it appears that T(N,S,O) is equal to the number of all combinations calculated by C(S,X)*C(N-S,S-X) where X is greater than O, Thus it is an attempt to enumerate all such combinations in which the overlap is more than O and thus which should be excluded from A. --Thus it would seem A should equal C(N,S) - T(N,S,O), not C(N,S) / T(N,S,O). Why isn't this correct] =====Vlad================ Let's apply a trivial algorithm to our problem, adding an arbitrary assembly to the working set merely if it doesn't conflict with any of the assemblies already in the working set. Adding a new assembly will ban other T(N,S,O) assemblies from the total pool of C(N,S) assemblies, thus each new assembly in the working set lowers the number of remaining assemblies that we'll be able to add later. Some assemblies from this pool will be banned multiple times, but at least C(N,S)/T(N,S,O) assemblies can be added without conflicts, Since T(N,S,O) is the maximum number of assemblies that each one in the pool is able to subtract from the total pool of assemblies. [=====EWP================: --I don't understand this. --First, yes, each new assembly of length S added to the working set lowers the number of remaining assemblies that we'll be able to add later, but adding a given new assembly will ban not T(N,S,O) assemblies, but rather only all those assemblies that overlap with it by more than O nodes. --Second, what are the cases where assemblies will be banned multiple times that you mentioned in the above text? --Third --- as mentioned in my last group of comments --- why doesn't A = C(N,S) - T(N,S,O), since C(N,S) is the total number of combinations of length S that can be formed from N nodes, and T(N,S,O) appears to enumerate all the combinations that occur with each possible overlap value greater O. Why do you think division of C(N,S) by T(N,S.O) is appropriate. --Fourth, is it correct to assume that T(N,S,O) is a complete enumeration of all the possible combinations sets of size S that all overlap each other by more than O? --Fifth, is possible that even though T(N,S,O) appears to enumerate all possible combinations in which all sets overlap by more than O, that it fails to take into account possible combinations of sets of size S in which some sets overlap by more than O and others do not? --in which case T(N,S,O) would be smaller than the number of all prohibited combinations of sets of length S. Or would all the possible sets of length S which overlap be have been properly taken into account in the above formula for T? --Sixth, if C(S,X)*C(N-S,S-X) enumerates all possible combinations having an overlap of X, why can't one calculate A as follows? A = SUM FROM X = 0 TO O OF C(S,X)*C(N-S,S-X) =========end of quote from Vlad's reply with my comments============ Sorry for asking so many questions, but, as I said above, if your formula is correct, I think it is quite important, and I would like to understand it. And if it has limitations, or if it could use corrections, I would like to know what they are. Thank you again for your time. Ed Porter -----Original Message----- From: Vladimir Nesov [mailto:[EMAIL PROTECTED] Sent: Tuesday, October 21, 2008 2:17 PM To: agi@v2.listbox.com Subject: Re: [agi] Who is smart enough to answer this question? C(N,S) is the total number of assemblies of size S that fit in the N nodes, if you forget about overlaps. Each assembly overlaps in X places with other C(S,X)*C(N-S,S-X) assemblies: if another assembly overlaps with our assembly in X places, then X nodes are inside S nodes of our assembly, which gives C(S,X) possible combinations, and the remaining S-X of the nodes are outside the assembly, in remaining N-S nodes, which gives C(N-S,S-X) combinations, totaling to C(S,X)*C(N-S,S-X). Thus, the total number of assemblies that overlap with our assembly in O to S places (including our assembly itself) is T(N,S,O)= C(S,S)*C(N-S,S-S)+ C(S,S-1)*C(N-S,S-(S-1))+ ..+ C(S,O)*C(N-S,S-O) Let's apply a trivial algorithm to our problem, adding an arbitrary assembly to the working set merely if it doesn't conflict with any of the assemblies already in the working set. Adding a new assembly will ban other T(N,S,O) assemblies from the total pool of C(N,S) assemblies, thus each new assembly in the working set lowers the number of remaining assemblies that we'll be able to add later. Some assemblies from this pool will be banned multiple times, but at least C(N,S)/T(N,S,O) assemblies can be added without conflicts, since T(N,S,O) is the maximum number of assemblies that each one in the pool is able to subtract from the total pool of assemblies. -- Vladimir Nesov [EMAIL PROTECTED] http://causalityrelay.wordpress.com/ ------------------------------------------- agi Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/ Modify Your Subscription: https://www.listbox.com/member/?&; Powered by Listbox: http://www.listbox.com ------------------------------------------- agi Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/ Modify Your Subscription: https://www.listbox.com/member/?member_id=8660244&id_secret=117534816-b15a34 Powered by Listbox: http://www.listbox.com
