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

Question

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:

a character may not occur multiple times (aab, aba, abca etc. is invalid)
a character may be excluded (ab is valid even if c is not present; a is also valid even if b and c are not present)

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.

Did you take a look to [itertools.combinations](https://docs.python.org/2/library/itertools.html#itertools.combinations) ? — Pierluigi, Mar 01 '18 at 15:42
@Pierluigi I didn't know about it. It seems though that I have to give the length, which should probably be the `len()` of the list of allowed characters, right? — rbaleksandar, Mar 01 '18 at 16:31

Işık Kaplan · Accepted Answer · 2018-03-01T16:17:10.683

3

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

edited Mar 01 '18 at 16:17

answered Mar 01 '18 at 15:56

Işık Kaplan

2,815
2
13
28

I upvoted all since all are working but this is the most readable and easier to understand. – rbaleksandar Mar 02 '18 at 08:13
1

`while len(i)>0: this.append(i.pop())` is slow compared to `this += i` – Jean-François Fabre Mar 02 '18 at 08:31

score 2 · Answer 2 · answered Mar 01 '18 at 15:43

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.

score 1 · Answer 3 · answered Mar 01 '18 at 15:44

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

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

3 Answers3