algorithm - What's a good one-pass pseudo-random shuffle? -

the fisher-yates shuffle gives nice algorithm shuffle array a of length n in single pass:

for k = 1 n     pick random integer j k n     swap a[k] , a[j] 

after single pass through algorithm, entries of a occur uniformly @ random.

a common way botch algorithm following:

for k = 1 n     pick random integer j 1 n     swap a[k] , a[j] 

the resulting distribution single pass through algorithm not uniformly random, , there nice discussion of @ post: what distribution broken random shuffle?

i read delightful article diaconis, fulman , holmes entitled analysis of casino shelf shuffling machines authors describe physical machine following batch shuffle:

for k = 1 n     pick random integer j 1 10     randomly choose place card k on top or bottom of stack j 

the question authors address whether or not gives reasonably random ordering after single pass. answer decidedly not. 1 way see flaw in shuffle start deck of cards has n/2 red cards atop of n/2 black cards. resulting deck after single pass have @ 10 clumps of red cards! n = 52*6, isn't terribly random. authors show optimal "guess next card" strategy once shuffled will, on average, correctly guess 9.5 cards, whereas optimal strategy random deck average 4.5 cards correctly guessed.

are there other interesting single-pass shuffles achieve near-randomness and/or interesting distributions? i'm interested in shuffles similar latter work batches of entries.

if have shuffled desk, wish shuffle batch of new cards (and know none of cards duplicates), think following valid.

foreach card in batch:     gap = random(deck.size() + 1)  # choose gap between cards, before first, or after last.     deck.insertat(gap,card) 

distribution

the distribution of random uniform, , order of deck unchanged, still uniform. think result should uniform. (my stats rusty sure).

time

assuming insertat o(1) not o(n) - depends upon implementeation of deck - whole routine o(batch size) - best can hope becuase have handle each card.