# Obtaining all posets in a certain form with SAGE

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 close merge delete

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"]]]];

Sort by » oldest newest most voted 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.

more

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 ' ?

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...

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?

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 '

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

def f(n):
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:
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"
print ( "The comparability graph of p as a matrix is:\n%s"
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):
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
, [ [ 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...

more

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"]].

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 '

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.

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".

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.