# OrderedSetPartitions (variant)

I would like to have the list of partitions of [1,2,...N] of finite size k but with using the NULL set

for example, if looking for the partitions of [1,2,3,4,5] of size 3, i would like [ [],[],[1,2,3,4,5] ]

and [ [],[1,2,3],[4,5] ] to be in this list

is it possible to do natively in Sage, or should i write a custom function ?

OrderedSetPartitions(5,3).list()

returns

[[{1, 2, 3}, {4}, {5}],
[{1, 2, 3}, {5}, {4}],
[{1, 2, 4}, {3}, {5}],
[{1, 2, 5}, {3}, {4}],...


EDIT: here is a (non optimized at all) attempt to solve naively this problem

def OrderedSetPartitions_0(A,k):

cols={i for i in range(k)}
# returns the list of k-OrderedSetPartitions of A, allowing for the empty set
s=Subsets(cols).list()
res=[]
count=0
P=[OrderedSetPartitions(A,i) for i in range(k+1)]

for sub in s:
print("sub=")
print(sub)

tmp=[ {} for i in range(k)]
c=sub.cardinality()
for part in P[c]:
print("part=")
print(part)
for i in range(c):
tmp[sub[i]]=part[i]

print("tmp=")
print(tmp)

res=res.append([tmp])
#  res=res.append([tmp]) # tried this too
print("res=")
print(res)
count=count+1
return(res)
# print(count)

A=range(3)
k=2
A
P=[OrderedSetPartitions(A,i) for i in range(k+1)]
# note that P.list is a list of list !
P.list()

[[{0, 1}, {2}],
[{0, 2}, {1}],
[{1, 2}, {0}],
[{0}, {1, 2}],
[{1}, {0, 2}],
[{2}, {0, 1}]]

myset=OrderedSetPartitions_0(A,k)


I get this error message, and I admit I don't get it at all, because it looks fine when coding, but somehow res seems to be "None" instead of []

sub=
{}
sub=
{0}
part=
[{0, 1, 2}]
tmp=
[{0, 1, 2}, {}]
res=
None
sub=
{1}
part=
[{0, 1, 2}]
tmp=
[{}, {0, 1, 2}]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "_sage_input_21.py", line 10, in <module>
exec compile(u'open("___code___.py","w").write("#


-- coding: utf-8 --\n" + _support_.preparse_worksheet_cell(base64.b64decode("bXlzZXQ9T3JkZXJlZFNldFBhcnRpdGlvbnNfMChBLGsp"),globals())+"\n"); execfile(os.path.abspath("___code___.py")) File "", line 1, in <module>

  File "/private/var/folders/gm/z065gk616xg6g0xgn4c7_bvc0000gn/T/tmpryfYOj/___code___.py", line 2, in <module>
exec compile(u'myset=OrderedSetPartitions_0(A,k)
File "", line 1, in <module>

File "/private/var/folders/gm/z065gk616xg6g0xgn4c7_bvc0000gn/T/tmpSH_9LF/___code___.py", line 27, in OrderedSetPartitions_0
res=res.append([tmp])
AttributeError: 'NoneType' object has no attribute 'append'


The problem is about res if i omit the line res=res.append(tmp), i will get the enumeration ok i think

EDIT: i changed res=res.append(tmp) by res.append(tmp) i also changed the line initializing tmp into tmp=[ set() for i in range(k)] now as a result of print(tmp) i get the correct enumeration

[{0, 1, 2}, set([]), set([])]
[set([]), {0, 1, 2}, set([])]
[set([]), set([]), {0, 1, 2}]
[{0, 1}, {2}, set([])]
[{0, 2}, {1}, set([])]
[{1 ...
edit retag close merge delete

Could you please give us what complete output you expect for k=3, N=3 ? It is not clear to me if the empty sets shoud happen first or not.

[{0, 1, 2}, {}, {}] [{}, {0, 1, 2}, {}] [{}, {}, {0, 1, 2}] [{0, 1}, {2}, {}] [{0, 2}, {1}, {}] [{1, 2}, {0}, {}] [{0}, {1, 2}, {}] [{1}, {0, 2}, {}] [{2}, {0, 1}, {}] [{0, 1}, {}, {2}] [{0, 2}, {}, {1}] [{1, 2}, {}, {0}] [{0}, {}, {1, 2}] [{1}, {}, {0, 2}] [{2}, {}, {0, 1}] [{}, {0, 1}, {2}] [{}, {0, 2}, {1}] [{}, {1, 2}, {0}] [{}, {0}, {1, 2}] [{}, {1}, {0, 2}] [{}, {2}, {0, 1}] [{0}, {1}, {2}] [{0}, {2}, {1}] [{1}, {0}, {2}] [{2}, {0}, {1}] [{1}, {2}, {0}] [{2}, {1}, {0}]

Sort by » oldest newest most voted

What is missing from the OrderedSetPartitions are the positions of the additional empty sets. Chosing a subset of size i in a list of size k is done via Combinations. So, here is a possibility mixing those two tools:

def OrderedSetPartitions_0(n,k):
my_list = []
for i in range(1,k+1):
for empty_spots in Combinations(k,k-i):
for part in OrderedSetPartitions(range(n),i):
L = list(part)
LL = []
for j in range(k):
if j in empty_spots:
LL.append(set())
else:
LL.append(L.pop())
my_list.append(LL)
return my_list


For example you get as expected:

sage: OrderedSetPartitions_0(3,3)
[[set(), set(), {0, 1, 2}],
[set(), {0, 1, 2}, set()],
[{0, 1, 2}, set(), set()],
[set(), {2}, {0, 1}],
[set(), {1}, {0, 2}],
[set(), {0}, {1, 2}],
[set(), {1, 2}, {0}],
[set(), {0, 2}, {1}],
[set(), {0, 1}, {2}],
[{2}, set(), {0, 1}],
[{1}, set(), {0, 2}],
[{0}, set(), {1, 2}],
[{1, 2}, set(), {0}],
[{0, 2}, set(), {1}],
[{0, 1}, set(), {2}],
[{2}, {0, 1}, set()],
[{1}, {0, 2}, set()],
[{0}, {1, 2}, set()],
[{1, 2}, {0}, set()],
[{0, 2}, {1}, set()],
[{0, 1}, {2}, set()],
[{2}, {1}, {0}],
[{1}, {2}, {0}],
[{2}, {0}, {1}],
[{1}, {0}, {2}],
[{0}, {2}, {1}],
[{0}, {1}, {2}]]

more

is set() different from {} ?

your solution works but i still wonder why i have this bug. I had all the elements right but when aggregating into a list with res.append() or the + operator i had strange side-effects...

This is not a bug, in Python set() denotes the empty set, while {} denotes the empty dictionary:

sage: type({})
<type 'dict'>
sage: type(set())
<type 'set'>


What kind of side effect do you have ?

thanks for this fact that i didn't know. i edited the question to reflect better the remaining problem that I have. Thanks