Conference rusure::math

111.0. "Shuffling bytes" by TURTLE::GILBERT () Mon Jul 30 1984 02:14

A well-known hack for permuting a sequence of bytes is by using a TRANSLATE
instruction (MOVTC on VAXen - many mainframes have a similar instruction).
This instruction usually converts a (variable) source string via a (constant)
256-byte translation table.  If, instead, the source string is constant, and
the table is the sequence of bytes to be permuted, any permutation of bytes is
possible with a single TRANSLATE instruction -- if fewer than 256 bytes are to
be permuted.

What if the permutation is of more than 256 elements?  In particular, how many
TRANSLATE instructions are needed for an arbitrary permutation of N bytes?
ONLY TRANSLATE instructions are allowed, source string and destination string
lengths must be the same (portability!), and there's a nearly unlimited amount
of memory for temporary results.  Any tables may be preconditioned as desired.

					- Gilbert

Gimpel gives a "divide and conquer" algorithm that I think is minimal.
If string A is too long, then it divides it into two strings B and C
and uses the fact that REVERSE(A)=REVERSE(C) concatenated with REVERSE(B).

The SNOBOL 4 code follows:

	DEFINE('REVERSE(S)A1,A2,L')
*
* Initialize REV_ALPHA to hold the reversed alphabet.
*
	TEMP		= &ALPHABET
REV_1	TEMP		LEN(1) . T =			:F(REVERSE_END)
	REV_ALPHA	= T REV_ALPHA			:(REV_1)
*
* Entry point:
*
REVERSE	L		= SIZE(S)
	GT(L,SIZE(&ALPHABET))				:S(REV_2)
	LE(L,0)						:S(RETURN)
	&ALPHABET	TAB(*L) . A1
	REV_ALPHA	RTAB(*L) REM . A2
	REVERSE		= REPLACE(A2,A1,S)		:(RETURN)
*
* Divide and conquer.
*
REV_2	S		LEN(SIZE(&ALPHABET)) . A1 REM . A2
	REVERSE		= REVERSE(A1) REVERSE(A1)	:(RETURN)
REVERSE_END

		Reference

James F. Gimpel, Algorithms in SNOBOL4. John Wiley & Sons, New York: 1976.
	page 45, program 3.6.

This is still open.