1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
#!/usr/bin/python3
# https://theweeklychallenge.org/blog/perl-weekly-challenge-260/#TASK2
#
# Task 2: Dictionary Rank
# =======================
#
# You are given a word, $word.
#
# Write a script to compute the dictionary rank of the given word.
#
## Example 1
##
## Input: $word = 'CAT'
## Output: 3
##
## All possible combinations of the letters:
## CAT, CTA, ATC, TCA, ACT, TAC
##
## Arrange them in alphabetical order:
## ACT, ATC, CAT, CTA, TAC, TCA
##
## CAT is the 3rd in the list.
## Therefore the dictionary rank of CAT is 3.
#
## Example 2
##
## Input: $word = 'GOOGLE'
## Output: 88
#
## Example 3
##
## Input: $word = 'SECRET'
## Output: 255
#
############################################################
##
## discussion
##
############################################################
#
# We first create all possible permutations, for which we use an
# iterator-based solution from Algorithm::Permute. Then we keep
# all permutations, removing duplicates (Algorithm::Permute will
# for example generate the word "GOOGLE" twice, once for each "O"
# in the first and the second of two possible positions). Then we
# just walk the sorted list, counting the index while walking, and
# returning 1+index once we found the original word.
import itertools
def dictionary_rank (word: str) -> None:
chars = list(word)
print(f"Input: {word}")
permutations = list(itertools.permutations(chars))
unique_permutations: list = []
seen: dict = {}
for perm in permutations:
w = "".join(perm)
if w not in seen:
unique_permutations.append(w)
seen[w] = 1
sorted_array = sorted(unique_permutations)
i=0
while i < len(sorted_array):
if sorted_array[i] == word:
i += 1
print(f"Output: {i}")
return
i += 1
dictionary_rank('CAT');
dictionary_rank('GOOGLE');
dictionary_rank('SECRET');
|
