@jjimm: "The problem:
I have a relation R where
domain set is: dom R = {A,B,C}, and
range set is: ran R = {1,2,3}.
The relations (maplets) are:
{A>1,A>3,B>2,B>3,C>1,C>3}
The following sets would be performed, if we use at most once every element
from each side of the relationship, within each new set. (E.g. {A>2,B>1} is
ok but {A>2,A>3,C>3} is not ok because A and 3 is being twice in the set).
We have:
first {A>1,B>2,C>3}
second {A>1,B>3} (not C3 because 3 is used)
third {A>1,C>3}
fourth {A>3,B>2,C>1}
etc.
I try to capture the sets with the most number of elements (first and fourth
line, that have 3 elements each) and be able to store these somehow, for
further manipulation.
I have spent long time with this problem, and I looked into the association
problem in operations management and in maths, but still, I couldn�t create
any algorithm.
Any help is appreciated.
Jim."
    @rkm: "<quote>
Can you point out why A>2, B>1, and C>2 are not listed as 
relations, even though you use them below.  I think I don't 
understand the problem because of this.
Rick"
    @jobollin: "<quote>
The brute force way is to generate all the possible sets and retain only 
the largest ones.  If I've figured it correctly, this can be either 
O(N^D) or O(N^R), where N is the number of relations, D is the size of 
the domain, and R is the size of the range; which complexity applies 
depends on the algorithm: whether you choose relations for the sets 
based on their left-hand or right-hand sides.  To do this you will need 
to classify relations based on their left-hand sides, right-hand sides, 
or both, depending on the details of the algorithm.
No, its not elegant, but you have already spent a lot of fruitless time 
on this so if the brute force approach works adequately then use it and 
go on.
John Bollinger
<email_address>"
    @jahorsmeier: ""Jim" <email_address> wrote in message news:bf38c5$l6q$<email_address>
<quote>
Google up the 'job assignment problem', this is exaclty what you want.
Think of it this way  build a bipartite graph, on the left are the
manager nodes, on the right are the departments. From every node on
the left to every node on the right, an arc exists a_ij. The value
a_ij = 0 when manager i does not manage department j, 1 otherwise.
Every arc ij has an associate cost c_ij. This c_ij = 0 when manager
i is capable of managing department j, otherwise c_ij is a very large
number ('big-M' in operations research lingo). 
Every manager i is capable of managing just one single department
and every department wants to be managed by just one single manager,
hence the 'capacaty' of all managers equals one as well as the 'demand'
of all the departments.
The job assignment problem solver minimizes just this:
    min sum(i, a_ij*c_ij)
    w.r.t. sum(i, a_ij) = 1 and sum(j, a_ij) = 1
If you want as many managers managing as many departments, you 
have to introduce an 'artificial' manager and en 'artificial'
department to your model. The cost for the artificial manager
managing real departments should be set to 'big-M', similar to
the costs of real managers managing the artificial department.
The artificial manager can manage the artificial department
at costs zero.
kind regards,
Jos (sorry, no Java code here)"
    @jjimm: "Thank you for the help guys, Jim
news:bf38c5$l6q$<email_address>
<quote>
element
is
fourth
association
create"
    @jahorsmeier: ""Jos A. Horsmeier" <email_address> wrote in message news:3f15785a$0$147$<email_address>
<quote>
I gave it some more thoughts and came to the conclusion that a regular
job assignment solver is a bit of an overkill here, especially if you 
look at the problem size. Your problem resembles the '8 Queens' problem
a bit, with an additional constraint, i.e. 'Queens' (read: managers)
are not allowed to be placed everywhere on the board (read: cannot be
assigned to every job). 
This all boils down to the following recursive back-tracking thingy:
public class Assign {
    private static final int M= 3;
    private static int[][] relation= new int[][] {
        { 0, 2 }, // A>1 A>3
        { 1, 2 }, // B>2 B>3
        { 0, 2 }  // C>1 C>3
    };
    private static int[] mgr= new int[M]; // manager i manages job mgr[i]
    private static int[] job= new int[M]; // job j is managed by manager job[j]
    private static String[] sol= new String[M*M]; // the solution stack
    private static int      cur= 0;               // number of current solutions
    private static int      len= 0;               // length of the solution
    private static void assign(int m) {           // assign manager m to a job
         save(); // save a current solution
        if (m >= relation.length)                 // all managers considered? 
            return;
        for (int i= 0; i < relation[m].length; ++i) // check what this one can do
            if (job[relation[m][i]] == 0) {         // this job still free?
                mgr[m]= relation[m][i]+1;           // claim this job
                job[relation[m][i]]= m+1;           // job claimed by manager
                assign(m+1);                        // assign next manager
                mgr[m]= 0;                          // release this job
                job[relation[m][i]]= 0;             // this job still available
           }
    }
    private static void save() { // save a current solution
        int p= 0;
        for (int i= 0; i < mgr.length; ++i)
            if (mgr[i] > 0) ++p;
        if (p > len) // found a better solution?
            cur= 0;  // drop previous solutions
        if (p >= len) { // worth keeping this solution?
            len= p;
            String s= ""; // cook up some rep. for this solution
            for (int i=0; i < mgr.length; ++i)
                if (mgr[i] > 0)
                    s+= i+">"+ (mgr[i]-1)+" ";
            sol[cur++]= s; // and stack it
        }
    }
    private static void print() { // print all solutions
        for (int i= 0; i < cur; ++i)
           System.out.println(sol[i]);
    }
    public static void main(String[] args) {
        assign(0);
        print();
    }
}
kind regards,
Jos"
{'source': 'USENET', 'other_information': '{"reply_count": 5, "forum_name": "comp.lang.java.programmer.20150110.mbox"}', 'file': 'data/output/usenet-comp.lang.parquet'}