Back to Problem Solutions forum
This one has me stumped.
Here's the relevant function that I use to produce the string at a given index in the list of all permutations:
def index_to_lexstring(symbols, length, index):
from math import factorial as fact
from math import floor
"""
Finds the string at <index> from a list of the lexicographically sorted
permutations of <symbols> set of length <length>.
INPUT: <index>, an integer; <symbols>, an iterable containing all symbols used.
OUTPUT: the nth lexicographic ordered string
"""
output = []
symbols = [str(item) for item in symbols]
n = 0
p = len(symbols)
q = length
i = index
#Calculate each symbol for the output list iteratively
while (n < q):
#Calculate the size of the complete permutations list.
#Save as the denominator
denominator = nCr(p-n-1, q-n-1) * fact(q-n-1)
#Select the next symbol, add to output, remove from symbols
output.append( symbols.pop( floor(i / denominator) ) )
#Update iterative values
i -= (denominator * floor(i / denominator))
n += 1
#Return a joined string of symbols in outlist
return("".join(output))
On the first two test cases (5 3 2
and 30 15 0
), it works fine. But on the third sample test case (36 16 7307872109
), it fails, producing the output 012345679QBFPZYX
instead of KLMNOPQRSTUVWXYZ
.
Any ideas why?
Hi!
What does your code give for such testcase:
5
5 3 0
5 3 1
5 3 2
5 3 3
5 3 4
I suspect there could be something wrong for 5 3 3
and probably this may be due to algorithm is solving some
different task... For combinations 012
and 021
is regarded the same.
Okay, I think I'm onto something. My output to your sample set is 012 021 102 120 201
. But as you've noted, I seem to be calculating partial permutations instead of partial combinations.
I just spent a week skiing with friends, no programming. So I think I'm ready to reattack this problem now! Wish me luck.
> I just spent a week skiing with friends,
Ha-ha, I feel envious to you and Sergey - we have almost no chance to ski here in St-Petes' this winter - right now there is mostly dirty ice covered with 3 inch pools of water - temperature keeps steady around the freezing point :)
Got it, finally!
For future reference of those following this... I was previously solving the factoradic problem. I needed to solve the combinadic problem. But half the fun was digging deep to find ideas, so I won't spoil it too much. ;)
That problem gave me quite a bit of trouble as well. Congratulations on solving it. If you like, you can check out my solution to the same problem. It's always nice to compare different ways of solving the same problem :)
Problem 129: Enumerating Combinations
Code on,
Christopher P. Matthews