Corporation Stake Problem

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开发者_Python百科 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

I think the following works, but I didn't thoroughly test it. Frankly I'm not sure I even understand your requirements.

Construct a directed graph based on the input. Each named company becomes a vertex. Each edge represents an ownership relationship between companies and has a weight equal to the ownership percentage.

To determine which companies are owned by a specific company, use the following pseudocode:

Let company C be the company of interest
Let T be a table of all companies and their total ownership by company C
Let S be the set of companies completely owned by C, initially containing only C itself

While S is not empty:
    Choose an unvisited company X from S
    Mark X as visited
    For each edge leading away from X to another company Y:
        Add the edge's weight to T[Y]
        If T[Y] >= 75, add Y to S