Tengo la siguiente lista:

['a', 'b', 'c']

Estoy buscando una forma de generar todas las cadenas posibles que contienen estos caracteres con las siguientes restricciones:

  • un personaje no puede aparecer varias veces (aab, aba, abca etc. no es válido)
  • puede excluirse un carácter (ab es válido incluso si c no está presente; a también es válido incluso si b y c no están presentes)

Puedo usar

[''.join(p) for p in permutations('abc')]

Para generar todas las cadenas que contienen a, b y c. Sin embargo tengo que hacer también

[''.join(p) for p in permutations('ab')]
[''.join(p) for p in permutations('ac')]
[''.join(p) for p in permutations('bc')]

Como probablemente pueda decir si la lista inicial de caracteres disponibles es larga, necesito hacer mucho trabajo. Así que estoy buscando una manera elegante en Python para generar todo lo anterior con solo la lista de caracteres permitidos como entrada:

def generate(vals=['a', 'b', 'c']):
  # The initial list of allowed characters also has to be part of the 
  # final list since these also represent valid values
  res = vals
  # Generate all possible strings and store in res

  return res

Necesito esto ya que quiero proporcionar un parámetro para una solicitud POST para mi servidor web, donde un parámetro (llamémoslo val) puede tomar diferentes valores únicos (caracteres individuales o una combinación de ellos) para desencadenar cierta generación de datos. La lista de valores disponibles crecerá con el tiempo, por lo que me gustaría facilitar el procesamiento de la solicitud al automatizar la verificación si los valores dados para val son válidos.

También he estado pensando en recorrer cada elemento de la lista de caracteres permitidos y concatenarlo con el resto ('a', 'ab', 'ac', 'abc', 'b', 'ba', 'bc' etc.) pero no tengo idea de cómo hacerlo.

5
rbaleksandar 1 mar. 2018 a las 18:35

3 respuestas

La mejor respuesta

Ya se han publicado respuestas correctas, pero quería darle una oportunidad, lo hice lo más legible posible.

from itertools import permutations as p

def gen(lst):
    y = [[a for a in p(lst,y)] for y in range(1,len(lst)+1)]

    this = []
    for i in y:
        while len(i)>0:
            this.append(i.pop())
    return [''.join(x) for x in this]

print(gen(['a','b','c']))
1
Işık Kaplan 1 mar. 2018 a las 16:17

Puede usar la recursión con una expresión generadora:

def permutation(s, current = []):
   if len(current) == len(s):
      yield current
   else:
      yield current
      for i in s:
        if current.count(i) == 0:
            for h in permutation(s, current + [i]):
               yield h

print(map(''.join, list(permutation(['a', 'b', 'c']))[1:]))

Salida:

['a', 'ab', 'abc', 'ac', 'acb', 'b', 'ba', 'bac', 'bc', 'bca', 'c', 'ca', 'cab', 'cb', 'cba']
1
Ajax1234 1 mar. 2018 a las 15:44

Encadenaría diferentes permutaciones de los caracteres de cadena con una restricción de longitud:

import itertools

def generate(vals="abc"):
    return ("".join(x) for x in itertools.chain.from_iterable(itertools.permutations(vals,i+1) for i in range(0,len(vals))))

print(list(generate("abc"))) # force iteration to print result

Resultado:

['a', 'b', 'c', 'ab', 'ac', 'ba', 'bc', 'ca', 'cb', 'abc', 'acb', 'bac', 'bca', 'cab', 'cba']

Editar: parece que produje una variante de la receta de powerset (¿Qué hay? una buena forma de combinar un conjunto?), sin considerar la cadena vacía, considerando el orden de los caracteres (abc y cba son 2 elementos diferentes) y utilizando str.join para generar cadenas directamente.

2
Jean-François Fabre 1 mar. 2018 a las 15:43