Ask Your Question
1

Obtaining all posets in a certain form with SAGE

asked 2017-09-20 03:02:17 -0600

maresage gravatar image

updated 2017-09-20 09:53:27 -0600

I want to do certain calculation with posets using GAP. But GAP has no package for posets so I want to use SAGE first to generate all connected posets with a certain number of points and then use the data in GAP. The output of posets in SAGE should have the form ["x1","x2","x3","x4"],[["x1","x2"],["x1","x3"],["x3","x4"],["x2","x4"]] so that I can use them in GAP. Here the poset has 4 elements x1,x2,x3 and x4 and ["x1","x2"] means that x1 is smaller than x2 etc.

So I want the following with SAGE:

Input: A number $n \geq 2$.

Output: The list of all connected posets with $n$ elements displayed in the form (this is an example) ["x1","x2","x3","x4"],[["x1","x2"],["x1","x3"],["x3","x4"],["x2","x4"]].

edit: Thank you very much for the two answers. Sadly I cannot comment at the moment directly without approvial of a moderator. Your codes solve my problem in a perfect way expect that the outputs have a ' where there should be a " so that GAP can understand it. (example: instead of ['x1', 'x2', 'x3', 'x4'], [['x1', 'x2'], ['x1', 'x3'], ['x1', 'x4'] the first element should look like ["x1", "x2", "x3"], [["x1", "x2"], ["x1", "x3"]]).

edit retag flag offensive close merge delete

Comments

So the output for n=3 should look like this : L:=[ [["x1", "x2", "x3"], [["x1", "x2"], ["x1", "x3"]] ], [["x1", "x2", "x3"], [["x1", "x2"], ["x2", "x3"]]], [["x1", "x2", "x3"], [["x1", "x3"], ["x2", "x3"]]]];

maresage gravatar imagemaresage ( 2017-09-20 10:46:41 -0600 )edit

2 answers

Sort by ยป oldest newest most voted
1

answered 2017-09-20 09:37:36 -0600

fidbc gravatar image

updated 2017-09-20 15:54:29 -0600

Not entirely clear what the question was. Or was this an implementation request?

In case you were looking for an implementation, here is a possible way of doing it. :-)

le_relations = lambda P: [(a,b) if P.le(a,b) else (b,a) for a,b in P.comparability_graph().edges(labels=None)]
cover_relations = lambda P: [(a,b) if P.le(a,b) else (b,a) for a,b in P.hasse_diagram().edges(labels=None)]

format_pt = lambda k: "'x{0}'".format(k+1)
format_relations = lambda relations: [[format_pt(a),format_pt(b)] for a,b in relations]
format_pts = lambda P: [format_pt(a) for a in P]
format_poset = lambda P: [format_pts(P), format_relations(cover_relations(P)), format_relations(le_relations(P))]

what_you_want = lambda n: [format_poset(P) for P in posets(n) if P.is_connected()]

Now you should be able to just issue:

what_you_want(3)
[[["'x1'", "'x2'", "'x3'"],
  [["'x1'", "'x2'"], ["'x1'", "'x3'"]],
  [["'x1'", "'x2'"], ["'x1'", "'x3'"]]],
 [["'x1'", "'x2'", "'x3'"],
  [["'x1'", "'x2'"], ["'x2'", "'x3'"]],
  [["'x1'", "'x2'"], ["'x1'", "'x3'"], ["'x2'", "'x3'"]]],
 [["'x2'", "'x1'", "'x3'"],
  [["'x1'", "'x3'"], ["'x2'", "'x3'"]],
  [["'x1'", "'x3'"], ["'x2'", "'x3'"]]]]

Observe that if you just wish to format a single poset, you can do so via format_poset.

Hope this is useful.


Update: Adapted to new output format.

edit flag offensive delete link more

Comments

Thank you very much, but the output for n=3 is as follows for the first poset: [['x0', 'x1'], ['x0', 'x2']] , is there a way to get " instead of ' ?

maresage gravatar imagemaresage ( 2017-09-20 09:47:58 -0600 )edit

The posted example

["x1","x2","x3","x4"],[["x1","x2"],["x1","x3"],["x3","x4"],["x2","x4"]]

only considers the minimal set of relations to be closed in order to deliver the poset for

  2
 / \
1   4
 \ /
  3

with the order "j smaller than k" connected by a path going from left to right.

There is no 1-4 in the list. Let's wait for this detail...

dan_fulea gravatar imagedan_fulea ( 2017-09-20 10:00:33 -0600 )edit

is there a way to get " instead of ' ?

Do you want a string

"""["x1","x2","x3","x4"],[["x1","x2"],["x1","x3"],["x3","x4"],["x2","x4"]]"""

or a list?

dan_fulea gravatar imagedan_fulea ( 2017-09-20 10:02:33 -0600 )edit

So the output for n=3 should look like this : L:=[ [["x1", "x2", "x3"], [["x1", "x2"], ["x1", "x3"]] ], [["x1", "x2", "x3"], [["x1", "x2"], ["x2", "x3"]]], [["x1", "x2", "x3"], [["x1", "x3"], ["x2", "x3"]]]]; with " instead of '

maresage gravatar imagemaresage ( 2017-09-20 10:46:54 -0600 )edit

@dan_fulea Were these questions meant to be on the original post?

fidbc gravatar imagefidbc ( 2017-09-20 15:55:08 -0600 )edit
1

answered 2017-09-20 09:47:50 -0600

dan_fulea gravatar image

updated 2017-09-20 18:12:00 -0600

If i correctly figure out what is needed, then the following code should solve the problem (to some percentage):

def f(n):
    """https://ask.sagemath.org/question/38865/
    obtaining-all-posets-in-a-certain-form-with-sage/
    """
    R         = range(n)
    posets    = [ p for p in Posets(n) if p.is_connected() ]
    variables = [ "x%s" % (k+1) for k in R  ]
    result    = []

    for p in posets:
        A = p.hasse_diagram().adjacency_matrix()
        result.append( [ variables
                         , [ [ variables[j], variables[k] ]
                             for j in R for k in R
                             if  A[j,k]
                         ] ] )
    return result

Example of usage in the sage interpreter:

sage: f(4)
[[['x1', 'x2', 'x3', 'x4'], [['x1', 'x2'], ['x1', 'x3'], ['x1', 'x4']]],
 [['x1', 'x2', 'x3', 'x4'], [['x1', 'x2'], ['x1', 'x4'], ['x2', 'x3']]],
 [['x1', 'x2', 'x3', 'x4'],
  [['x1', 'x2'], ['x1', 'x3'], ['x2', 'x4'], ['x3', 'x4']]],
 [['x1', 'x2', 'x3', 'x4'], [['x1', 'x2'], ['x2', 'x3'], ['x2', 'x4']]],
 [['x1', 'x2', 'x3', 'x4'], [['x1', 'x3'], ['x2', 'x3'], ['x3', 'x4']]],
 [['x1', 'x2', 'x3', 'x4'], [['x1', 'x4'], ['x2', 'x4'], ['x3', 'x4']]],
 [['x1', 'x2', 'x3', 'x4'], [['x1', 'x4'], ['x2', 'x3'], ['x2', 'x4']]],
 [['x1', 'x2', 'x3', 'x4'],
  [['x1', 'x3'], ['x1', 'x4'], ['x2', 'x3'], ['x2', 'x4']]],
 [['x1', 'x2', 'x3', 'x4'], [['x1', 'x2'], ['x2', 'x3'], ['x3', 'x4']]],
 [['x1', 'x2', 'x3', 'x4'], [['x1', 'x4'], ['x2', 'x3'], ['x3', 'x4']]]]
sage:

LATER EDIT:

I will try to explain the way the above code works still here in the answer, since it would not fit in the comment. My favorite way is always by using a special situation.

So let us get a big connected poset, code:

X = ZZ( 2^2 * 3 ).divisors()
R = [ [j,k] for j in X for k in X if j != k and j.divides(k) ]
p = Poset( (X, R) )

print ( "Is p connected? %s" 
        % p.is_connected() )
print ( "The Hasse diagram of p is given by the matrix:\n%s" 
        % p.hasse_diagram().adjacency_matrix() )
print ( "The comparability graph of p as a matrix is:\n%s" 
        % p.comparability_graph().adjacency_matrix() )
print ( "An oriented version of this matrix is:\n%s" 
        % matrix( ZZ, len(X), len(X)
                  , [ [ p.compare_elements(j,k) for k in X ] 
                      for j in X ] ) )

It gives an explanation of all objects:

Is p connected? True
The Hasse diagram of p is given by the matrix:
[0 1 1 0 0 0]
[0 0 0 1 1 0]
[0 0 0 0 1 0]
[0 0 0 0 0 1]
[0 0 0 0 0 1]
[0 0 0 0 0 0]
The comparability graph of p as a matrix is:
[0 1 1 1 1 1]
[1 0 0 1 1 1]
[1 0 0 0 1 1]
[1 1 0 0 0 1]
[1 1 1 0 0 1]
[1 1 1 1 1 0]
An oriented version of this matrix is:
[ 0 -1 -1 -1 -1 -1]
[ 1  0  0 -1 -1 -1]
[ 1  0  0  0 -1 -1]
[ 1  1  0  0  0 -1]
[ 1  1  1  0  0 -1]
[ 1  1  1  1  1  0]
sage:

The -1 in the first row means that $1$ (strictly) divides all other elements. The second row [ 1 0 0 -1 -1 -1] reads 2 is strictly divisible by 1, not strictly by 2, it does not (strictly) divide 3, but it does for 4, 6, 12 .

Now back to the original problem. Suppose we need variables for $x_k$ using exactly the divisors, as strings, the list of Hasse relations, the cover relations, and all relations for the strict divisibility. Here they are:

sage: dic = dict( [ (k, 'x%s' % k) for k in X ] )
sage: vars = dic.values()
sage: vars
['x1', 'x2', 'x3', 'x4', 'x6', 'x12']
sage: hasse_pairs = [ [ dic[j], dic[k] ] for j in X for k in X if [j,k] in p.cover_relations() ] 
sage: hasse_pairs
[['x1', 'x2'],
 ['x1', 'x3'],
 ['x2', 'x4'],
 ['x2', 'x6'],
 ['x3', 'x6'],
 ['x4', 'x12'],
 ['x6', 'x12']]
sage: all_pairs = [ [ dic[j], dic[k] ] for j in X for k in X if p.compare_elements(j,k) == -1 ]
sage: all_pairs
[['x1', 'x2'],
 ['x1', 'x3'],
 ['x1', 'x4'],
 ['x1', 'x6'],
 ['x1', 'x12'],
 ['x2', 'x4'],
 ['x2', 'x6'],
 ['x2', 'x12'],
 ['x3', 'x6'],
 ['x3', 'x12'],
 ['x4', 'x12'],
 ['x6', 'x12']]
sage:

(Sorry for the space used for such a simple step, but now all problems are solved. People generally underestimate the bad didactic impact of small steps omissions in maths and info. This still propagates from the last century, as paper and publication space were expensive.)

The one problem with the double quote... I would solve it in the very last step in the film "code writes code", and in this step we can replace all simple quotes with double ones in the resulted code string. For instance, you may need - as in the last comment:

def f(n):
    """https://ask.sagemath.org/question/38865/
    obtaining-all-posets-in-a-certain-form-with-sage/
    """
    R    = range(n)
    dic  = dict( [ (k, 'x%s' % (k+1)) for k in R ] )    # dic 0->'x1', 1->'x2', ...
    vars = dic.values()

    result    = []    # and we append in the next loop

    for p in Posets(n):
        if not p.is_connected():
            continue
        entry = [ vars
                  , [ [ dic[j], dic[k] ]
                      for j in R for k in R
                      if  p.hasse_diagram().adjacency_matrix() [j,k] ]
                  , [ [ dic[j], dic[k] ]
                      for j in R for k in R
                      if  p.compare_elements(j,k) == -1 ]
                  ]
        # entry = re.sub( "'", '"', str(entry) )    # here or later
        result.append( entry )
    return result

import re
# print  [ '\n'.join( [ re.sub( "'", '"', str(row) ) for row in f(5) ] ) ]
for row in f(5):
    print  re.sub( "'", '"', str(row) )

This gives a long list...

edit flag offensive delete link more

Comments

Thank you, this looks almost perfect! But the output has a ' instead of the needed " for gap. So instead of ['x1', 'x2', 'x3'], [['x1', 'x2'], ['x1', 'x3']] the first element should look like ["x1", "x2", "x3"], [["x1", "x2"], ["x1", "x3"]].

maresage gravatar imagemaresage ( 2017-09-20 09:51:49 -0600 )edit

So the output for n=3 should look like this : L:=[ [["x1", "x2", "x3"], [["x1", "x2"], ["x1", "x3"]] ], [["x1", "x2", "x3"], [["x1", "x2"], ["x2", "x3"]]], [["x1", "x2", "x3"], [["x1", "x3"], ["x2", "x3"]]]]; with " instead of '

maresage gravatar imagemaresage ( 2017-09-20 10:47:03 -0600 )edit

Thank you very much! This is almost perfect, expect that for n=3 the output should look like this: [ [["x1", "x2", "x3"], [["x1", "x2"], ["x1", "x3"]] ], [["x1", "x2", "x3"], [["x1", "x2"], ["x2", "x3"]]], [["x1", "x2", "x3"], [["x1", "x3"], ["x2", "x3"]]]] so instead of ' there should be " so that GAP can understand it.

maresage gravatar imagemaresage ( 2017-09-20 12:27:41 -0600 )edit

Alternatively an output like [ [[x1, x2, x3], [[x1, x2], [x1, x3]] ], [[x1, x2, x3], [[x1, x2], [x2, x3]]], [[x1, x2, x3], [[x1, x3], [x2, x3]]]] would also be ok since I can redefine in GAP then with x1:="y1" , x2:="y2" and x3:="y3".

maresage gravatar imagemaresage ( 2017-09-20 13:39:24 -0600 )edit

I got now a ok version using variables = [ "'x%s'" % (k+1) for k in R ], thanks again! By the way how can I apply your program to translate only a single given poset into the form (for example the poset of all divisors of 12). Sorry for the stupid question but I have no experience with SAGE.

maresage gravatar imagemaresage ( 2017-09-20 13:43:23 -0600 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2017-09-20 03:02:17 -0600

Seen: 183 times

Last updated: Sep 20