+ 6

Word Rank [Code Coach]

For those who have solved this problem, what was your approach to the problem? I’m not looking for the solution in code but rather just the thought process behind approaching and solving the problem. This so far has been the only challenge I haven’t been able to finish in Python. I’ve tried a few different approaches but they either didn’t work because I wasn’t successful in it or it was a flawed solution that only worked with single cases. First I tried to just letter swap until I generated every possible word then index it. This became a ridiculous feet when you got to large words like SOLOLEARN. Second I tried to index each letter to make it similar to binary treating something like "ABAB" as 0101 and comparing it to it’s alphabetical counterpart "AABB" as 0011. This in theory worked for two letters since subtracting them would give me 0100 aka 2. But going more complex I couldn’t wrap my head around it. Third I tried looking at what my expected output should be my examining HELLO, I wrote down each outcome in a notepad: -HELLO Sort alphabetically 1.EHLLO 2.EHLOL 3.EHOLL 4.ELHLO 5.ELHOL 6.ELLOH 7.ELLHO 8.ELOLH 9.ELLHO 10.EOLLH 11.EOLHL 12.EOHLL 13.HELLO By looking at it I thought I could do something like: for each character in the word: for the number of remaining characters: create every word from the possible remaining letters. add that new word to an array index the solution and return it. On paper it looked fine but I realized that I’m just getting rid of the first character and then running into the same problem of generating every possibility of that word. Which I haven’t been able to wrap my head around just yet. For those who might ask for my code for reference, I scrapped each attempt after they didn’t work so I don’t have any versions saved of my old attempts. Apologizes ahead of time.

27th Jan 2020, 7:31 PM
Pie - avatar
9 Answers
+ 7
To find all the permutations you can use itertools permutations.
27th Jan 2020, 8:09 PM
Lothar - avatar
+ 8
Pie I haven't solved the problem, but here would be my approach (Similar to yours): 1. Find all the permutations 2. Remove duplicates 3. Rank them 4. Find the rank However, the permutations you wrote by hand are incorrect. There are more permutations than that.
27th Jan 2020, 8:00 PM
Aymane Boukrouh
Aymane Boukrouh - avatar
21st Feb 2020, 9:37 AM
David Ashton
David Ashton - avatar
+ 6
Although it passes all the test cases (using Python), generating all permutations isn't an efficient solution. My approach is quite similar to the one shown here: https://brilliant.org/wiki/rank-of-a-word-in-dictionary/#rank-of-a-word-with-repetition-of-letters
27th Jan 2020, 11:16 PM
Diego - avatar
+ 5
In Python I was lazy with sorted permutations. ;-) For my C version I googled and implemented this: https://www.geeksforgeeks.org/lexicographic-permutations-of-string/
27th Jan 2020, 11:36 PM
HonFu - avatar
+ 1
t=0 from itertools import permutations a=input() s=list(permutations(a)) s=[''.join(permutations) for permutations in s] s.sort() dub=set() ite=[] for i in s: if i not in dub: t=t+1 ite.append(i) dub.add(i) if i==a: print(t)
28th Oct 2022, 12:30 AM
Otaku Gaming
+ 1
I promarily work with c++ and can anyone tell me how in the world am I suposed to accomplish something so complex with c++. I know that I can arrange word in the alphabetic sequence and see if a word repeated itself using nested for loops but then what nothing else makes sense what should be my next step and what new should i learn coz sololearn course of c++ is very basic and does not contain useful tutorials for c++ atleast. I know python has permutation builtin as usual with most things but I was looking for a c++ solution.
28th Dec 2022, 1:12 PM
Gaurav Kaushik
+ 1
Hello Gaurav Kaushik ...I am still learning C. But I have already solved this problem with my own in Java without any extra implementation. first..given String was splitted into char and sorted(a,b,c..). That was stored into a String.And act like as a probability tree. ***Target*** -No. of given String in probability tree -skip same words(if same char on branch,results are same.Just skip) -to stop calculating when we found the answer(to avoid the device from stunning) 😄😄 I can show my solution on paper.My algorithm. Probability tree's branch.But now I don't know how to tell you. Just solve like as a probability tree.I think you will be solved.😊😊😊 https://code.sololearn.com/cv1TCz67zWCw/?ref=app
8th Jun 2023, 6:11 PM
mg thu kha
mg thu kha - avatar
David Ashton I appreciate the code example however the second sentence of the post was about how I was *not* looking for a solution in code but rather a proper explanation. I appreciate it none the less.
24th Feb 2020, 5:52 PM
Pie - avatar