2

谷歌搜索了一段时间以查找字符串的子集，我阅读了维基百科并提到

.....对于 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，我们可以运行 from 0to并为on位2^n - 1打印字符。 我无法得到的是如何以最优化的方式将这些位映射到相应的字符

PS：检查过的线程，但无法理解这一点和 c++：由位生成的功率集

4

2 回答 2

1

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

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

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

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

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

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

543210
101010

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

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

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

我们的映射也是有效的，因为我们选择的二进制数的长度最多等于我们集合的大小，因此位位置总是可以分配给集合中的一个元素。结合我们的输入集被选择为具有与幂集大小相同的大小 (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"));}

}
于 2014-07-11T08:20:07.010 回答
1

这是一种简单的方法（伪代码）：-

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 的字符串中的索引。

于 2014-07-11T10:37:25.100 回答