better way to generate a permutation?

I'm putting the polish on pnmstega/pnmdestega.  Currently they spend
the largest part of their time generating the permuted list of bit positions
to use for storing the data bits.  Not surprising, I knew the first
version would be slow - it actually mallocs an array, fills it with
numbers, and shuffles them.  Now I'm looking for suggestions on better
methods.  I looked in Knuth, Sedgewick, and Schneier, and didn't
find anything.  Send email if you've got an idea.  Something with a
bit vector might work.
---
Jef