NumCombsWithRep

[randy3k]

You could simply compute NumCombsWithRep with choose(n+r-1, r).

https://github.com/jwood000/RcppAlgos/blob/master/src/CombPermUtils.cpp#L84-L101

[randy3k]

Ha, I see that you credited me for the algorithm used in MultisetPermRowNum. It may be unclear from the algorithm, I was using a generating function to compute this. Check: https://www.quora.com/If-I-choose-n-elements-from-a-multiset-S-how-many-possible-combinations-orderless-and-sequences-ordered-are-possible/answer/Nick-Shales Though, I derived the formula and algorithm by myself as I couldn't find any resources talking about it when I first wrote iterpc.

[jwood000]

Hey @randy3k ,

Again, thanks for your input. As I stated in issue #2 , a lot of algorithms present in RcppAlgos come about rather organically. This is good and bad as many innovative approaches are born, however as you have pointed out here, I end up missing very simple implementations.

I will implement this improvement in the next commit and comment here when I've completed it.

Also, thanks for the extra bit of information on counting permutations of multisets as I too have had a difficult time finding any resources on this subject.

If you look back at how I was counting before, it was not pretty at all (lines 622 to 667 in commit 124): https://github.com/jwood000/RcppAlgos/blob/d689a7b897d45c17853264629ada6a5979a10cbf/src/CombinatoricsContainer.cpp#L622 I was generating all combinations of the multiset first, then counting the number of permutations of each of those combinations. Needless to say, it was expensive.

I don't have any benchmarks saved, but I vaguely remember that npermutations on multisets was thousands of times faster than what I was doing above.

Regards, Joseph

[jwood000]

Updated NumCombsWithRep to compute choose(n+r-1, r) instead of using the modified Pascal's triangle approach