Java Poset simulation

Question

I'm looking to simulate a poset, called x say, of size 2n in java of the form a_1 < a_2 < ... < a_n, and b_1 < b_2 < ... < b_n.

I want to run an iteration to get a random linear extension whereby I compare the 'size' of each object and if two adjacent positions can be switched I do so, if not then I stick, to end with a new order. For example x[i] = a_k and x[i+1] = b_k I switch them, however if x[i] = a_k and x[i+1] = a_(k+1) I would not. (In essence this is the Karzanov Khachiyan chain).

I initially thought of using an array of arrays where x[][] = {a_1[], ..., b_1[], ... }, where say a_1 = {a,1}, where I could compare the values and easily make a switch. Now I am trying to think of other ways to do this, as from my previous quesiton I can see this isn't going to be a partiularly efficient or elegant way of doing this. Does anyone have any suggestions?

Owen · Accepted Answer · 2011-06-25 19:52:00Z

3

Well first, I like your idea of storing the whole chain in an array. I think that will work fine.

But I agree with you that the "nested" array,

{ {'a', 1}, {'a', 2}, ... }

will probably be a little annoying. Have you thought of making a class like

class Elem {
    String symbol;
    int subscript;
}

You could then write a comparator to say whether one Elem is less than another:

Comparator<Elem> comp = new Comparator<Elem>() {
    public int compareTo(Elem e1, Elem e2) {
        // return -1 if e1<e2, +1 if e2<e1, 0 otherwise
    }
    public boolean equals(Elem e1, Elem e2) {
        // ...
    }
};

I think that might make your life easier because then one element feels more like a single object.

edited Jun 25, 2011 at 19:52

answered Jun 25, 2011 at 16:27

Owen

39.5k14 gold badges98 silver badges131 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user528676 Over a year ago

Thanks for the tip. I arrived at creating a class called ELement() as well which seems to have worked. I like the comparator idea which I think I will use.

Collectives™ on Stack Overflow

Java Poset simulation

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related