借助位位置的java打印功率集

Question

在谷歌上搜索一段时间，寻找字符串的子集，我读了 wikipedia ，它提到了这一点

。。。。。对于S的整个功率集，我们得到：

{ } = 000 (Binary) = 0 (Decimal)
{x} = 100 = 4
{y} = 010 = 2
{z} = 001 = 1
{x, y} = 110 = 6
{x, z} = 101 = 5
{y, z} = 011 = 3
{x, y, z} = 111 = 7

有没有可能通过程序实现这一点，避免使用字符串长度的递归算法

到目前为止，我所理解的是，对于长度为n的字符串，我们可以从0运行到2^n - 1，并在位上打印的字符
我无法得到的是如何以最优化的方式将位上的映射到相应的字符

<强> ps：<强> >检查线程，但不能理解这一点，C++：<强> Power set generated by bits>/p>

Answer 1

其思想是，一组大小为n的幂集有2^n个元素，与长度最多为n的不同二进制数完全相同

现在你需要做的就是在两者之间创建一个映射，而不需要递归算法。幸运的是，对于二进制数，你有一个真正直观而自然的映射，如果你的循环变量有位j，你只需在字符串中的位置j添加一个字符到一个子集，你就可以轻松地使用我在那里写的getBit()（你可以内联它，但为了更好的可读性，我为你做了一个单独的函数）

p.S.根据要求，关于映射的更详细解释： 如果您有一个递归算法，那么您的流是由您在递归调用中遍历数据结构的方式给出的。因此，它是解决许多问题的一种非常直观和自然的方式

如果你想解决这样一个问题，而不管出于什么原因，比如为了减少时间和内存的使用，你都需要显式地进行遍历

当我们使用一个带有循环变量的循环，该循环变量假定一组特定的值时，我们需要确保将循环变量的每个值（例如42）映射到一个元素，在我们的例子中，映射到s的子集，这样我们就有了一个双射映射，也就是说，我们只映射到每个子集一次。因为我们有一个集合，顺序无关紧要，所以我们只需要满足这些要求的映射

现在我们来看一个二进制数，例如42=32+8+2，同样地，在上面位置的二进制中：

543210
101010

因此，我们可以使用位置将42映射到一个子集，如下所示：

• 以您喜欢的任何方式对集合s中的元素进行排序，但要保持一致（在一个程序执行中始终相同），我们可以在本例中使用字符串中的顺序
• 当且仅当位置j处的位被设置（等于1）时，添加元素e_j

由于每个数字至少有一个数字不同于其他数字，我们总是得到不同的子集，因此我们的映射是内射的（不同的输入->；不同的输出）

我们的映射也是有效的，因为我们选择的二进制数的长度最多等于集合的大小，所以位位置总是可以分配给集合中的一个元素。再加上我们选择的输入集与幂集大小相同（2^n），我们可以得出它实际上是双射的

import java.util.HashSet;
import java.util.Set;

public class PowerSet
{

    static boolean getBit(int i, int pos) {return (i&1<<pos)>0;}

    static Set<Set<Character>> powerSet(String s)
    {
        Set<Set<Character>> pow = new HashSet<>();
        for(int i=0;i<(2<<s.length());i++)
        {
            Set<Character> subSet = new HashSet<>();
            for(int j=0;j<s.length();j++)
            {
                if(getBit(i,j)) {subSet.add(s.charAt(j));}
            }
            pow.add(subSet);
        }
        return pow;

    }

    public static void main(String[] args)
    {System.out.println(powerSet("xyz"));}

}

Answer 2

下面是一个简单的方法（伪代码）：-

for(int i=0;i<2^n;i++) {

  char subset[];
  int k = i;
  int c = 0;
  while(k>0) {

    if(k%2==1) {
       subset.add(string[c]);
    }
    k = k/2;
    c++;
  } 

  print subset;
}

解释：-代码将数字除以2，然后计算余数，余数用于将数字转换为二进制形式。然后，正如你们所知，只选择字符串中的索引，其位号为1