代码之家 › 专栏 › 技术社区 › ahmet alp balkan

如何获取字符串(Java或C++等)的所有子序列组合

algorithm c++ java

ahmet alp balkan · 技术社区 · 16 年前

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

-->1 2 3 4 5
-->12 13 14 15 23 24 25 34 35 45
--&燃气轮机;123 124 125 234 235 345
-->1234 1235 1245 1345 2345
--GT;12345

请注意,我将它们按不同的字符数分组,但没有更改它们的顺序。我需要一个方法/函数来实现这一点。

12 回复 | 直到 9 年前

Community Mohan Dere 9 年前

你想要一台动力装置。下面是有关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,所以我会在半路上遇到你,给你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;
        }
    }

outis 16 年前

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

参考文献:

“ Efficiently Enumerating the Subsets of a Set “Loughry、Hemert和Schoofs
“ Generating Subsets “石溪算法库

Community Mohan Dere 14 年前

方法清理方法可以通过如下的递归实现。

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");
        }
}

Matthieu N. 16 年前

在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()));
}

Adrien Plisson 16 年前

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

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')]

sergtk 16 年前

您可以使用下面的类(在爪哇):

class Combinations {

  String input;
  StringBuilder cur;

  private void next(int pos, int reminder) {
    cur.append(input.charAt(pos));

    if (reminder == 1) {
      System.out.println(cur);
    } else {
      for (int i = pos + 1; i + reminder - 1 <= input.length(); i++)
        next(i, reminder - 1);
    }
    cur.deleteCharAt(cur.length() - 1);
  }

  public void generate(String input) {
    cur = new StringBuilder();
    this.input = input;
    for (int length = 1; length <= input.length(); length++)
      for (int pos = 0; pos + length <= input.length(); pos++)
        next(pos, length);
  }
}

要运行示例,请使用以下代码:

new Combinations().generate("12345");

输出的顺序与示例中的顺序相同。它不需要存储所有子集,然后对它们进行排序以获得您描述的顺序。

digitaljoel 13 年前

Java实现OUTIS的答案,将输入字符串作为ARG。

import java.util.ArrayList;
import java.util.List;

public class Combo {

  public static void main(String[] args) {
    List<String> results = new ArrayList<String>();
    for ( int i = 1; i <= (1<<(args.length))-1; i++ ) {
      StringBuilder builder = new StringBuilder();
      for ( int j = 0; j < args.length; j++ ) {
        if ( (i & (1<<j)) != 0) {
          builder.append(args[j]);
        }
      }
      results.add(builder.toString());
    }
    System.out.println( results );
  }
}

这是跑步。

> javac Combo.java
> java Combo A B C
[A, B, AB, C, AC, BC, ABC]

sth 14 年前

在爪哇中给出生成字符串的所有可能组合的代码。长度为4的字符串的所有可能组合为2^4(2提升到幂4)。一般来说,对于长度为n的字符串,可能的组合为2^n(2上升到幂n)。因此代码:

    class Perms
    {
    public void permsOfString(String a)
      {
     int x = 1;

     /* 
          Computes 2^string length

     */

     for(int i = 0;i<a.length() ;i++)
     {
         x = x * 2;
     }
     /*
            Iterate through all the possible combinations using a binary value of the number

      */
     for(int i = 1 ;i<x;i++)
     {

         String binStr = Integer.toBinaryString(i); // Convert i to binary string 
         for(int j = binStr.length() ; j <  a.length() ;j++)
         {
             binStr = "0"+binStr; // left pad with 0s
         }
   /*loop through the binary string if a character at the string is '1' note the    index,then display the character of the given string with that index */

          for(int k = 0; k <binStr.length();k++)
          {
             if(binStr.charAt(k) == '0') continue;
             else
             {
                 System.out.print(a.charAt(k));
             }

          }
         System.out.println();

     }

    }
    public static void main(String[]s)
  {
Perms p = new Perms();
p.permsOfString("abcd");
   }
}

Community Mohan Dere 9 年前

Adrien Plisson's answer 显示如何在Python中检索指定长度的所有子序列(对于任意序列数据类型)。操作指定他使用字符串,并且他希望 全部的 子序列。因此,使用 itertools.combinations 我们定义:

>>> from itertools import combinations
>>> def subseq_combos(inp):
...     return (''.join(s) for r in range(len(inp) + 1) for s in combinations(inp, r))
... 
>>> list(subseq_combos('12345'))
['', '1', '2', '3', '4', '5', '12', '13', '14', '15', '23', '24', '25', '34', '35', '45', '123', '124', '125', '134', '135', '145', '234', '235', '245', '345', '1234', '1235', '1245', '1345', '2345', '12345']

(如果应省略空的子序列,则使用 range(1, len(inp) + 1)) )

Madhu S. Kapoor 13 年前

C实施

//Usage
combinations((char*)"",(char*)"12346897909787");


void combinations(char* suffix,char* prefix){
    if(NULL ==prefix || NULL == suffix){ return ;}
    int prefixLen = strlen(prefix);
    printf("\n[%s]",suffix);
    int slen  = strlen(suffix);
    char* s   = (char*)malloc(slen+2);
    s[slen+1] = '\0';
    for(int i=0;i<prefixLen;i++){
        strcpy(s,suffix);
        s[slen]  = prefix[i];
        int npfl = prefixLen-(i+1);
        char* p  = (char*) malloc(npfl+1);
        p[npfl]  = '\0';
        strcpy(p,prefix+i+1);
        combinations(s,p);
        free(p);
    }
    free(s);
}

Pang Ajmal PraveeN 9 年前

C++解决方案:

#include<iostream>
#include<string>

using namespace std;

int sub[10];

void next(int max, int length) {

    int pos = length - 1;

    //find first digit that can be increased
    while(pos >= 0)
    {
        if(sub[pos] == max - (length - 1 - pos))
            pos--;

        else
            break;
    }

        sub[pos]++; //increase digit

        //update other digits
        for(int a = pos+1; a < length; a++)
            sub[a] = sub[a-1] + 1;

}

int main()
{
    string word;
    cin >> word; 

    int max = word.length() - 1; //max value


    for(int n=1; n <= max+1; n++)
    {

        cout << n << "\n----\n";

        for(int i = 0; i < n; i++)
        {
            sub[i] = i;
        }

        for(int a = 0; ; a++)
        {               
            for(int b=0; b < n; b++)
                cout << word[sub[b]];

            cout << '\n';

            if(sub[0] == max - (n - 1))
                break;

            else
                next(max, n); //maximum value and last position
        }   

        cout << '\n';

    }   


    return 0;
 }
> for input :Sigma
> output is
1
----
s
i
g
m
a

2
----
si
sg
sm
sa
ig
im
ia
gm
ga
ma

3
----
sig
sim
sia
sgm
sga
sma
igm
iga
ima
gma

4
----
sigm
siga
sima
sgma
igma

5
----
sigma

-1

pillmuncher 16 年前

哎呀,回答错误:

python中特定长度的子序列:

def subseqs(seq, length):
    for i in xrange(len(seq) - length + 1):
        yield seq[i:i+length]

使用方法如下:

for each in subseqs("hello", 3):
    print each

印刷品:

hel
ell
llo

要生成所有子序列,请执行以下操作:

for i in xrange(len("hello")):
    for each in subseqs("hello", i + 1):
        print each

印刷品:

h
e
l
l
o
he
el
ll
lo
hel
ell
llo
hell
ello
hello

米克。

现在我明白了,你想要的是子集,而不是子列表。