如何获取String的所有子序列组合（在Java或C ++等中）
假设我有一个字符串“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
- – > 12345
请注意，我将它们分组在不同数量的字符中但未更改其顺序。 我需要一个方法/函数来做到这一点。
你想要一个powerset。 以下是关于StackOverflow的所有提及powersets或power sets的问题 。
这是python中的基本实现：
def powerset(s): n = len(s) masks = [1< 这是它的输出：
[] [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(2**n):更改for i in xrange(1, 2**n):如果要跳过空集。
以下是适合生成字符串输出的代码：
def powerset(s): n = len(s) masks = [1<
编辑2009-10-24
好的，我看到你偏爱Java中的实现。 我不认识Java，所以我会中途见到你并用C＃给你代码：
static public IEnumerable> powerset(IList 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 newList = new List (n); for (int j = 0; j < n; j++) if ((masks[j] & i) != 0) newList.Add(s[j]); yield return newList; } }
用于生成一组大小为N的子集的最简单算法是使用N比特来考虑所有二进制数。 数字中的每个位置代表集合中的元素。 如果数字中的位为1，则相应的set元素位于子集中，否则该元素不在子集中。 由于数字中的位是有序的，因此保留了原始集的顺序。
参考文献：
- “ 有效地枚举集合的子集 ”; Loughry，Hemert和Schoofs
- “ 生成子集 ”; Stony Brook算法库
方式清洁方法可以通过递归实现如下。
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
在C ++中给出以下例程：
templatebool next_combination（const Iterator first，Iterator k，const Iterator last） { / *致谢：Mark Nelson http://marknelson.us * / if（（first == last）||（first == k）||（last == k）） 返回虚假; 迭代器i1 =第一个; 迭代器i2 =最后; ++ I1; if（last == i1） 返回虚假; i1 =最后; --i1; i1 = k; --i2; while（first！= i1） { if（* - i1 <* i2） { 迭代器j = k; while（！（* i1 <* j））++ j; 的std :: iter_swap（I1，J）; ++ I1; ++焦耳; i2 = k; 的std ::旋转（I1，J，最后一个）; 而（最后！= j） { ++焦耳; ++ I2; } 的std ::旋转（K，I2，最后一个）; 返回true; } } 的std ::旋转（第一，K，最后一个）; 返回虚假; }
然后，您可以继续执行以下操作：
std :: string s =“12345”;
for（std :: size_t i = 1; i <= s.size（）; ++ i）
{
做
{
std :: cout << std :: string（s.begin（），s.begin（）+ i）<< std :: endl;
}
while（next_combination（s.begin（），s.begin（）+ i，s.end（）））;
}
使用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')]
您可以使用以下类（在Java中）：
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");
输出的顺序与示例中的顺序相同。 它不需要存储所有子集，然后对它们进行排序以获得您描述的顺序。
outis’答案的Java实现，将输入字符串作为args。
import java.util.ArrayList; import java.util.List; public class Combo { public static void main(String[] args) { List results = new ArrayList (); 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<
这是一个运行。
> javac Combo.java > java Combo ABC [A, B, AB, C, AC, BC, ABC]
生成所有可能的字符串组合的代码在java中给出。 长度为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
Adrien Plisson的答案显示了如何在Python中检索指定长度的所有子序列（对于任意序列数据类型）。 OP指定他使用字符串，并且他想要所有子序列。 因此，使用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)) 。）
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
C ++解决方案：
#include #include 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
哎呀，错误答案：
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
米克。
现在我明白了，你想要的是子集，而不是子列表。