生成所有“唯一”集合的子集（不是电源） [英] Generate all "unique" subsets of a set (not a powerset)

问题描述

假设我们有一个Set S ，其中包含一些子集：

   -  [a，b，c] 
  -  [a，b] 
  -  [c] 
  -  [d，e，f] 
  -  [d，f ] 
  -  [e] 
  

我们还说S包含六个独特的元素： a，b，c，d，e 和 f 。

我们如何找到包含 S 每一个唯一元素的所有可能的子集 S p>

函数/方法的结果应该是这样的：

1. [[a，b，c]，[d，e，f]];


2. [[a， b，c]，[d，f]，[e]];


3. [[a，b]，[c] ，[d，e，f]];


4. [[a，b]，[c]，[d，f] ，[e]]。

有没有最佳实践或任何标准的方法来实现？ / p>

我会感谢一个伪代码，Ruby或Erlang的例子。

解决方案

听起来好像是什么您正在寻找的是一组/阵列的分区。

这样做的一种方式是递归的：

• 一个元素数组[x]只有一个分区
• 
  
• 如果x是x = [head] + tail的形式的数组，那么x的分区是通过将每个分区分配给每个分区来生成的。例如，如果我们生成[3,2,1]的分区，那么从[2,1]的分区[[2,1]]中我们可以添加3到[2,1]或作为单独的元素，它给了我们2 [[3,2,1]或[[2,1]，[3]]的分区[1,2,3]具有

一个ruby实现看起来有点像

  def partition（x）
如果x.length == 1 
 [[x]] 
 else 
 head，tail = x [0]，x [1，x.length-1] 
分区（tail）.inject（[]）do | result，tail_partition | 
 result + partitions_by_adding_element（tail_partition，head）
 end 
 end 
 end 
 
 def partitions_by_adding_element（partition，element）
（0 .. partition.length）.collect do | index_to_add_at | 
 new_partition = partition.dup 
 new_partition [index_to_add_at] =（new_partition [index_to_add_at] || []）+ [element] 
 new_partition 
 end 
 end 
  

Let's say we have a Set S which contains a few subsets:

- [a,b,c]
- [a,b]
- [c]
- [d,e,f]
- [d,f]
- [e]

Let's also say that S contains six unique elements: a, b, c, d, e and f.

How can we find all possible subsets of S that contain each of the unique elements of S exactly once?

The result of the function/method should be something like that:

1. [[a,b,c], [d,e,f]];
2. [[a,b,c], [d,f], [e]];
3. [[a,b], [c], [d,e,f]];
4. [[a,b], [c], [d,f], [e]].

Is there any best practice or any standard way to achieve that?

I would be grateful for a Pseudo-code, Ruby or Erlang example.

解决方案

It sounds like what you are looking for are the partitions of a set/array.

One way of doing this is recursively:

• a 1 element array [x] has exactly one partition
• if x is an array of the form x = [head] + tail, then the partitions of x are generated by taking each partition of tail and adding head to each possible. For example if we were generating the partitions of [3,2,1] then from the partition [[2,1]] of [2,1] we can either add 3 to to [2,1] or as a separate element, which gives us 2 partitions [[3,2,1] or [[2,1], [3]] of the 5 that [1,2,3] has

A ruby implementation looks a little like

def partitions(x)
  if x.length == 1
   [[x]]
  else
    head, tail = x[0], x[1, x.length-1]
    partitions(tail).inject([]) do |result, tail_partition|
      result + partitions_by_adding_element(tail_partition, head)
    end
  end
end

def partitions_by_adding_element(partition, element)
  (0..partition.length).collect do |index_to_add_at|
    new_partition = partition.dup
    new_partition[index_to_add_at] = (new_partition[index_to_add_at] || []) + [element]
    new_partition
  end
end

这篇关于生成所有“唯一”集合的子集（不是电源）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！