如何获取一个字符串的所有子组合(Java或C ++等) [英] How to obtain all subsequence combinations of a String (in Java, or C++ etc)
问题描述
比方说我有一个字符串12345我要获得这个字符串的所有子组合,如:
Let's say I've a string "12345" I should obtain all subsequence combinations of this string such as:
- - > 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
请注意,我归纳他们在不同的数字字符,但不改变它们的顺序。我需要一个方法/函数做到这一点。
Please note that I grouped them in different number of chars but not changed their order. I need a method/function does that.
推荐答案
您想幂。下面是关于计算器中提到 powersets 或的发电机组的。
You want a powerset. Here are all the questions on StackOverflow that mention powersets or power sets.
下面是用Python的基本实现:
Here is a basic implementation in 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
这里是它的输出:
And here is its output:
[]
[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]
注意,它的第一个结果是空集。从这个中的xrange更改迭代我(2 ** N):
这个对我的xrange(1,2 ** N):
,如果你想跳过空集。
Notice that its first result is the empty set. Change the iteration from this for i in xrange(2**n):
to this for i in xrange(1, 2**n):
if you want to skip an empty set.
下面是code适合于产生字符串输出:
Here is the code adapted to produce string output:
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
Edit 2009-10-24
好了,我看你是部分Java中的实现。我不知道Java的,所以我会半路遇见你,给你code在C#:</ P>
Okay, I see you are partial to an implementation in Java. I don't know Java, so I'll meet you halfway and give you code in 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;
}
}
这篇关于如何获取一个字符串的所有子组合(Java或C ++等)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!