python 字符串按分隔符拆分所有可能的排列
python string split by separator all possible permutations
这可能与 Python 3.3: Split string and create all combinations 类似的问题密切相关，但我无法从中推断出 pythonic 解决方案。
问题是：
假设有一个 str，例如 'hi|guys|whats|app'，我需要用分隔符拆分该 str 的所有排列。示例：
#splitting only once
['hi','guys|whats|app']
['hi|guys','whats|app']
['hi|guys|whats','app']
#splitting only twice
['hi','guys','whats|app']
['hi','guys|whats','app']
#splitting only three times
...
etc
我可以编写一个回溯算法，但是 python（例如 itertools）是否提供了一个可以简化该算法的库？
提前致谢！！
一种方法使用combinations and chain
from itertools import combinations, chain
def partition(alist, indices):
#
pairs = zip(chain([0], indices), chain(indices, [None]))
return (alist[i:j] for i, j in pairs)
s = 'hi|guys|whats|app'
delimiter_count = s.count("|")
splits = s.split("|")
for i in range(1, delimiter_count + 1):
print("split", i)
for combination in combinations(range(1, delimiter_count + 1), i):
res = ["|".join(part) for part in partition(splits, combination)]
print(res)
输出
split 1
['hi', 'guys|whats|app']
['hi|guys', 'whats|app']
['hi|guys|whats', 'app']
split 2
['hi', 'guys', 'whats|app']
['hi', 'guys|whats', 'app']
['hi|guys', 'whats', 'app']
split 3
['hi', 'guys', 'whats', 'app']
我们的想法是生成所有方法来选择（或删除）分隔符 1、2、3 次，然后从那里生成分区。
这是我想出的一个递归函数：
def splitperms(string, i=0):
if len(string) == i:
return [[string]]
elif string[i] == "|":
return [*[[string[:i]] + split for split in splitperms(string[i + 1:])], *splitperms(string, i + 1)]
else:
return splitperms(string, i + 1)
输出：
>>> splitperms('hi|guys|whats|app')
[['hi', 'guys', 'whats', 'app'], ['hi', 'guys', 'whats|app'], ['hi', 'guys|whats', 'app'], ['hi', 'guys|whats|app'], ['hi|guys', 'whats', 'app'], ['hi|guys', 'whats|app'], ['hi|guys|whats', 'app'], ['hi|guys|whats|app']]
>>>
一种方法，一旦你拆分了字符串，就是使用itertools.combinations定义列表中的拆分点，其他位置应该再次融合。
def lst_merge(lst, positions, sep='|'):
'''merges a list on points other than positions'''
'''A, B, C, D and 0, 1 -> A, B, C|D'''
a = -1
out = []
for b in list(positions)+[len(lst)-1]:
out.append('|'.join(lst[a+1:b+1]))
a = b
return out
def split_comb(s, split=1, sep='|'):
from itertools import combinations
l = s.split(sep)
return [lst_merge(l, pos, sep=sep)
for pos in combinations(range(len(l)-1), split)]
例子
>>> split_comb('hi|guys|whats|app', 0)
[['hi|guys|whats|app']]
>>> split_comb('hi|guys|whats|app', 1)
[['hi', 'guys|whats|app'],
['hi|guys', 'whats|app'],
['hi|guys|whats', 'app']]
>>> split_comb('hi|guys|whats|app', 2)
[['hi', 'guys', 'whats|app'],
['hi', 'guys|whats', 'app'],
['hi|guys', 'whats', 'app']]
>>> split_comb('hi|guys|whats|app', 3)
[['hi', 'guys', 'whats', 'app']]
>>> split_comb('hi|guys|whats|app', 4)
[] ## impossible
理由
ABCD -> A B C D
0 1 2
combinations of split points: 0/1 or 0/2 or 1/2
0/1 -> merge on 2 -> A B CD
0/2 -> merge on 1 -> A BC D
1/2 -> merge on 0 -> AB C D
泛型函数
这是一个通用版本，像上面一样工作，但也将 -1 作为 split 的参数，在这种情况下它将输出所有组合
def lst_merge(lst, positions, sep='|'):
a = -1
out = []
for b in list(positions)+[len(lst)-1]:
out.append('|'.join(lst[a+1:b+1]))
a = b
return out
def split_comb(s, split=1, sep='|'):
from itertools import combinations, chain
l = s.split(sep)
if split == -1:
pos = chain.from_iterable(combinations(range(len(l)-1), r)
for r in range(len(l)+1))
else:
pos = combinations(range(len(l)-1), split)
return [lst_merge(l, pos, sep=sep)
for pos in pos]
示例：
>>> split_comb('hi|guys|whats|app', -1)
[['hi|guys|whats|app'],
['hi', 'guys|whats|app'],
['hi|guys', 'whats|app'],
['hi|guys|whats', 'app'],
['hi', 'guys', 'whats|app'],
['hi', 'guys|whats', 'app'],
['hi|guys', 'whats', 'app'],
['hi', 'guys', 'whats', 'app']]
您可以找到 index 所有 '|' 然后在所有组合中将 '|' 替换为 ',' 然后拆分基础 ',' 如下所示：
>>> from itertools import combinations
>>> st = 'hi|guys|whats|app'
>>> idxs_rep = [idx for idx, s in enumerate(st) if s=='|']
>>> def combs(x):
... return [c for i in range(len(x)+1) for c in combinations(x,i)]
>>> for idxs in combs(idxs_rep):
... lst_st = list(st)
... for idx in idxs:
... lst_st[idx] = ','
... st2 = ''.join(lst_st)
... print(st2.split(','))
['hi|guys|whats|app']
['hi', 'guys|whats|app']
['hi|guys', 'whats|app']
['hi|guys|whats', 'app']
['hi', 'guys', 'whats|app']
['hi', 'guys|whats', 'app']
['hi|guys', 'whats', 'app']
['hi', 'guys', 'whats', 'app']
如果您想要 所有 个分区，请尝试从 more-itertools:
partitions
from more_itertools import partitions
s = 'hi|guys|whats|app'
for p in partitions(s.split('|')):
print(list(map('|'.join, p)))
输出：
['hi|guys|whats|app']
['hi', 'guys|whats|app']
['hi|guys', 'whats|app']
['hi|guys|whats', 'app']
['hi', 'guys', 'whats|app']
['hi', 'guys|whats', 'app']
['hi|guys', 'whats', 'app']
['hi', 'guys', 'whats', 'app']
如果你只想要一定数量的分割，那么不是在 所有 分隔符处分割然后重新加入这些部分，你可以只获得分隔符索引和相应地获取子字符串：
from itertools import combinations
s = 'hi|guys|whats|app'
splits = 2
indexes = [i for i, c in enumerate(s) if c == '|']
for I in combinations(indexes, splits):
print([s[i+1:j] for i, j in zip([-1, *I], [*I, None])])
输出：
['hi', 'guys', 'whats|app']
['hi', 'guys|whats', 'app']
['hi|guys', 'whats', 'app']
令我惊讶的是大多数答案都使用 combinations，这显然是一个 二元幂 序列（即多个 二元笛卡尔积串联).
让我详细说明一下：如果我们有 n 个分隔符，我们就有 2**n 个可能的字符串，其中每个分隔符是 on 或 off。因此，如果我们将从 0 到 2**n 的整数序列的每一位映射到每个分隔符（0 表示我们不拆分，1 表示我们拆分）我们可以生成整个事情非常有效（没有 运行 进入堆栈深度限制，并且能够 pause 和 resume 生成器 - 甚至运行 它是并行的！- 只使用一个简单的整数来跟踪进度）。
def partition(index, tokens, separator):
def helper():
n = index
for token in tokens:
yield token
if n % 2:
yield separator
n //= 2
return ''.join(helper())
def all_partitions(txt, separator):
tokens = txt.split(separator)
for i in range(2**(len(tokens)-1)):
yield partition(i, tokens, separator)
for x in all_partitions('hi|guys|whats|app', '|'):
print(x)
解释：
hi|guys|whats|app
^ ^ ^
bit 0 1 2 (big endian representation)
hi guys whats up
^ ^ ^
0 = 0 0 0
hi|guys whats up
^ ^ ^
1 = 1 0 0
hi guys|whats up
^ ^ ^
2 = 0 1 0
hi|guys|whats up
^ ^ ^
3 = 1 1 0
hi guys whats|up
^ ^ ^
4 = 0 0 1
hi|guys whats|up
^ ^ ^
5 = 1 0 1
hi guys|whats|up
^ ^ ^
6 = 0 1 1
hi|guys|whats|up
^ ^ ^
7 = 1 1 1
这可能与 Python 3.3: Split string and create all combinations 类似的问题密切相关，但我无法从中推断出 pythonic 解决方案。
问题是：
假设有一个 str，例如 'hi|guys|whats|app'，我需要用分隔符拆分该 str 的所有排列。示例：
#splitting only once
['hi','guys|whats|app']
['hi|guys','whats|app']
['hi|guys|whats','app']
#splitting only twice
['hi','guys','whats|app']
['hi','guys|whats','app']
#splitting only three times
...
etc
我可以编写一个回溯算法，但是 python（例如 itertools）是否提供了一个可以简化该算法的库？
提前致谢！！
一种方法使用combinations and chain
from itertools import combinations, chain
def partition(alist, indices):
#
pairs = zip(chain([0], indices), chain(indices, [None]))
return (alist[i:j] for i, j in pairs)
s = 'hi|guys|whats|app'
delimiter_count = s.count("|")
splits = s.split("|")
for i in range(1, delimiter_count + 1):
print("split", i)
for combination in combinations(range(1, delimiter_count + 1), i):
res = ["|".join(part) for part in partition(splits, combination)]
print(res)
输出
split 1
['hi', 'guys|whats|app']
['hi|guys', 'whats|app']
['hi|guys|whats', 'app']
split 2
['hi', 'guys', 'whats|app']
['hi', 'guys|whats', 'app']
['hi|guys', 'whats', 'app']
split 3
['hi', 'guys', 'whats', 'app']
我们的想法是生成所有方法来选择（或删除）分隔符 1、2、3 次，然后从那里生成分区。
这是我想出的一个递归函数：
def splitperms(string, i=0):
if len(string) == i:
return [[string]]
elif string[i] == "|":
return [*[[string[:i]] + split for split in splitperms(string[i + 1:])], *splitperms(string, i + 1)]
else:
return splitperms(string, i + 1)
输出：
>>> splitperms('hi|guys|whats|app')
[['hi', 'guys', 'whats', 'app'], ['hi', 'guys', 'whats|app'], ['hi', 'guys|whats', 'app'], ['hi', 'guys|whats|app'], ['hi|guys', 'whats', 'app'], ['hi|guys', 'whats|app'], ['hi|guys|whats', 'app'], ['hi|guys|whats|app']]
>>>
一种方法，一旦你拆分了字符串，就是使用itertools.combinations定义列表中的拆分点，其他位置应该再次融合。
def lst_merge(lst, positions, sep='|'):
'''merges a list on points other than positions'''
'''A, B, C, D and 0, 1 -> A, B, C|D'''
a = -1
out = []
for b in list(positions)+[len(lst)-1]:
out.append('|'.join(lst[a+1:b+1]))
a = b
return out
def split_comb(s, split=1, sep='|'):
from itertools import combinations
l = s.split(sep)
return [lst_merge(l, pos, sep=sep)
for pos in combinations(range(len(l)-1), split)]
例子
>>> split_comb('hi|guys|whats|app', 0)
[['hi|guys|whats|app']]
>>> split_comb('hi|guys|whats|app', 1)
[['hi', 'guys|whats|app'],
['hi|guys', 'whats|app'],
['hi|guys|whats', 'app']]
>>> split_comb('hi|guys|whats|app', 2)
[['hi', 'guys', 'whats|app'],
['hi', 'guys|whats', 'app'],
['hi|guys', 'whats', 'app']]
>>> split_comb('hi|guys|whats|app', 3)
[['hi', 'guys', 'whats', 'app']]
>>> split_comb('hi|guys|whats|app', 4)
[] ## impossible
理由
ABCD -> A B C D
0 1 2
combinations of split points: 0/1 or 0/2 or 1/2
0/1 -> merge on 2 -> A B CD
0/2 -> merge on 1 -> A BC D
1/2 -> merge on 0 -> AB C D
泛型函数
这是一个通用版本，像上面一样工作，但也将 -1 作为 split 的参数，在这种情况下它将输出所有组合
def lst_merge(lst, positions, sep='|'):
a = -1
out = []
for b in list(positions)+[len(lst)-1]:
out.append('|'.join(lst[a+1:b+1]))
a = b
return out
def split_comb(s, split=1, sep='|'):
from itertools import combinations, chain
l = s.split(sep)
if split == -1:
pos = chain.from_iterable(combinations(range(len(l)-1), r)
for r in range(len(l)+1))
else:
pos = combinations(range(len(l)-1), split)
return [lst_merge(l, pos, sep=sep)
for pos in pos]
示例：
>>> split_comb('hi|guys|whats|app', -1)
[['hi|guys|whats|app'],
['hi', 'guys|whats|app'],
['hi|guys', 'whats|app'],
['hi|guys|whats', 'app'],
['hi', 'guys', 'whats|app'],
['hi', 'guys|whats', 'app'],
['hi|guys', 'whats', 'app'],
['hi', 'guys', 'whats', 'app']]
您可以找到 index 所有 '|' 然后在所有组合中将 '|' 替换为 ',' 然后拆分基础 ',' 如下所示：
>>> from itertools import combinations
>>> st = 'hi|guys|whats|app'
>>> idxs_rep = [idx for idx, s in enumerate(st) if s=='|']
>>> def combs(x):
... return [c for i in range(len(x)+1) for c in combinations(x,i)]
>>> for idxs in combs(idxs_rep):
... lst_st = list(st)
... for idx in idxs:
... lst_st[idx] = ','
... st2 = ''.join(lst_st)
... print(st2.split(','))
['hi|guys|whats|app']
['hi', 'guys|whats|app']
['hi|guys', 'whats|app']
['hi|guys|whats', 'app']
['hi', 'guys', 'whats|app']
['hi', 'guys|whats', 'app']
['hi|guys', 'whats', 'app']
['hi', 'guys', 'whats', 'app']
如果您想要 所有 个分区，请尝试从 more-itertools:
partitions
from more_itertools import partitions
s = 'hi|guys|whats|app'
for p in partitions(s.split('|')):
print(list(map('|'.join, p)))
输出：
['hi|guys|whats|app']
['hi', 'guys|whats|app']
['hi|guys', 'whats|app']
['hi|guys|whats', 'app']
['hi', 'guys', 'whats|app']
['hi', 'guys|whats', 'app']
['hi|guys', 'whats', 'app']
['hi', 'guys', 'whats', 'app']
如果你只想要一定数量的分割，那么不是在 所有 分隔符处分割然后重新加入这些部分，你可以只获得分隔符索引和相应地获取子字符串：
from itertools import combinations
s = 'hi|guys|whats|app'
splits = 2
indexes = [i for i, c in enumerate(s) if c == '|']
for I in combinations(indexes, splits):
print([s[i+1:j] for i, j in zip([-1, *I], [*I, None])])
输出：
['hi', 'guys', 'whats|app']
['hi', 'guys|whats', 'app']
['hi|guys', 'whats', 'app']
令我惊讶的是大多数答案都使用 combinations，这显然是一个 二元幂 序列（即多个 二元笛卡尔积串联).
让我详细说明一下：如果我们有 n 个分隔符，我们就有 2**n 个可能的字符串，其中每个分隔符是 on 或 off。因此，如果我们将从 0 到 2**n 的整数序列的每一位映射到每个分隔符（0 表示我们不拆分，1 表示我们拆分）我们可以生成整个事情非常有效（没有 运行 进入堆栈深度限制，并且能够 pause 和 resume 生成器 - 甚至运行 它是并行的！- 只使用一个简单的整数来跟踪进度）。
def partition(index, tokens, separator):
def helper():
n = index
for token in tokens:
yield token
if n % 2:
yield separator
n //= 2
return ''.join(helper())
def all_partitions(txt, separator):
tokens = txt.split(separator)
for i in range(2**(len(tokens)-1)):
yield partition(i, tokens, separator)
for x in all_partitions('hi|guys|whats|app', '|'):
print(x)
解释：
hi|guys|whats|app
^ ^ ^
bit 0 1 2 (big endian representation)
hi guys whats up
^ ^ ^
0 = 0 0 0
hi|guys whats up
^ ^ ^
1 = 1 0 0
hi guys|whats up
^ ^ ^
2 = 0 1 0
hi|guys|whats up
^ ^ ^
3 = 1 1 0
hi guys whats|up
^ ^ ^
4 = 0 0 1
hi|guys whats|up
^ ^ ^
5 = 1 0 1
hi guys|whats|up
^ ^ ^
6 = 0 1 1
hi|guys|whats|up
^ ^ ^
7 = 1 1 1