-2

I am struggling with the following, is my code correct and how to test if it works?

Task: Take a string as a single input argument. You may assume the string consists of distinct lower case letters (in alphabetical order). You may assume the input is a string of letters in alphabetical order.

Return a list of strings where each string represents a permutation of the input string. The list of permutations must be in lexicographic order. (This is basically the ordering that dictionaries use. Order by the first letter (alphabetically), if tie then use the second letter, etc.

  • If the string contains a single character return a list containing that string
  • Loop through all character positions of the string containing the characters to be permuted, for each character:
  • Form a simpler string by removing the character
  • Generate all permutations of the simpler string recursively
  • Add the removed character to the front of each permutation of the simpler word, and add the resulting permutation to a list
  • Return all these newly constructed permutations

[My code]

def perm_gen_lex(in_string):

    if (len(in_string) <= 1):
        return(in_string)

    # List of all new combinations
    empty_list = []

    # All permutations
    final_perm = perm_gen_lex(in_string[1:])

    # Character to be removed
    remove_char = in_string(0)

    # Remaining part of string
    remaining_string = in_string[1:]

    for perm in final_perm[1:]:
        for i in range(len(in_string) + 1):
            return empty_list.append(perm[:i] + remove_char + perm[i:])

    return empty_list
smci
  • 32,567
  • 20
  • 113
  • 146
Mihai G
  • 27
  • 2
  • 5
  • I'd strongly recommend taking a look at [`itertools.permutations`](https://docs.python.org/3/library/itertools.html#itertools.permutations). One, in real world code, it's what you would use, but two, the documentation for it actually includes the Python code that performs the same task, which might be a useful starting point. About the only difference from your code would be that you'd replace the `yield`s with `append`s to your result `list` (because I'm guessing you haven't covered generator functions yet). – ShadowRanger Sep 27 '17 at 00:10
  • Take a look at this. Provides good understanding on how to write such an algorithm. https://stackoverflow.com/questions/1622532/algorithm-to-find-next-greater-permutation-of-a-given-string – thebenman Sep 27 '17 at 00:36
  • Possible duplicate of [Algorithm to find next greater permutation of a given string](https://stackoverflow.com/questions/1622532/algorithm-to-find-next-greater-permutation-of-a-given-string) – thebenman Sep 27 '17 at 00:36
  • I tried to fix you indentation, please check it. But yeah this is a duplicate. – smci May 04 '18 at 04:28

1 Answers1

-2

Some variation on this will get you moving:

from itertools import product

def combinations(string):
    return [''.join(i) for i in product(string, repeat = len(string))]

print(combinations("abc"))

See https://docs.python.org/3/library/itertools.html#itertools.product

Dan
  • 1,209
  • 3
  • 13
  • 29
  • 1
    You just wrapped `itertools.product` and named it `combinations` (which it isn't). Actual combinations (order-insensitive) don't help with generating permutations (order-sensitive), and products of a repeated input produce many non-permutation outputs (because they contain an item from the string multiple times, while omitting others). And even if this worked, the OP asked for tips; code without explanation is the opposite of what they need. – ShadowRanger Sep 27 '17 at 00:31
  • Thank you kindly for your constructive feedback ShadowRinger. Please accept my most humble apologies for the sub par offer of direction. – Dan Sep 27 '17 at 00:38
  • I am so lost with what you said, I really have tried understanding this. But I am such a beginner that I cant even follow what your doing. Im still trying to figure out how to make a unittest – Mihai G Sep 27 '17 at 05:29
  • im confused about this line, What does it do ?... return [''.join(i) for i in product(string, repeat = len(string))] – Mihai G Sep 27 '17 at 06:03
  • The line is wrapped in [ and ] which means its a list comprehension statement. See here for a good explanation of what that is if you aren't familiar with list comprehension: http://treyhunner.com/2015/12/python-list-comprehensions-now-in-color/. Its a very useful Python concept for writing concise and efficient code and removing for loops. – Dan Sep 27 '17 at 12:43
  • The statement product(string, repeat=len(string)] is an itertools function that builds different Cartesian products of the input value. But as ShadowRinger points out - there are more suitable itertools functions for your problem. Itertools is a library that offer some very useful functions for iterating over objects efficiently. There is a quite well explained article on the basic iteritems functions here https://pymotw.com/2/itertools/. The function you likely want is itertools.permutations. – Dan Sep 27 '17 at 12:43