标签: powerset

powerset {1, 2, 3}是:

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

假设我有一个SetJava语言:

Set<Integer> mySet = new HashSet<Integer>();
mySet.add(1);
mySet.add(2);
mySet.add(3);
Set<Set<Integer>> powerSet = getPowerset(mySet);

如何以最佳的复杂度顺序编写函数getPowerset？(我想它可能是O(2 ^ n).)

给定一套

{0, 1, 2, 3}

生成子集的好方法是什么:

[set(),
 {0},
 {1},
 {2},
 {3},
 {0, 1},
 {0, 2},
 {0, 3},
 {1, 2},
 {1, 3},
 {2, 3},
 {0, 1, 2},
 {0, 1, 3},
 {0, 2, 3},
 {1, 2, 3},
 {0, 1, 2, 3}]

我需要获取数组的所有可能子集.

说我有这个:

[1, 2, 3]

我怎么得到这个？

[], [1], [2], [1, 2], [2, 3], [1, 3], [1, 2, 3]

我对所有子集感兴趣.有关特定长度的子集,请参阅以下问题:

• 大小为n的子集找到:1,2
• 查找大小> 1:1的子集

我想基于数字的起始列表有效地生成唯一的数字组合列表.

示例开始,list = [1,2,3,4,5]但算法应该工作[1,2,3...n]

result = 

[1],[2],[3],[4],[5]
[1,2],[1,3],[1,4],[1,5]
[1,2,3],[1,2,4],[1,2,5]
[1,3,4],[1,3,5],[1,4,5]
[2,3],[2,4],[2,5]
[2,3,4],[2,3,5]
[3,4],[3,5]
[3,4,5]
[4,5]

注意.我不想要重复的组合,虽然我可以忍受它们,例如在上面的例子中我真的不需要组合[1,3,2],因为它已经存在[1,2,3]

我正在面试,我在"数学"类别下在网上偶然发现了这个问题.

生成给定集的幂集:

int A[] = {1,2,3,4,5};  
int N = 5; 
int Total = 1 << N;
for ( int i = 0; i < Total; i++ ) { 
 for ( int j = 0; j < N; j++) {
  if ( (i >> j) & 1 ) 
      cout << A[j]; 
   } 
 cout <<endl;

 }

请我不要一个明确的答案.我只想澄清和提示如何解决这个问题.

我检查了谷歌上的电源设置算法,我仍然不明白如何解决这个问题.

此外,有人可以重申问题的要求.

谢谢.

我有一些类型的项目,并希望生成其权力集.

我搜索了网络,找不到任何解决此特定任务的Scala代码.

这就是我提出的.它允许您限制length参数生成的集合的基数.

def power[T](set: Set[T], length: Int) = {
   var res = Set[Set[T]]()
   res ++= set.map(Set(_))

   for (i <- 1 until length)
      res = res.map(x => set.map(x + _)).flatten

   res
   }

这不包括空集.要完成此操作,您必须将方法的最后一行简单地更改为res + Set()

有什么建议如何以更实用的方式实现这一目标？

给定输入数组

[a,b,c,d,e]

和'加入'功能 (a,b) => (a+b)

我的代码返回以下数组数组,包含通过将join函数应用于各种元素对而获得的每个可能的变体,同时保持顺序:

[
  [a,b,c,d,e],
  [a,b+c,d,e],
  [a,b+c+d,e],
  [a,b,c+d,e],
  [a+b,c,d,e],
  [a+b,c+d,e],
  [a+b+c,d,e],
  [a+b+c+d,e],
  [a,b,c,d+e],
  [a,b+c,d+e],
  [a,b+c+d+e],
  [a,b,c+d+e],
  [a+b,c,d+e],
  [a+b,c+d+e],
  [a+b+c,d+e],
  [a+b+c+d+e],
]

在视觉上,我想要做的是:

代码可以工作,但我不知道该怎么称呼它 - 并且想要使用熟悉此操作的其他开发人员可以理解的名称,如果存在这样的名称.它不是一个电源组,但它是类似的......这个特定的set/array操作有一个名字吗？

编辑:好的.它们不是排列 ; 排列将是不同顺序的5元素阵列[[a,b,c,d,e], [e,d,c,b,a], [a,d,b,c,e], ...]

它们不是分区,因为任何子集只能包含输入的相邻元素. - 换句话说,分区允许这样:

(这可能源于纯集理论,没有有序集的概念.)

它们不是组合,因为输出的每个元素都只使用输入集的每个成员一次.

我认为myArray.OrderedPartitions((a,b) => (a+b))可能是一个适当的简洁和解释.

我有这个代码生成一个大小为4的数组的幂集(数字只是一个例子,更少的组合写...).

#define ARRAY_SIZE 4


unsigned int i, j, bits, i_max = 1U << ARRAY_SIZE;
int array[ARRAY_SIZE];

for (i = 0; i < i_max ; ++i) {
    for (bits = i, j = 0; bits; bits >>= 1, ++j) {
        if (bits & 1)
            printf("%d", array[j]);
    }
}

输出:

{}
{1}
{2}
{1, 2}
{3}
{1, 3}
{2, 3}
{1, 2, 3}
{4}
{1, 4}
{2, 4}
{1, 2, 4}
{3, 4}
{1, 3, 4}
{2, 3, 4}
{1, 2, 3, …

我有一个元素列表(1,2,3),我需要得到该列表的超集(powerset)(没有重复元素).所以基本上我需要创建一个列表列表,如下所示:

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

实现这一点的最佳方式是什么(简单>效率在这种情况下,列表不会很大)？最好是在Java中,但任何语言的解决方案都是有用的.

尝试计算9个字母的字符串'ABCDEFGHI'的所有子集(幂集).

使用标准递归方法,我的机器在完成之前就会出现内存不足(1GB)错误.我没有更多的物理记忆.

怎么能做得更好？语言没有问题,发送到标准输出的结果也很好 - 在输出之前不需要全部保存在内存中.