-1
\$\begingroup\$

An assignment at school required me to print all permutations of a string in lexicographic or dictionary order.

Here is my solution to the task -

from math import factorial

def print_permutations_lexicographic_order(s):

    seq = list(s)
    for _ in range(factorial(len(seq))):
        print(''.join(seq))
        nxt = get_next_permutation(seq)
        # if seq is the highest permutation
        if nxt is None:
            # then reverse it
            seq.reverse()
        else:
            seq = nxt

def get_next_permutation(seq):
    """
    Return next greater lexicographic permutation. Return None if cannot.

    This will return the next greater permutation of seq in lexicographic order. If seq is the highest permutation then this will return None.

    seq is a list.
    """
    if len(seq) == 0:
        return None

    nxt = get_next_permutation(seq[1:])

    # if seq[1:] is the highest permutation
    if nxt is None:
        # reverse seq[1:], so that seq[1:] now is in ascending order
        seq[1:] = reversed(seq[1:])

        # find q such that seq[q] is the smallest element in seq[1:] such that
        # seq[q] > seq[0]
        q = 1
        while q < len(seq) and seq[0] > seq[q]:
            q += 1

        # if cannot find q, then seq is the highest permutation
        if q == len(seq):
            return None

        # swap seq[0] and seq[q]
        seq[0], seq[q] = seq[q], seq[0]

        return seq
    else:
        return [seq[0]] + nxt


s = input('Enter the string: ')
print_permutations_lexicographic_order(s))

Here are some example inputs/outputs:

Enter the string: cow
>>> cow
    cwo
    ocw
    owc
    wco
    woc

Enter the string: dogs
>>> dogs
    dosg
    dsgo
    dsog
    gdos
    gdso
    gods
    gosd
    gsdo
    gsod
    odgs
    odsg
    ogds
    ogsd
    osdg
    osgd
    sdgo
    sdog
    sgdo
    sgod
    sodg
    sogd
    ogds
    ogsd

So, I would like to know whether I could make my program shorter and more efficient.

Any help would be highly appreciated.

\$\endgroup\$
  • \$\begingroup\$ Why the downvote :( Is anything wrong with the question? \$\endgroup\$ – Justin May 27 at 16:16
  • \$\begingroup\$ I didn't downvote, but I notice that the 2nd example is wrong. "dgos" and "dgso" are missing while "ogds" and "ogsd" occur twice. Also the tag "dictionary" refers to the data structure, not dictionary order. \$\endgroup\$ – Sedsarq May 27 at 16:25
  • \$\begingroup\$ I've edited the tags, performance doesn't look like an aim, since your code doesn't look to care too much about it. \$\endgroup\$ – Peilonrayz May 27 at 16:28
  • \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. The moment answers arrive, you stop touching the code. That's the rules. It gets awfully messy otherwise. \$\endgroup\$ – Mast May 27 at 18:03
5
\$\begingroup\$

And in the third time I will recommend you the itertools module:

As I told in another answers, your code is very C/C++ styled, it is not Pythonic. Try to avoid manual iteration with indices as much as possible. Python has an enormous standard library that contains many useful modules. I already recommended you an itertools module. It contains pair of dozens generic functions to work with iterators. One of them - permutations - do 90% of your work:

And in the second time I will recommend you the itertools.permutations function that can solve your problem with literally one line of code:

from itertools import permutations

def get_lexicographic_permutations(s):
    return sorted(''.join(chars) for chars in permutations(s))

print(get_lexicographic_permutations('dogs'))

['dgos', 'dgso', 'dogs', 'dosg', 'dsgo', 'dsog', 'gdos', 'gdso', 'gods', 'gosd', 'gsdo', 'gsod', 'odgs', 'odsg', 'ogds', 'ogsd', 'osdg', 'osgd', 'sdgo', 'sdog', 'sgdo', 'sgod', 'sodg', 'sogd']

\$\endgroup\$
  • 2
    \$\begingroup\$ Title says he's supposed to use recursion though. \$\endgroup\$ – Sedsarq May 27 at 16:01
  • 1
    \$\begingroup\$ @Sedsarq The question isn't tagged with reinventing-the-wheel, and doesn't state they have to use recursion. It is also tagged performance, and this is almost definitely more performant. \$\endgroup\$ – Peilonrayz May 27 at 16:14
  • \$\begingroup\$ @Peilonrayz That's a fair point. I read the title to mean that the program should involve recursion, but it could just as well mean simply that his version does. \$\endgroup\$ – Sedsarq May 27 at 16:17
2
\$\begingroup\$

A basic recursive idea is to repeatedly reduce the problem to a simpler version of the same kind, until it reaches a base case which can no longer be reduced. Recursive solutions are often "simple" in the sense of not using many lines of code, so that's something to look for.

Let's see how this can be applied to this particular problem. Take the word "cow", with the permutations

cow, cwo, ocw, owc, wco, woc

Notice how the first character stays the same, until all permutations of the "tail" has been covered. That's the reduction step you need: For each character in the string, make that the first character, and then call the function again with the rest of the characters. Keep track of the character selection order as that will be the word. Then remember to catch the base case: If there's no characters left in the string, we're done removing characters and the word is complete.

def lexperm(s, word=''):
    if not s:
        print(word)
    for i, char in enumerate(s):
        lexperm(s[:i] + s[i+1:], word + char)

Notice how this doesn't require swapping or reversing anything, because we're removing all characters, in every order.

\$\endgroup\$
2
\$\begingroup\$

I've read over a couple of your past questions, and I can't really describe how unsightly the code is without violating SE's rules.

Read and follow PEP8.

Skip over the section "A Foolish Consistency is the Hobgoblin of Little Minds" as you don't seem to know what good code looks like and you arn't interacting with legacy code. It's better to be a Hobgoblin for now, as you'll produce better code than you are now.


Get a couple of linter wrappers, like Flake8, Prospector or Coala. Make sure to turn all warnings on, as they don't normally by default.

These will help you know what parts of your code sucks without having to ask others!

Fixing all the errors these tools raise helps keep your code clean and make it so when you produce larger programs it's easier to understand what your code is doing. You may protest and say, "but people on Code Review understand my code!" And you would be right, but that is because you're developing solutions to coding challenges, not real life problems that are more intricate and require larger amounts of code.

\$\endgroup\$
  • \$\begingroup\$ I understand. I will keep this in mind. Thank you :) \$\endgroup\$ – Justin May 27 at 16:59
1
\$\begingroup\$

I would recommend looking at itertools.permutations

from itertools import permutations
for p in permutations("cow"):
    joined = "".join(p)
    print(joined)

Output:

cow
cwo
ocw
owc
wco
woc

You can use it multiple ways:

  1. Test your algorithm regarding output
  2. Compare to your algorithm regarding speed
  3. Check the implementation to get an idea how to it is done

Regarding 3, there is even an equivalent version (optimized but still readable) in the docs.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.