Partisi non-cross set

Question

Sebuah partisi set tidak bersilangan jika ada empat elemen $a<b<c<d$ seperti itu $a,c$ berada di blok yang sama dan $b,d$ berada di blok yang sama $a,b,c,d$ semuanya ada di blok yang sama.

Dapatkah saya mendapatkan daftar partisi himpunan yang tidak saling silang.

Dengan "Combinatorica" ​​saya bisa mendapatkan SEMUA partisi set (katakanlah {1,2,3,4}) dengan perintah SetPartitions [4].

Yang saya inginkan adalah daftar ini tanpa elemen {{1,3}, {2,4}} yang tidak bersilangan.

Answer 1

Needs["Combinatorica`"]

ClearAll[nonCrossingSetPartitions]
nonCrossingSetPartitions = 
    DeleteCases[{___, {___, a_, ___, c_, ___}, ___, {___, b_, ___, d_, ___}, ___} /;
       a < b < c < d] @* SetPartitions;

nonCrossingSetPartitions @ 4 // Column

nonCrossingSetPartitions @ 5 // Length

42

Answer 2

Saya memiliki paket Mathematica untuk menghasilkan objek Catalan di GitHub, jadi saya memiliki beberapa algoritme rekursif yang menghasilkan apa yang Anda inginkan. Selain itu, ia memiliki representasi grafis yang bagus dari ini, dan beberapa operasi pada ini, seperti rotasi.

Cukup unduh paketnya, dan lakukan

Needs["CatalanObjects`"]
Last /@ NonCrossingPartitions[4]

mendapatkan

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

Jika Anda tidak ingin semua ada di dalam paket, itu harus mudah untuk mengekstrak metode ini.