生成所有“独特"的集合的子集(不是幂集) [英] Generate all "unique" subsets of a set (not a powerset)
问题描述
假设我们有一个集合 S
,其中包含一些子集:
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]
假设 S 包含六个唯一元素:a、b、c、d、e
和 f
.
Let's also say that S contains six unique elements: a, b, c, d, e
and f
.
我们如何才能找到所有可能的 S
子集,其中包含 S
的每个唯一元素恰好一次?
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?
如果有伪代码、Ruby 或 Erlang 示例,我将不胜感激.
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:
- 一个 1 元素数组 [x] 恰好有一个分区
- 如果 x 是 x = [head] + tail 形式的数组,则 x 的分区是通过获取 tail 的每个分区并将 head 添加到每个可能的来生成的.例如,如果我们生成 [3,2,1] 的分区,那么从 [2,1] 的分区 [[2,1]] 我们可以将 3 添加到 [2,1] 或作为单独的元素,这为我们提供了 [1,2,3] 的 5 个分区中的 2 个分区 [[3,2,1] 或 [[2,1], [3]]
ruby 实现有点像
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屋!