如何查找集合的所有分区

Question

我有一套不同的价值观.我正在寻找一种方法来生成此集合的所有分区,即将集合划分为子集的所有可能方式.

例如,该集{1, 2, 3}具有以下分区:

{ {1}, {2}, {3} },
{ {1, 2}, {3} },
{ {1, 3}, {2} },
{ {1}, {2, 3} },
{ {1, 2, 3} }.

由于这些是数学意义上的集合,因此顺序无关紧要.例如,{1, 2}, {3}是相同的,{3}, {2, 1}也不应该是单独的结果.

可以在Wikipedia上找到集合分区的完整定义.

Answer 1

我找到了一个简单的递归解决方案.

首先,让我们解决一个更简单的问题:如何找到由两部分组成的所有分区.对于n元素集,我们可以计算从0到(2 ^ n)-1的int.这将创建每个n位模式,每个位对应一个输入元素.如果该位为0,则将元素放在第一部分中; 如果为1,则元素放在第二部分中.这留下了一个问题:对于每个分区,我们将得到重复的结果,其中两个部分被交换.为了解决这个问题,我们将始终将第一个元素放入第一部分.然后,我们仅通过从0到(2 ^(n-1)) - 1的计数来分配剩余的n-1个元素.

现在我们可以将一个集合分成两部分,我们可以编写一个递归函数来解决问题的其余部分.该函数从原始集开始,找到所有两部分分区.对于这些分区中的每一个,它递归地找到将第二部分分成两部分的所有方法,从而产生所有三部分分区.然后,它将每个分区的最后一部分分开以生成所有四部分分区,依此类推.

以下是C#中的实现.调用

Partitioning.GetAllPartitions(new[] { 1, 2, 3, 4 })

产量

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

using System;
using System.Collections.Generic;
using System.Linq;

namespace PartitionTest {
    public static class Partitioning {
        public static IEnumerable<T[][]> GetAllPartitions<T>(T[] elements) {
            return GetAllPartitions(new T[][]{}, elements);
        }

        private static IEnumerable<T[][]> GetAllPartitions<T>(
            T[][] fixedParts, T[] suffixElements)
        {
            // A trivial partition consists of the fixed parts
            // followed by all suffix elements as one block
            yield return fixedParts.Concat(new[] { suffixElements }).ToArray();

            // Get all two-group-partitions of the suffix elements
            // and sub-divide them recursively
            var suffixPartitions = GetTuplePartitions(suffixElements);
            foreach (Tuple<T[], T[]> suffixPartition in suffixPartitions) {
                var subPartitions = GetAllPartitions(
                    fixedParts.Concat(new[] { suffixPartition.Item1 }).ToArray(),
                    suffixPartition.Item2);
                foreach (var subPartition in subPartitions) {
                    yield return subPartition;
                }
            }
        }

        private static IEnumerable<Tuple<T[], T[]>> GetTuplePartitions<T>(
            T[] elements)
        {
            // No result if less than 2 elements
            if (elements.Length < 2) yield break;

            // Generate all 2-part partitions
            for (int pattern = 1; pattern < 1 << (elements.Length - 1); pattern++) {
                // Create the two result sets and
                // assign the first element to the first set
                List<T>[] resultSets = {
                    new List<T> { elements[0] }, new List<T>() };
                // Distribute the remaining elements
                for (int index = 1; index < elements.Length; index++) {
                    resultSets[(pattern >> (index - 1)) & 1].Add(elements[index]);
                }

                yield return Tuple.Create(
                    resultSets[0].ToArray(), resultSets[1].ToArray());
            }
        }
    }
}

Answer 2

请参考贝尔数，这里是对这个问题的简单思考：
将 f(n,m) 视为将 n 个元素的集合划分为 m 个非空集合。

例如3个元素的集合的划分可以是：
1）集合大小1：{{1,2,3}, } <-- f(3,1)
2）集合大小2：{{1,2 },{3}}, {{1,3},{2}}, {{2,3},{1}} <-- f(3,2)
3) 设置大小 3: {{1}, {2}, {3}} <-- f(3,3)

现在让我们计算 f(4,2)：
有两种方法可以得到 f(4,2)：

A. 向 f(3,1) 添加一个集合，它将从 {{1,2,3}, } 转换为 {{1,2,3}, {4}}
B. 添加 4 到任何集合f(3,2)，它将从
{{1,2},{3}}, {{1,3},{2}}, {{2,3},{1}} 转换
为
{{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) + f(3,2)*2
这导致f(n,m) = f(n-1,m-1) + f(n-1,m)*m

这是用于获取集合的所有分区的 Java 代码：

import java.util.ArrayList;
import java.util.List;

public class SetPartition {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        for(int i=1; i<=3; i++) {
            list.add(i);
        }

        int cnt = 0;
        for(int i=1; i<=list.size(); i++) {
            List<List<List<Integer>>> ret = helper(list, i);
            cnt += ret.size();
            System.out.println(ret);
        }
        System.out.println("Number of partitions: " + cnt);
    }

    // partition f(n, m)
    private static List<List<List<Integer>>> helper(List<Integer> ori, int m) {
        List<List<List<Integer>>> ret = new ArrayList<>();
        if(ori.size() < m || m < 1) return ret;

        if(m == 1) {
            List<List<Integer>> partition = new ArrayList<>();
            partition.add(new ArrayList<>(ori));
            ret.add(partition);
            return ret;
        }

        // f(n-1, m)
        List<List<List<Integer>>> prev1 = helper(ori.subList(0, ori.size() - 1), m);
        for(int i=0; i<prev1.size(); i++) {
            for(int j=0; j<prev1.get(i).size(); j++) {
                // Deep copy from prev1.get(i) to l
                List<List<Integer>> l = new ArrayList<>();
                for(List<Integer> inner : prev1.get(i)) {
                    l.add(new ArrayList<>(inner));
                }

                l.get(j).add(ori.get(ori.size()-1));
                ret.add(l);
            }
        }

        List<Integer> set = new ArrayList<>();
        set.add(ori.get(ori.size() - 1));
        // f(n-1, m-1)
        List<List<List<Integer>>> prev2 = helper(ori.subList(0, ori.size() - 1), m - 1);
        for(int i=0; i<prev2.size(); i++) {
            List<List<Integer>> l = new ArrayList<>(prev2.get(i));
            l.add(set);
            ret.add(l);
        }

        return ret;
    }

}

结果是：
[[[1, 2, 3]]] [[[1, 3], [2]], [[1], [2, 3]], [[1, 2], [3]]] [[[1], [2], [3]]] Number of partitions: 5