I’ve just stumbled upon this problem on the net. It kind of goes something like this.
There are corporations that have stakes in other corporations. And I would like to find out if one company owns another company.
So, the problem is this, if company 1 owns more than 75% of company 2, he automatically owns it. And another twist is that if company 1 owns more than 75% of company 3 that owns more than 75% of company 2, then company 1 owns company 2.
Here’s a clearer example:
Company 1 owns 50% of Company 2 Company 1 owns 75% of Company 3 Company 3 owns 25% of Company 2 Therefore, Company 1 owns Company 2
I think it will involve recursion, splitting the ownership process by company. However, I can’t figure out how to implement this. Thank you very much for your help!
*Update : Sorry for not properly defining the problem. The problem consists of records, containing three pieces of data, as seen above, and the problem is to find out if a certain company owns another (eg does company 1 own company 2?).
So I’m planning to store each ownership value to the owner (for direct ownership) and reduce the ownership value of indirect owners (if own > 75%, then replace w/ next owner) until it reaches the base. Thanks for the suggestions!
I make no assumption on the list, how long it can be and how many companies are involved. I also make no assumption that all companies are linked. It is possible the list can form many distinct ownership graph. I also assume it is possible for scenarios allowing some form of mutual ownership (A own 75% of B and B own 75% of A, strange situation I’ll admit but mathematically there is nothing preventing this from happening)
A Brute Force algorithm to solve absolute ownership could be done this way :
First pass – Determine all associations of a company with other companies.
Let C be the company of interest Let A be the list of companies C has associations with. Let Astar be a list of companies not already visited, initially containing C. Let dist be the distance of companies from C, initially set to 0. While Astar is not empty Let X be the first in Astart, remove X from Astar Add X to A dist++ For each company Y that X has stakes in if Y is not in Astar, Set Y.dist = dist Add Y to Astar
Now we have a list (A) of companies that C can potentially own, all other companies in the original list can be ignored.
now let’s calculate the actual ownership. Here we attempt to calculate the actual stakes C has in all other companies. If C owns 50% of X and X owns 50% of Y then C owns 25% of Y. To take into account the 75% rule, if at any point a company has 70% or more stakes in another we automatically convert the 75% into 100%.
Let X be an array containing the stakes X has in all other companies within A, initially set to 0 For each company in A Let X be the company the furthest away from C not already visited in A. Mark X as visited. For each edge E leading away from X to company Y if the Y is marked visited in A For each edge F leading away from Y to company Z Set X[Z] = F * E If X[Z] >= 75% Set F = 100% remove visited mark on X else For each company W that Y has stakes in Set X[W] = Y[W] * E
This will perform a sort of backtracking algorithm that will re-evaluate stakes when ownership is established. At the end you should have the array C with all the net stakes C has in all other companies. If any are above 75% then C owns it.
This is a very brute algorithm, it would be preferable to merge the two passes into one to make it a more elegant solution though at this point I prefer getting proof of something that works rather than something that looks or performs good. I have not tried it, only ran it mentally so I could be very wrong. However I think it would cover the mutual ownership cycles. However to see the mutual ownership you would have to repeat the procedure replacing C for every company in the list. Then you would have a complete picture of ownership directly visible from each company.
— EDIT —
I hope I did not misunderstand here, the question is indeed hard to fully grasp. If we have a large set of companies and ownership is defined in triplets then you could do as below by letting the list be all the triplets bundled together. This would create a larger graph but solving one graph is much easier than solving a set of interdependent graphs