# string permutation in lexicographically order with repetition of characters in the string def permute(input): count_map = {} for ch in input: if ch in count_map.keys(): count_map[ch] = count_map[ch] + 1 else: count_map[ch] = 1 keys = sorted(count_map) str = [] count = [] for key in keys: str.append(key) count.append(count_map[key]) result = [0 for x in range(len(input))] permute_util(str, count, result, 0) def permute_util(str, count, result, level): if level == len(result): print(result) return for i in range(len(str)): if count[i] == 0: continue; result[level] = str[i] count[i] -= 1 permute_util(str, count, result, level + 1) count[i] += 1 if __name__ == '__main__': input = ['B', 'C', 'A', 'A'] permute(input)