java - 借助位位置打印 PowerSet

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并打印 on 位的字符。
我无法得到的是如何以最优化的方式将那些 on 位映射到相应的字符

PS: 检查了线程，但无法理解这个和 c++: Power set generated by bits

Answer 1

想法是大小为 n 的集合的幂集恰好有 2^n 个元素，与长度最多为 n 的不同二进制数完全相同。

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

附言根据要求，对映射进行更详细的解释:如果您有递归算法，则您的流程由您在递归调用中遍历数据结构的方式决定。这是解决许多问题的一种非常直观和自然的方法。

如果您出于任何原因想要在不使用递归的情况下解决此类问题，例如使用更少的时间和内存，那么您将面临使此遍历显式化的艰巨任务。

当我们使用一个循环和一个假设一组特定值的循环变量时，我们需要确保映射循环变量的每个值，例如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"));}

}