5

I've come across this post: How to generate all permutations of a list in Python

But I require something more, namely all of the permutations of a string as well as all the permutations of all the substrings. I know it's a big number, but is it possible?

Community
  • 1
  • 1
Anshu Dwibhashi
  • 4,617
  • 3
  • 28
  • 59
  • 1
    Possible duplicate: http://stackoverflow.com/questions/12273688/algorithm-to-generate-permutations-of-a-list-of-strings-and-their-substrings – bdean20 Aug 25 '13 at 14:36

2 Answers2

5
import itertools

def all_permutations_substrings(a_str):
    return (
        ''.join(item)
        for length in xrange(1, len(a_str)+1)
        for item in itertools.permutations(a_str, length))

Note, however, that this is true permutations - as in, hello will have any substring permutation that has two ls in it twice, since the l's will be considered "unique". If you wanted to get rid of that, you could pass it through a set():

all_permutations_no_dupes = set(all_permutations_substrings(a_str))
Amber
  • 507,862
  • 82
  • 626
  • 550
  • You can iterate over them (e.g. `for result in all_permutations_substrings(...)`) or you can pass it to `list()` if you just want a list. – Amber Aug 25 '13 at 14:53
  • @AnshumanDwibhashi, you could do this: `result = [''.join(ele) for ele in set(all_permutations_substrings('hello'))]` – Akavall Aug 25 '13 at 14:59
1

As the question you linked states, itertools.permutations is the solution for generating permutations of lists. In python, strings can be treated as lists, so itertools.permutations("text") will work just fine. For substrings, you can pass a length into itertools.permutations as an optional second argument.

def permutate_all_substrings(text):
  permutations = []
  # All possible substring lengths
  for length in range(1, len(text)+1):
    # All permutations of a given length
    for permutation in itertools.permutations(text, length):
      # itertools.permutations returns a tuple, so join it back into a string
      permutations.append("".join(permutation))
  return permutations

Or if you prefer one-line list comprehensions

list(itertools.chain.from_iterable([["".join(p) for p in itertools.permutations(text, l)] for l in range(1, len(text)+1)]))
Fugiman
  • 11
  • 3