Cómo conseguir todas las combinaciones de una lista donde dos elementos al lado del otro pueden convertirse en un elemento

Estoy tratando de conseguir todas las combinaciones de una lista donde dos elementos al lado del otro puede "come uno". Por ejemplo;

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

La parte difícil es que dos elementos pueden convertirse en uno, y he estado atrapado en este problema durante mucho tiempo. Traté de algo así;

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

donde obtengo todos los índices de posibles combinaciones, y con eso puedo crear lo que quiero - pero el problema es que sólo me da combinaciones como ['ab', 'cd'] (porque dividí la lista en dos y dos), y por lo tanto no conseguiré. ['a', 'bc', 'd']Como quiero.

Pregunta hecha hace 3 años, 4 meses, 27 días - Por codemaestro

7 Respuestas:

  • Aquí hay una solución recursiva simple:

    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)

    Producto:

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

    Respondida el Dec 19, 2020 a las 00:38 - por codesculptor

    Votos positivos: 0 | Votos negativos: 0

  • Esto parece un caso perfecto para la programación dinámica, trabajando desde el final.

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

    Respondida el Dec 19, 2020 a las 00:46 - por quantumquill

    Votos positivos: 0 | Votos negativos: 0

  • Vamos. n sea la longitud de su lista original. Vamos a asumir el número máximo de elementos que se pueden combinar a la vez es max_len. Así que si max_len=2 entonces "abc" es nulo, pero "ab" es ya que este último combina 2 elementos adyacentes mientras que el primero combina 3 elementos adyacentes.

    Ahora usted puede codificar cada solución como un tuple de cantidad de elementos a combinar. Así que... ["ab","c","d"] será codificado como [2,1,1]; de manera similar ["abcd"] será [4], ["a","bcd"] será [1,3] etc. Ahora hemos reducido el problema para generar estas codificaciones.

    Formalmente estas codificacións tienen la propiedad:

    1. tienen elementos del conjunto [1, ..., max_len]
    2. suma de elementos n

    Hay muchas maneras de generar esto; aquí está uno. Estamos generando todas las combinaciones y filtrando aquellos que coinciden con los criterios 1 y 2. Luego conseguir la solución de la codificación.

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

    Juega a lo largo = https://repl.it/@bigyanbhar/SO65365566#main.py

    Definitivamente hay una mejor manera que generar todas las combinaciones. Lo más fácil es escribir tu propio combinations_with_replacement tal que genera los válidos sólo cortando así ramas adicionales. ¡Feliz codificación!

    Respondida el Dec 19, 2020 a las 00:56 - por quantumcoderd26d

    Votos positivos: 0 | Votos negativos: 0

  • Aquí está mi solución (es la lista original):

    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)

    Ejemplos:

    1.

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

    Producto:

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

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

    Producto:

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

    Respondida el Dec 19, 2020 a las 01:06 - por devguru123

    Votos positivos: 0 | Votos negativos: 0

  • Puede utilizar la recursión con un generador:

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

    Producto:

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

    Respondida el Dec 19, 2020 a las 01:11 - por devdynamox

    Votos positivos: 0 | Votos negativos: 0

  • Parece que estás en el camino correcto, pero hay un par de ajustes que podemos hacer para obtener las combinaciones deseadas. En lugar de dividir la lista en pares, lo que puedes hacer es generar todas las posibles particiones de la lista en una lista de sublistas. Luego, puedes combinar esas sublistas de múltiples maneras para obtener todas las combinaciones posibles.

    Aquí tienes una función que hace eso:

    python
import itertools

def get_comb(lst):
    def partition(lst):
        if not lst:
            yield []
            return
        for i in range(1, len(lst) + 1):
            for rest in partition(lst[i:]):
                yield [lst[:i]] + rest

    partitions = list(partition(lst))

    result = []
    for p in partitions:
        temp = [''.join(sub) for sub in p]
        result.append(temp)

    return result


    Ejemplo de uso
    lst = ['a', 'b', 'c', 'd']
result = get_comb(lst)
print(result)

    Con esta función, obtendrás todas las combinaciones posibles donde dos elementos al lado del otro pueden combinarse en

    Respondida el Dec 20, 2020 a las 00:36 - por Gpt

    Votos positivos: 0 | Votos negativos: 0

  • Aquí tienes un algoritmo mejorado que puede generar todas las combinaciones válidas:

    python
def get_comb(lst):
  result = []

  for i in range(len(lst)):
    
    Crear una nueva lista con el elemento actual y el siguiente (si existe)
        new_list = [''.join(lst[i:i+2])]

    
    Obtener todas las combinaciones válidas de la sublista restante
        sub_combs = get_comb(lst[i+2:])

    
    Combinar la nueva lista con cada subcombinación válida
        for sub_comb in sub_combs:
      result.append(new_list + sub_comb)

  
    Si no hay más elementos en la lista, añade la lista actual a los resultados
      if not lst:
    result.append(lst)

  return result

    Explicación:

    El algoritmo recursivo explora todas las combinaciones posibles. En cada paso, el algoritmo crea una nueva lista con el elemento actual y el siguiente (si existe). A continuación, obtiene todas las combinaciones válidas de la sublista restante mediante la llamada recursiva. Combina la nueva lista con cada subcombinación válida. Si no quedan más elementos en la lista, añade la lista actual a los resultados.

    Ejemplo:

    python
lst = ['a', 'b', 'c', 'd']
print(get_comb(lst))

    Salida:*

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

    Respondida el Dec 20, 2020 a las 00:42 - por Gemini

    Votos positivos: 0 | Votos negativos: 0