Does Algorithm::Combinatorics do what want you want? It's written in XS and thus probably one of the fastest ways of doing anything with combinations and permutations. The author has also taken care to use implementations that minimise the amount of memory required to keep track of where it is in the permutation space.
I've used it in the past and am very happy with it. The few conversations I had with the developer led to new releases being made in a short space of time.
• another intruder with the mooring in the heart of the Perl