Set partitions into k groups (including the NULL set) in Python

Question

there a few posts like this one I have a list of numbers, how to generate all unique k-partitions?

but i'd like to know if there are some new efficient libraries to solve this problem (itertools ? sagemath ?)

I have a list of numbers, how to generate all unique ordered k-partitions? for example, if I have [1,2,3,4,5] and k=3

[[1,2],[3],[4,5]] is such a partition but [[4,5],[3],[1,2]] is also such a partition

i would also like to include the NULL set as a possible set among the k subset for example

[[2,3],[],[1,4,5]]

the order matters between

[[1,2],[3],[4,5]]

and [[4,5],[3],[1,2]]

but [[2,1],[3],[5,4]] is considered the same as [[1,2],[3],[4,5]] if you follow me...

As far as I know, OrderedSetPartitions(5,3) from Sagemath will not provide the answer to my question because its excluding the NULL set

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

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[2].list is a list of list !
P[2].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

  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 aggregating the list into res. if i put a sharp to all the lines involving res i can enumerate the output correctly

EDIT: thanks for your answers

actually i changed res=res.append(tmp) to res.append(tmp) i get the enumeration right when doing print(tmp)

[{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}]

but strangely res is wrong , there must be some side effects

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

The first 3 lines are correct, then it starts to diverge with what i get with print(tmp). its very strange to me because there is no instruction between print(tmp) and res.append(tmp) !!!!!

Answer 1

Here is a solution in Sagemath, using NumPy arrays and itertools. The idea is same as in your code: create OrderedSetPartitions and beef them up with empty sets. To do this without too many loops, NumPy arrays are used: the key part is partitions[:, s] = P where certain columns of a 2D array partitions, initially filled with empty sets, are replaced by nonempty sets coming from OrderedSetPartitions.

import numpy as np
from itertools import combinations
A = Set([1, 2, 3, 4, 5])        # Sage set, not Python set
k = 3                           # number of elements in partition
all_partitions = np.array(OrderedSetPartitions(A, k).list())
for i in range(k-1, 0, -1):
    P = np.array(OrderedSetPartitions(A, i).list()) if i > 1 else [[A]]
    for s in combinations(range(k), i):
        partitions = np.empty((len(P), k), dtype=object)
        partitions[:, :] = [[Set()]]
        partitions[:, s] = P
        all_partitions = np.vstack((all_partitions, partitions))
print all_partitions

The output is a double NumPy array. You can return all_partitions.tolist() if a Python list is desired.

Technicalities

Sage sets (created with Set([1,2,3])) and Python sets (created with set([1,2,3]) or {1,2,3,4,5}) are objects of different classes. Within Sagemath, the output looks better for Sage sets: they are shown as {1,2,3} while Python sets are displayed as set([1,2,3]). For this reason, Sage sets are to be preferred within Sagemath. Also, OrderedSetPartitions returns Sage sets.

But it takes a bit more effort to get NumPy to play along with Sage sets: in particular, I couldn't get np.full to accept empty Sage set Set() as a filling object. This is the reason for using np.empty and then filling it in.

A similar issue is responsible for the case i == 1 being treated differently: NumPy tries to cast [[Set([1,2,3,4,5])]] to a three-dimensional array of numbers instead of a two-dimensional array containing one Sage set object.