HackerRank itertools.combinations()

Question

I was solving the following problem on HackerRank.

Here's my solution -

from itertools import combinations
a = input()
ls = list(map(str, a.split()))
for i in range(1, int(ls[1])+1):
 ls2 = []
 ls2 = list(map("".join, combinations(ls[0], i)))
 for elem in ls2:
 ls2[ls2.index(elem)] = "".join(sorted(elem))
 ls2.sort()
 for char in ls2:
 print(char)

But I feel it's not very efficient as it uses 2 Lists and 2 nested loops.

Any suggestions as to how can I improve the code?

• Juho: In my experience, you should always avoid explicit loops when looking for performance. So that's never a bad first step.

Answer 1

Nice solution, these are my suggestions:

• Parsing the input: in Python 3 the function input always returns a string, so the mapping can be removed. In Python 2, you can use raw_input.
• Naming: ls is too generic. In this case, a suggestion is to take the names from the problem description. From:

  a = input()
  ls = list(map(str, a.split()))
  

  To:

  S, k = input().split()
  

• Sort in advance: the problem requires to output the combinations in lexicographic sorted order. The doc says:

The combination tuples are emitted in lexicographic ordering according to the order of the input iterable. So, if the input iterable is sorted, the combination tuples will be produced in sorted order.

So, instead of sorting each combination, it's enough sorting the input S at the beginning and all the combinations will be automatically sorted.

• Use the output of itertools.combinations: the output of itertools.combinations is an iterable or tuples, which can be used in a for-loop to print the combinations one by one. The only change is to convert the tuple to a string, and can be done with string.join.

Revised code

from itertools import combinations
S, k = input().split()
S_sorted = ''.join(sorted(S))
for i in range(1, int(k)+1):
 for c in combinations(S_sorted, i):
 print(''.join(c))