Red de conocimiento informático - Consumibles informáticos - Establecer algoritmo de partición

Establecer algoritmo de partición

Supongamos que un conjunto de n elementos se puede dividir en F(n,m) conjuntos diferentes compuestos por m subconjuntos no vacíos.

Considere un conjunto de 3 elementos, que se pueden dividir en

① Un conjunto de 1 subconjunto: {{1, 2, 3}}

② 2 subconjuntos Conjunto de conjuntos: {{1, 2}, {3}}, {{1, 3}, {2}}, {{2, 3}, {1}}

③ 3 subconjuntos El conjunto de: {{1}, {2}, {3}}

∴F(3,1)=1;F(3,2)=3;F(3,3) =1 ;

¿Qué hacer si se requiere F(4,2)?

A. Agrega un elemento {4} a ① para obtener {{1, 2, 3}, {4}}

B Agrega cualquier subconjunto a ② Agrega un 4 a. obtener

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

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

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

∴F(4,2)=F(3,1)+2*F(3,2)=1+2*3=7

Extensión, obtenemos F(n,m)=F(n-1,m-1)+m*F(n-1,m)