0

Problem: If we have a set of letter: {A,D,E,I,K,M,O,T}. Problem is to find which permutation is "METODIKA". alphabetically (lexicographic order)

Solution is to see that if we write first letter A we then write 7! combinations. After A we write D again 7! combinations... When we can to letter M we write $5\cdot$ 7! combinations. That's idea for the fist letter and we keep going until last letter.
Solution is 27346.
My question is: if we know that we can have 8!(40 320) combinations, is there a way to count permutations not from begin but form the end to begin. Because 27346 is bigger than 40320/2 and we will must count smaller number of combinations?

josf
  • 1,317
  • 1
    How do you enumerate permutations? I assume alphabetically (lexicographic order)? - Then see Finding the n-th lexicographic permutation of a string. – Vepir Oct 12 '19 at 14:08
  • 1
    Strictly speaking, sets do not have order, so METODIKA could be viewed the first permutation. It seems you arrange all permutations in lexical order? – Hagen von Eitzen Oct 12 '19 at 14:09
  • 1
    Why do you consider it soo much harder to count that M has five letters before it than to count that it has two letters after it? Nevertheless, you can find the position in reverse lexical order (i.e., starting from ${T,O,M,K,I,E,D,A}$ and subtract from $8!$ and hope you do not introduce an off-by-one error. – Hagen von Eitzen Oct 12 '19 at 14:11
  • 4
    From end, that is from TOMKIEDA and go backward? Yes, it's possible. Count how many letters before reaching the end, with basically the same method. But both methods are equally fast: you don't count each permutation, but you increment the index wisely (for instance, if the first letter is M, you know there are $5$ blocks of $7!$ permutations before, no need to go through them all). – Jean-Claude Arbaut Oct 12 '19 at 14:39

0 Answers0