Python字符串子集的所有组合

Question

我需要一个字符串的所有子集组合。另外，长度为1的子集只能跟在长度大于1的子集后面。例如，对于字符串4824，结果应该是：

 [ [4, 824], [4, 82, 4], [48, 24], [482, 4], [4824] ]

迄今为止，我已经通过以下方式检索到所有可能的子集：

    length = len(number)
    ss = []
    for i in xrange(length):
        for j in xrange(i,length):
            ss.append(number[i:j + 1])

这给了我：

  ['4', '48', '482', '4824', '8', '82', '824', '2', '24', '4']

但是我不知道如何将它们组合起来。

- wasp256

---

也许这可以帮助你 列表推导式。 - emartinelli

我认为你对幂集很感兴趣。 - Cory Kramer

这不是关于幂集的问题。我不知道正确的术语，但是这个问题肯定是相关的，并且那里给出的一些答案可以针对额外要求进行改进，即“长度为1的子集只能后跟长度> 1的子集”。 - John Y

[4, 8, 24] 为什么没有？ - Jose Ricardo Bustos M.

@skolsuper，我发布了一个答案，基于它...希望是正确的。 - Jose Ricardo Bustos M.

Answer 1

首先，编写一个函数来生成字符串的所有分割：

def partitions(s):
    if s:
        for i in range(1, len(s) + 1):
            for p in partitions(s[i:]):
                yield [s[:i]] + p
    else:
        yield []

这将迭代所有可能的第一个段（一个字符，两个字符等），并将其与字符串余下部分的所有分区相结合。

>>> list(partitions("4824"))
[['4', '8', '2', '4'], ['4', '8', '24'], ['4', '82', '4'], ['4', '824'], ['48', '2', '4'], ['48', '24'], ['482', '4'], ['4824']]

现在，您可以过滤与您的条件匹配的内容，即那些没有连续长度为一的两个子字符串的内容。

>>> [p for p in partitions("4824") if not any(len(x) == len(y) == 1 for x, y in zip(p, p[1:]))]
[['4', '82', '4'], ['4', '824'], ['48', '24'], ['482', '4'], ['4824']]

这里，“zip(p, p[1:])”是一个常见的遍历所有相邻对的项目的方法。

---

更新：实际上，直接将您的限制条件纳入“partition”函数中也不难。只需跟踪最后一个段并相应地设置最小长度即可。

def partitions(s, minLength=1):
    if len(s) >= minLength:
        for i in range(minLength, len(s) + 1):
            for p in partitions(s[i:], 1 if i > 1 else 2):
                yield [s[:i]] + p
    elif not s:
        yield []

示例：

>>> print list(partitions("4824"))
[['4', '82', '4'], ['4', '824'], ['48', '24'], ['482', '4'], ['4824']]

- tobias_k

---

对于较长的字符串来说，这种方法效率低下，因为你会生成很多将被过滤掉的分区。 - chepner

@chepner同意。添加了另一个算法，在生成解决方案的同时进行过滤。 - tobias_k

Answer 2

很有趣，如果能看到更多的测试用例。以下算法实现了你所说的功能：

s="4824"

def partitions(s):
  yield [s]
  if(len(s)>2):
    for i in range(len(s)-1, 0, -1):
      for g in partitions(s[i:]):
        out = [s[:i]] + g
        if not any([len(out[i]) == len(out[i+1]) and len(out[i])==1 for i in range(len(out)-1)]):
          yield out

list(partitions(s))

你将获得：

[['4824'], ['482', '4'], ['48', '24'], ['4', '824'], ['4', '82', '4']]

解释

我基于以下算法：

s="4824"

def partitions_original(s):
  #yield original string
  yield [s]
  if(len(s)>2):
    for i in range(len(s)-1, 0, -1):
      #divide string in two parts
      #iteration 1: a="482", b="4"
      #iteration 2: a="48", b="24"
      #iteration 3: a="4", b="824"
      a = s[:i]
      b = s[i:]
      #recursive call of b
      for g in partitions_original(b):
        #iteration 1: b="4", g=[['4']]
        #iteration 2: b="24", g=[['24']]
        #iteration 3: b="824", g=[['824'], ['82', '4'], ['8', '24']]
        yield [a] + g

list(partitions_original(s))

你需要的是：

[['4824'], ['482', '4'], ['48', '24'], ['4', '824'], 
['4', '82', '4'], ['4', '8', '24']]

问题是['4', '8', '24']......然后我必须在代码中添加if，因为"长度为1的子集只能跟随长度>1的子集"

[len(out[i]) == len(out[i+1]) and len(out[i])==1 for i in range(len(out)-1)]对于['4', '8', '24']返回[True, False].... any如果可迭代对象中有任何一个元素为真，则返回True。

注意

也可以使用：

if all([len(out[i]) != len(out[i+1]) or len(out[i])!=1 for i in range(len(out)-1)]):

- Jose Ricardo Bustos M.

Answer 3

我在这里做的是获取字符串的所有可能分割位置并消除最后一个。

例如，在一些由5个数字组成的字符串“12345”中，有4个可能的分割位置，称之为possibility = (0,0,0,0),(1,0,1,0)...其中(0,0,1,0)表示（不要分离1和2345，不要分离12和345，分离123和45，不要分离1234和5），因此您可以在验证条件的同时获得所有可能性，因为我们消除了（1,1,1,1）的情况。

import itertools
from math import factorial
from itertools import product

def get_comb(string):
    L = len(string_)
    combinisation = []

    for possibility in product([0,1], repeat=len(string_)-1):
        s = []
        indexes = [i for i in range(len(string_)-1) if list(possibility)[i]!=0]
        if sum(indexes) != 0:
            if sum(indexes) != len(string_)-1:
                for index in indexes:
                    s.append(string_[:index+1])
                s.append(string_[indexes[-1:][0]+1:])
                combinisation.append(s)
            else:
                combinisation.append(string_)
    return combinisation



string_ = '4824'
print "%s combinations:"%string_
print get_comb(string_)



string_ = '478952'
print "%s combinations:"%string_
print get_comb(string_)



string_ = '1234'
print "%s combinations:"%string_
print get_comb(string_)


>> 
4824 combinations:
[['482', '4'], ['48', '24'], '4824', ['4', '482', '4'], ['4', '48', '24'], '4824
']
478952 combinations:

[['47895', '2'], ['4789', '52'], ['4789', '47895', '2'], ['478', '952'], ['478',
 '47895', '2'], '478952', ['478', '4789', '47895', '2'], ['47', '8952'], '478952
', ['47', '4789', '52'], ['47', '4789', '47895', '2'], ['47', '478', '952'], ['4
7', '478', '47895', '2'], ['47', '478', '4789', '52'], ['47', '478', '4789', '47
895', '2'], ['4', '47895', '2'], ['4', '4789', '52'], ['4', '4789', '47895', '2'
], ['4', '478', '952'], ['4', '478', '47895', '2'], '478952', ['4', '478', '4789
', '47895', '2'], ['4', '47', '8952'], '478952', ['4', '47', '4789', '52'], ['4'
, '47', '4789', '47895', '2'], ['4', '47', '478', '952'], ['4', '47', '478', '47
895', '2'], ['4', '47', '478', '4789', '52'], ['4', '47', '478', '4789', '47895'
, '2']]

1234 combinations:

[['123', '4'], ['12', '34'], '1234', ['1', '123', '4'], ['1', '12', '34'], '1234
']

- farhawa

---

你的组合中似乎有一些重复的字符，例如 ['4', '482', '4']。此外，我建议在列表中使用更一致的数据类型，即使用 ['4824'] 而不是 '4824'。 - tobias_k

Answer 4

一个普通的代码可以这样写：

s=raw_input('enter the string:')
word=[]
for i in range(len(s)):
    for j in range(i,len(s)):
        word.append(s[i:j+1])

print word
print 'no of possible combinations:',len(word)

输出结果： 请输入字符串： 4824 ['4', '48', '482', '4824', '8', '82', '824', '2', '24', '4'] 可能的组合数：10

- Girish Chandra