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/?member_id=8660244&id_secret=117534816-b15a34 Powered by Listbox: http://www.listbox.com
