CODEWITHSUNDEEP
pythonpermutation
Anshu Dwibhashi
Anshu Dwibhashi

Reputation: 4675

Python permutations including substrings

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?

Upvotes: 5

Views: 2400

Answers (2)

Fugiman
Fugiman

Reputation: 11

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

Upvotes: 1

Amber
Amber

Reputation: 526573

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

Upvotes: 5

Related Questions