Algorithm: Printing the correct index for the character sequence
algorithm, combinations, combinatorics
Solution
Let me give you a few hints:
- Can you find a formula for the number of such words of a given length `k` ?
- Now fix a length `k`, and a letter `l`. How many word of length `k` starting with `l` are they ?
Hint: Pascal triangle. If you need some more hint, http://en.wikipedia.org/wiki/Combinadic can help. If you need some implementation, you can get inspiration from the rank function defined in (Python language) https://github.com/sagemath/sagelib/blob/master/sage/combinat/choose_nk.py
Problem
I came across the following problem while preparing for an exam: Imagine an alphabet of words. Example: ``` a ==> 1 b ==> 2 c ==> 3 ... z ==> 26 ab ==> 27 ac ==> 28 ... az ==> 51 bc ==> 52 and so on. ``` The sequence of characters needs to be in ascending order only (i.e. 'ab' is valid but 'ba' is not). Question: Given any word, print its index if valid and 0 if not. ``` Input Output ab 27 ba 0 aez 441 ``` Any pointers on how to solve this would be appreciated.