Phân vùng không đặt chéo

Question

Một phân vùng tập hợp là không chéo nếu bất cứ khi nào bốn phần tử $a<b<c<d$ có phải như vậy không $a,c$ ở trong cùng một khối và $b,d$ sau đó ở trong cùng một khối $a,b,c,d$ là tất cả trong cùng một khối.

Tôi có thể lấy danh sách các phân vùng đã đặt không.

Với "Combinatorica", tôi có thể lấy TẤT CẢ các phân vùng đã đặt (chẳng hạn như {1,2,3,4}) bằng lệnh SetPartitions [4].

Điều tôi muốn là danh sách này không có phần tử {{1,3}, {2,4}} không phải là phần tử không cộng gộp.

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

Tôi có một gói Mathematica để tạo các đối tượng Catalan trên GitHub, vì vậy tôi có một số thuật toán đệ quy tạo ra những gì bạn muốn. Hơn nữa, nó có một biểu diễn đồ họa đẹp mắt và một số thao tác trên chúng, chẳng hạn như xoay.

Chỉ cần tải xuống gói và làm

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

để có được

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

Nếu bạn không muốn mọi thứ trong gói, bạn nên dễ dàng giải nén phương thức.