生成集合[1]的所有分区

3 回答

• 2

  如果您的集合不大(或使用堆栈)，则可以尝试递归答案：

  原理如下，您有一个回馈函数：

  rec_func(SET) = List of List of Set
  

  和工作如下：

  rec_func(SET) =
    if SET = {empty}:
      // if no element, easy to give the answer
      return([[]])
    else:
      // 1. Remove one element from the set : 'a' to this set
      a = SET.pop()
      // 2. Call rec_func :
      list_of_list_of_set = rec_func(SET\'a')  
      response = []
      // 3. For every possibilities given by the function add the element 'a' :
      For every list_of_set in list_of_list_of_set  :
         // Case 1, you add 'a' to list_of_set
         response.push( [{'a'} + list_of_set] )
         // Case 2, for every set, you create a copy where you add 'a'
         for every set in list_of_set:
             response.push( [{set,'a'} + list_of_set\set] )
  
      // The function return the list of list of set created.        
      return(response)
  

  回复于 2024-04-27T05:12:49+08:00
• 16

  有一个重要的发现(在注释中)，可以将一组n个元素的分区表示为[6]形式的整数序列，其中 pi 是元素 i 的分区号。为了使这样的序列有效，它必须遵守以下规则：p1 为 1，并且对于每个<1≤n≤j 的 j，都有一些 i <j 使得 pj≤pi1。或者换句话说，在任何前缀中序列中，没有整数被跳过。

  现在，有一种按字典顺序枚举受约束序列的标准算法，该算法包括以下内容：

  • 从最小的顺序开始。

  • 要按字典顺序查找下一个序列：

  • 向后扫描序列，找到最右边的“可递增”元素。 (可递增元素是这样的元素，使得有一些较大的元素可以代替该元素，并且直到该点为止的结果子序列都是至少一个有效 sequence.)的前缀

  • 将该元素更改为下一个可行的较大元素(i.e.这将导致有效的前缀，如上所述)，然后在其右边的其余元素(如果有)中填充尽可能小的值。

  • 如果没有可递增元素，则枚举已终止。

  关于搜索可递增元素的几项规定，当要递增的元素通常接近序列末尾时，此算法最差 O(n)，通常为 O(1)。 (例如，使用此算法枚举排列是 O(1)，只要您可以在 O(1).)中找到“下一个元素”，就可以查找下一个排列

  为了将此算法应用于分区情况，我们观察到以下几点：

  • 最小的可能序列是[7]

  • 元素 pi 是可递增的，条件是：

  • pi <n

  • 有些 j <i 使得 pi=pj

  • 可行前缀的最小后缀是[8]

  在观察 2 中陈述条件的另一种方式是，元素是可递增的，除非其值为 n 或它是具有其值的序列中的第一个元素。如果我们也维持序列[9]，其中 m1 为 0，并且 mi 是 mi 和 pi 的最大值，则可以在 O(1)中进行确定。 m 的维护很简单，它使我们可以将可递增性条件重写为 pi≤mi。

  显而易见，可以在 O(n)时间实现“下一个分区”，但实际上发生的时间是在 O(1)内摊销。粗略地说，这是因为在大多数情况下，序列的最后一个元素是可递增的。

  回复于 2024-04-27T05:12:49+08:00
• -1

  我正在研究一种有效的算法，该算法根据@rici 定义的关键字方法生成集的所有分区，如前所述。以下用 python 编写的算法可以做到，并且仍有可能进行优化。我去做。您可能知道，这个问题是 NP-complete！由于优化，可能会有一些奇怪的符号，例如 try/except。但是，可以通过 n 定义 n 和 k 变量，集合具有多少个不同元素，而 k 是允许集合具有的不同类的数量。 INFO：该算法会生成所有分区，最多达到不同类的数量，而不仅仅是这些类！！！

  def partitions():
          global n
          global k
          codeword = [1 for digitIndex in range(0, n)]
          while True:
                  print codeword
                  startIndex = n - 1
                  while startIndex >= 0:
                          maxValue = max(codeword[0 : startIndex])
                          if codeword[startIndex] > maxValue or maxValue > k or codeword[startIndex] >= k:
                                  codeword[startIndex] = 1
                                  startIndex -= 1
                          else:
                                  codeword[startIndex] += 1
                                  break
  
  n = 12
  k = 2
  try:
          partitions()
  except:
          pass
  

  回复于 2024-04-27T05:12:49+08:00