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, 5 meses, 4 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 esmax_len
. Así que simax_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:
- tienen elementos del conjunto
[1, ..., max_len]
- 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 - tienen elementos del conjunto
-
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 resultExplicació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