3

The following was a job interview question which I struggled with. (Unnecessary switching between list and set, tested it and realised it was missing an expected output, too many steps). If possible, looking for the proper answer or maybe a guide on how I should have tackled the problem. Thank you.

Question: Give a String, find all possible combinations from it (Front and Reverse). Print all combinations and total count of combinations. Order doesn't matter.

Example s = 'polo'

Front Answer = 'p', 'po', 'pol', 'polo', 'ol', 'olo', 'lo', 'o', 'l'.
Reverse Answer: 'o', 'ol', 'olo', 'olop', 'lop', 'op', 'p', 'l'.

My answer:

count = 0
count2 = -1
length = len(s)
my_list = []
for i in s:
    temp = s[count:]
    temp2 = s[:count2]
    my_list.append(i)
    my_list.append(temp)
    my_list.append(temp2)
    count += 1
    count2 -= 1

my_set = set(my_list) 
for f in my_set:
    print(f)
print(len(my_set)) # Answer for front

new_list = []
for f in my_set:
    new_list.append(f[::-1])

print('Reverse Result:')
for f in new_list:
    print(f)
print(len(new_list)) # Answer for reverse
Community
  • 1
  • 1
kang
  • 707
  • 4
  • 17
  • 1
    Possible duplicate of [Finding all possible permutations of a given string in python](https://stackoverflow.com/questions/8306654/finding-all-possible-permutations-of-a-given-string-in-python) – Abhishek Singh Oct 08 '17 at 12:38

2 Answers2

2

You can do this with two nested for-loops. One will loop through the start indexes and the nested one loops through the end indexes (starting from the start + 1 going to the length of s +1 to reach the very end).

With these two indexes (start and end), we can use string slicing to append that combination to the list forward. This gives you all the combinations as you see below.

To get the reversed ones, you could do a for-loop as you have done reversing the order of the forward ones, but to save the space, in the code below, we just append the same index but sliced from the reversed s (olop).

s = "polo"

forward = []
backward = []
for start in range(len(s)):
    for end in range(start+1, len(s)+1):
        forward.append(s[start:end])
        backward.append(s[::-1][start:end])

print(forward)
print(backward)
print(len(forward) + len(backward))

which outputs:

['p', 'po', 'pol', 'polo', 'o', 'ol', 'olo', 'l', 'lo', 'o']
['o', 'ol', 'olo', 'olop', 'l', 'lo', 'lop', 'o', 'op', 'p']
20

If you really wanted to make the code clean and short, you could do the same thing in a list-comprehension. The logic remains the same, but we just compress it down to 1 line:

s = "polo"

forward = [s[start:end] for start in range(len(s)) for end in range(start+1, len(s)+1)]    
backward = [c[::-1] for c in forward]

print(forward)
print(backward)
print(len(forward) + len(backward))

which gives the same output as before.

Hope this helps!

Joe Iddon
  • 20,101
  • 7
  • 33
  • 54
0

Try this:

   string = "polo"
   x = [string[i:j] for i in range(len(string)) for j in range(len(string),0,-1) if j > i ]
   x.sort()
   print("Forward:",x[::-1])
   print("Reverse:",x[::])
Js doe
  • 26
  • 4