4
$\begingroup$

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.

Flat: enter image description here

Non-Flat: enter image description here

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[#[[1]], #[[2]]] &];
flatQ[par_, r_] := AnyTrue[par, qflat[#, r] &];
pickflat[par_, r_] := 
  Select[Transpose[{par, flatQ[#, r] & /@ par}], #[[2]] == 
      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?

$\endgroup$
8
$\begingroup$

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

Addendum

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.

$\endgroup$
  • $\begingroup$ Ok thank you this is great. The compiled predicate idea will definitely help with the larger sets. $\endgroup$ – Alexander Kartun-Giles Jun 19 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.