I want a fast algorithm to calculate no of permutations for n elements with some elements identical.
Using formula :
n! / k1! k2!....km!
where ki = no of i elements, i = (1,2,...m)
and k1 + k2 + ...... + km = n
Without calculating each factorial as if n is a large no like 400, 400! goes out of range of long long int( largest possible size in c++ ).
If you are posting code please use c/c++.
Thanx in advance :)
Jump to PostSo, what you essentially want is efficient calculation of multinomial coefficients. I googled that, and the first link I got was this.
Jump to PostGood link oh m4ster r0shi! The application of recursion for such tasks is one of those elegant applications of logic to overcome system limitations. I used a similar approach to generate the prime factors of very large numbers, such as Goedel encodings.
So, what you essentially want is efficient calculation of multinomial coefficients. I googled that, and the first link I got was this.
Good link oh m4ster r0shi! The application of recursion for such tasks is one of those elegant applications of logic to overcome system limitations. I used a similar approach to generate the prime factors of very large numbers, such as Goedel encodings.
The code looked like missing
include <algorithm>
I managed to get the code running in my Code::Blocks, but the example given in document: multi(7, 9, 4, 6) and given by running the code ( 564327584) has different result than my naive factorial based Python code gives (12760912164000). My Python code gives same results as the document for the three arguments examples, though. And this my result is same as online maxima version gives
Also I am quite satisfied with the speed of the naive algorithm in Python (0.047 ms for above calculation), so maybe it is worth while to just install one good multiprecission package for c++.
Yes. It seems that the author's primary concern was that the intermediate results were smaller than the final one, so, he overlooked the fact that the latter might not fit in a size_t... I had to replace three occurrences of size_t with unsigned long long to get the expected result.
Yes, I did global replace of size_t with unsigned long long and the C++ code managed the correct answer. Announced running time was 0.750 s, but I think it includes the showing of result and initialization of the C++ system, not only calculation of the multinomial function.
Okay, I calculated the binomial coefficient for n = 1600 and k = 800 using the factorial approach and a smart memoization method I found here. As you can see from the results, it turns out that the former way is more efficient in terms of both time consumption and memory usage. So, if I didn't do anything wrong, and if there isn't a better memoization technique for this, what we learned today is that (while recursion can be extremely useful, as rubberman noticed) for this particular problem (computing binomial / multinomial coefficients), arbitrary precision arithmetic is the way to go.
@m4ster_r0shi: OK the binomial coefficient in Python from my euler library:
from euler import timing
@timing
def binomial(n, k):
nt = 1
for t in range(min(k, n-k)):
nt = nt*(n-t)//(t+1)
return nt
print binomial(1600, 800)
"""Output:
binomial took 2.539 ms
886758324272110719282468686879536361457351622657983619121681971864823233331589221250359432261468147135933370909829053538163845995985088712282515329522750222379031947188666517397254719707323414953335609483867048436232634405323188637876061293480030952312211193078478973979253741391505347189612395970898130251421740603364990257291343139048628543399749402864756324566872108155027609528759946296604108771462220362337026916630726896133207343677015896455480787250090029343572616299975784
>>>
"""
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.