生成所有“唯一”集合的子集（不是电源）

本文介绍了生成所有“唯一”集合的子集（不是电源）的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 假设我们有一个Set S ，其中包含一些子集：

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

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

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

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

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

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

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

[[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:

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

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

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

[[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