# Non-flat partitions of a set

A non-flat partition of a set is one where, when the elements of the set are on a grid, the partition does not contain subsets with elements from the same row. When the set is more irregular the same idea holds.

See e.g. Chapter 4 of G. Peccati and M. Taqqu. Wiener Chaos: Moments, Cumulants and Diagrams: A survey with Computer Implementation. Bocconi & Springer Series. Springer, 2011.

For example, when the set is a $$3 \times 4$$ grid of dots, we have an example flat and non-flat partition of the dots as follows.

I have the following code, which arranges points on a grid, finds all the partitions, and selects all the non-flat ones:

range[x_, r_] := Module[{interval},
i = IntegerPart[(x - 1)/r]; interval = Range[r i + 1, r i + r]];
qflat[x_, r_] :=
AnyTrue[Subsets[range[#, r] & /@ x, {2}],
IntersectingQ[#[], #[]] &];
flatQ[par_, r_] := AnyTrue[par, qflat[#, r] &];
pickflat[par_, r_] :=
Select[Transpose[{par, flatQ[#, r] & /@ par}], #[] ==
False &][[All, 1]];
Needs["Combinatorica"];
par = SetPartitions[Range[1, 12]];
SetPartitions[Range[1, 12]] // AbsoluteTiming // First
pickflat[par, 4] // AbsoluteTiming // First


14.811

351.011

The last step pickflat is quite long. Is there a trick which avoids the use of subsets here, which might optimise the code?

Why not use Quotient to figure out what row each element belongs to, and then make sure there are no duplicates? For example:

fQ[part_, n_] := AllTrue[Quotient[part, n, 1], DuplicateFreeQ]


Comparison:

rand = RandomSample[par, 10000];

r1 = pickflat[rand, 4]; //AbsoluteTiming
r2 = Select[rand, fQ[#, 4]&]; //AbsoluteTiming

r1 === r2


{0.71157, Null}

{0.078211, Null}

True

By the way, you can represent your set partitions with a simple vector. For example, the following set partition:

{{1},{2,3,8},{4,7,9,10},{5,6,11,12}}


could be represented with:

{1, 2, 2, 3, 4, 4, 3, 2, 3, 3, 4, 4}
`

which gives the set each index is associated to, that is:

$$\begin{array}{c} 1\to 1 \\ 2\to 2 \\ 3\to 2 \\ 4\to 3 \\ 5\to 4 \\ 6\to 4 \\ 7\to 3 \\ 8\to 2 \\ 9\to 3 \\ 10\to 3 \\ 11\to 4 \\ 12\to 4 \\ \end{array}$$

Then, your list of set partitions could be represented as a matrix of integers. It is possible to define a compiled predicate that decides whether this new representation is flat or not. This compiled code would be orders of magnitude faster.

• Ok thank you this is great. The compiled predicate idea will definitely help with the larger sets. – apkg Jun 19 '19 at 14:54