CODEWITHSUNDEEP
pythonpython-2.7
rbaleksandar
rbaleksandar

Reputation: 9691

How to generate all combinations of a set of characters without repetitions?

I have the following list:

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

I'm looking into a way to generate all possible strings that contain these characters with the following restrictions:

I can use 

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

to generate all strings that contain a, b and c. However I have to also do

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

As you can probably tell if the initial list of available characters is long I need to do a lot of work. So I'm looking for an elegant way in Python to generate all of the above with just the list of allowed characters as input:

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

I need this since I want to provide a parameter for a POST request for my web server, where a parameter (let's call it val) can take different unique values (either single characters or a combination of those) in order to trigger some data generation. The list of available values will grow over time so I'd like to make it easier to process the request by automating the check if the given values for val is a valid one.

I've been also thinking of iterating through each element of the list of allowed characters and concatenating it the rest ('a', 'ab', 'ac', 'abc', 'b', 'ba', 'bc' etc.) but I have no idea how to do that.

Upvotes: 5

Views: 5313

Answers (3)

Işık Kaplan
Işık Kaplan

Reputation: 2982

There are correct answers already been posted but I wanted to give it a shot, made it as readable as I can.

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

Upvotes: 3

Ajax1234
Ajax1234

Reputation: 71451

You can use recursion with a generator expression:

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

Output:

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

Upvotes: 1

Jean-François Fabre
Jean-François Fabre

Reputation: 140168

I would chain different permutations of the string characters with a length constraint:

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

result:

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

Edit: seems that I produced a variant of the powerset recipe (what's a good way to combinate through a set?), not considering the empty string, considering order of the characters (abc and cba are 2 different items) and using str.join to generate strings directly.

Upvotes: 2

Related Questions