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

user_12021677 0
Viewed 261

I'm trying to get all combinations of a list where two elements next to each other may "become one". For example;

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

The tricky part is that two elements can become one, and I've been stuck on this problem for a long time. I tried something like this;

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)]

where I get all the indexes of possible combinations, and with that I can get create what I want - but the problem is that it only gives me combinations like ['ab', 'cd'] (because I split the list into two and two), and I therefore won't get i.e. ['a', 'bc', 'd'], as I want.

combinations list python
5 Answers

This looks like a perfect case for dynamic programming, working from the end.

[] -> []
['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.
user_64574070

Let n be the length of your original list. We will assume the maximum number of elements that can be combined at a time is max_len. So if max_len=2 then "abc" is invalid, but "ab" is since the latter combines 2 adjacent elements while the former combines 3 adjacent elements.

Now you can encode each solution as a tuple of number of elements to be combined. So ["ab","c","d"] will be encoded as [2,1,1]; similarly ["abcd"] will be [4], ["a","bcd"] will be [1,3] etc. Now we have reduced the problem to generating these encodings.

Formally these encodings have the property:

  1. have elements from the set [1, ..., max_len]
  2. sum of elements is n

There are many ways of generating this; here is one. We are generating all combinations and filtering those which match criterion 1 and 2. Then getting the solution from the encoding.

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])

Play along = https://repl.it/@bigyanbhar/SO65365566#main.py

There is definitely a better way than generating all combinations. The easiest is to write your own combinations_with_replacement such that it generates valid ones only thereby cutting down extra branches. Happy coding!

user_4387580

Here's a simple recursive solution:

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)

Output:

['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']
user_9844210

Here is my solution (l is the original list):

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)

Examples:

1.

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

Output:

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

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

Output:

[('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')]
user_82285580

You can use recursion with a generator:

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)))))

Output:

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