假设我有一个字符串“ 12345”,我应该获得该字符串的所有子序列组合,例如:
请注意,我将它们分组为不同数量的字符,但未更改其顺序。我需要一个方法/函数来做到这一点。
您需要电源。这里是所有StackOverflow上提及的问题powersets或发电机组。
这是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;
}
}
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句