如何获取String的所有子序列组合(在Java或C++等中)

Question

假设我有一个字符串"12345"我应该获得此字符串的所有子序列组合,例如:

1. - > 1 2 3 4 5
2. - > 12 13 14 15 23 24 25 34 35 45
3. - > 123 124 125 234 235 345
4. - > 1234 1235 1245 1345 2345
5. - > 12345

请注意,我将它们分组为不同数量的字符,但未更改其顺序.我需要一个方法/函数来做到这一点.

Answer 1

你想要一个powerset.以下是关于StackOverflow的所有提及powersets或power sets的问题.

这是python中的基本实现:

def powerset(s):
    n = len(s)
    masks = [1<<j for j in xrange(n)]
    for i in xrange(2**n):
        yield [s[j] for j in range(n) if (masks[j] & i)]


if __name__ == '__main__':
    for elem in powerset([1,2,3,4,5]):
        print elem

这是它的输出:

[]
[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, 4]
[5]
[1, 5]
[2, 5]
[1, 2, 5]
[3, 5]
[1, 3, 5]
[2, 3, 5]
[1, 2, 3, 5]
[4, 5]
[1, 4, 5]
[2, 4, 5]
[1, 2, 4, 5]
[3, 4, 5]
[1, 3, 4, 5]
[2, 3, 4, 5]
[1, 2, 3, 4, 5]

请注意,它的第一个结果是空集.从这个迭代改变for i in xrange(2**n):这个for i in xrange(1, 2**n):,如果你想跳过一个空集.

以下是适合生成字符串输出的代码:

def powerset(s):
    n = len(s)
    masks = [1<<j for j in xrange(n)]
    for i in xrange(2**n):
        yield "".join([str(s[j]) for j in range(n) if (masks[j] & i)])

编辑2009-10-24

好的,我看到你偏爱Java中的实现.我不认识Java,所以我会半途而废,并用C#给你代码:

    static public IEnumerable<IList<T>> powerset<T>(IList<T> s)
    {
        int n = s.Count;
        int[] masks = new int[n];
        for (int i = 0; i < n; i++)
            masks[i] = (1 << i);
        for (int i = 0; i < (1 << n); i++)
        {
            List<T> newList = new List<T>(n);
            for (int j = 0; j < n; j++)
                if ((masks[j] & i) != 0)
                    newList.Add(s[j]);
            yield return newList;
        }
    }

Answer 2

用于生成一组大小为N的子集的最简单算法是使用N比特来考虑所有二进制数.数字中的每个位置代表集合中的元素.如果数字中的位为1,则相应的set元素位于子集中,否则该元素不在子集中.由于数字中的位是有序的,因此保留了原始集的顺序.

参考文献:

1. " 有效地枚举集合的子集 "; Loughry,Hemert和Schoofs
2. " 生成子集 "; Stony Brook算法库

Answer 3

方式清洁方法可以通过递归实现如下.

Public class StrManipulation{

    public static void combinations(String suffix,String prefix){
        if(prefix.length()<0)return;
        System.out.println(suffix);
        for(int i=0;i<prefix.length();i++)
         combinations(suffix+prefix.charAt(i),prefix.substring(i+1,prefix.length()));
    }

    public static void main (String args[]){
        combinations("","12345");
        }
}

Answer 4

在C++中给出以下例程:

template <typename Iterator>
bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
   /* Credits: Mark Nelson http://marknelson.us */
   if ((first == last) || (first == k) || (last == k))
      return false;
   Iterator i1 = first;
   Iterator i2 = last;
   ++i1;
   if (last == i1)
      return false;
   i1 = last;
   --i1;
   i1 = k;
   --i2;
   while (first != i1)
   {
      if (*--i1 < *i2)
      {
         Iterator j = k;
         while (!(*i1 < *j)) ++j;
         std::iter_swap(i1,j);
         ++i1;
         ++j;
         i2 = k;
         std::rotate(i1,j,last);
         while (last != j)
         {
            ++j;
            ++i2;
         }
         std::rotate(k,i2,last);
         return true;
      }
   }
   std::rotate(first,k,last);
   return false;
}

然后,您可以继续执行以下操作:

std::string s = "12345";
for(std::size_t i = 1; i <= s.size(); ++i)
{
   do
   {
      std::cout << std::string(s.begin(),s.begin() + i) << std::endl;
   }
   while(next_combination(s.begin(),s.begin() + i,s.end()));
}

Answer 5

使用python,itertools模块定义了一个combination()方法,它可以满足你的需要.

from itertools import *
list(combinations( '12345', 2 ))

会给你:

[('1', '2'), ('1', '3'), ('1', '4'), ('1', '5'), ('2', '3'), ('2', '4'), ('2', '5'), ('3', '4'), ('3', '5'), ('4', '5')]