如何获得一个列表的所有组合，其中两个相邻的元素可以成为一个元素

Question

我正在尝试获取一个列表的所有组合，其中两个元素 彼此相邻 可能“成为一个”。例如;

>>> list = ['a', 'b', 'c', 'd']
>>> get_comb(list)
[['ab', 'c' 'd'], ['a', 'bc' 'd'], ['a', 'b', 'cd'] ['ab', 'cd']]

棘手的是两个元素可以合二为一，我在这个问题上卡了很久。我试过这样的东西；

list_split_up = [list[i:i+2] for i in range(0, len(list), 2)]
indexes = [str(i) for i in range(len(list_split_up)) if len(list_split_up[i])==2]
comb = [''.join(l) for i in range(len(indexes),0,-1) for l in itertools.combinations(indexes, i)]

在那里我得到了所有可能组合的索引，这样我就可以创建我想要的东西——但问题是它只给我像 ['ab', 'cd'] 这样的组合（因为我把列表分成两部分和两个），因此我不会得到我想要的 ['a', 'bc', 'd']。

Answer 1

这看起来是动态规划的完美案例，从头开始工作。

[] -> []
['e'] -> ['e']
['d', 'e'] -> ['de'] prepended to all solutions for []
               plus ['d'] prepended to all solutions for ['e']
['c', 'd', 'e'] -> ['cd'] prepended to all solutions for ['e']
                plus ['c'] prepended to all solutions for ['de']
and so on.

Answer 2

这是我的解决方案（l 是原始列表）：

import itertools

k=len(l)-1

m=[]

for i in range(1, len(l)//2+1):
    comb=[x for x in itertools.permutations([1]*i+[0]*(k-i))]
    m=list(set(m))
    m.extend(comb)

def isvalid(x):
    for i in range(len(x)-1):
        if x[i]==x[i+1]==1:
            return False
    return True

m=[i for i in m if isvalid(i)]

res=[]

for i in m:
    temp=[]
    for x in range(len(i)):
        if i[x]==0 and (x==0 or i[x-1]==0):
            temp.append(l[x])
        if i[x]==1:
            temp.append(l[x]+l[x+1])
    if i[-1]==0:
        temp.append(l[-1])
    res.append(temp)

res=[tuple(i) for i in res]
res=list(set(res))
print(res)

示例：

1.

l=  ['a', 'b', 'c', 'd']

输出：

[('ab', 'c', 'd'), ('a', 'b', 'cd'), ('a', 'bc', 'd'), ('ab', 'cd')]

l=['a', 'b', 'c', 'd', 'e']

输出：

[('ab', 'c', 'de'), ('a', 'b', 'cd', 'e'), ('a', 'bc', 'de'), ('a', 'b', 'c', 'de'), ('a', 'bc', 'd', 'e'), ('ab', 'c', 'd', 'e'), ('ab', 'cd', 'e')]

Answer 3

您可以对生成器使用递归：

l = ['a', 'b', 'c', 'd']
def get_groups(d):
  yield tuple(d)
  if (k:=len(d)) > 1:
    for i in range(len(d)-1):
      yield from get_groups([*d[:i], d[i]+d[i+1], *([] if i+2 >= k else d[i+2:])])

print(list(map(list, set(get_groups(l)))))

输出：

[['a', 'b', 'cd'], ['abc', 'd'], ['a', 'bc', 'd'], ['ab', 'c', 'd'], ['abcd'], ['a', 'bcd'], ['a', 'b', 'c', 'd'], ['ab', 'cd']]

Answer 4

设 n 为原始列表的长度。我们将假设一次可以组合的最大元素数为 max_len。所以如果max_len=2那么"abc"是无效的，但是"ab"是因为后者结合了2个相邻的元素，而前者结合了3个相邻的元素。

现在您可以将每个解决方案编码为要组合的元素数量的元组。所以["ab","c","d"]会被编码为[2,1,1]；类似地，["abcd"] 将是 [4]，["a","bcd"] 将是 [1,3] 等。现在我们已经将生成这些编码的问题减少了。

形式上这些编码有属性:

有集合[1, ..., max_len]
元素总和为n

生成这个的方法有很多种；这是一个。我们正在生成所有组合并过滤符合标准 1 和 2 的组合。然后从编码中获得解决方案。

from itertools import combinations_with_replacement, accumulate, takewhile

# generating the data
n = 4
ls = list(chr(ord('a')+e) for e in range(n))
print("data = ", ls)

# setting the maximum number of adjacent elements that can be combined at a time
max_len = 2
max_len = min(n,max_len)
print("max_len = ", max_len)

# actual implementation
combinations = combinations_with_replacement(range(1,max_len+1),n)
combinations_with_cumsum = (zip(e,accumulate(e)) for e in combinations)
combinations_till_maxElm = (list(takewhile(lambda x: x[1]<=n,e)) for e in combinations_with_cumsum)
combinations_till_maxElm = filter(lambda x:x[-1][1]==n, combinations_till_maxElm)

indices = (
    [0] + [e[1] for e in elm]
    for elm in set(map(tuple,combinations_till_maxElm))
)

indices_si_ei = (zip(e,e[1:]) for e in indices)

print("result = ", [["".join(ls[si:ei]) for si,ei in e] for e in indices_si_ei])

一起玩 = https://repl.it/@bigyanbhar/SO65365566#main.py

肯定有比生成所有组合更好的方法。最简单的方法是编写您自己的 combinations_with_replacement，这样它只生成有效的，从而减少额外的分支。编码愉快！

Answer 5

这是一个简单的递归解决方案：

example = ['a', 'b', 'c', 'd', 'e', 'f']

def generate(tail, head=[]):
    for i in range(1, len(tail)):
        current = tail[:]
        current[i-1:i+1] = [current[i-1] + current[i]]
        yield head + current
        yield from generate(current[i:], head + current[:i])

for item in generate(example):
    print(item)

输出：

['ab', 'c', 'd', 'e', 'f']
['ab', 'cd', 'e', 'f']
['ab', 'cd', 'ef']
['ab', 'c', 'de', 'f']
['ab', 'c', 'd', 'ef']
['a', 'bc', 'd', 'e', 'f']
['a', 'bc', 'de', 'f']
['a', 'bc', 'd', 'ef']
['a', 'b', 'cd', 'e', 'f']
['a', 'b', 'cd', 'ef']
['a', 'b', 'c', 'de', 'f']
['a', 'b', 'c', 'd', 'ef']

如何获得一个列表的所有组合，其中两个相邻的元素可以成为一个元素

How to get all combinations of a list where two elements next to each other can become one element

python

combinations

list