Balls

[Maarten Litmaath]

In article <1990Aug8.141722.26196 at specialix.co.uk>,
	jonb at specialix.co.uk (Jon Brawn) writes:
)[Urm.... I do hope I don't need to be anyone special to post these things...]

You only gotta have BALLS!  :-)

)Imagine, if you will, that you posses four balls, (0, 1, 2, and 3)
)Now, you can arrange these four balls in 24 permutations:
)
)        0 1 2 3,     1 0 2 3,    2 0 1 3,    3 0 1 2,
)        0 1 3 2,     1 0 3 2,    2 0 3 1,    3 0 2 1,
)        0 2 1 3,     1 2 0 3,    2 1 0 3,    3 1 0 2,
)        0 2 3 1,     1 2 3 0,    2 1 3 0,    3 1 2 0,
)        0 3 1 2,     1 3 0 2,    2 3 0 1,    3 2 0 1,
)        0 3 2 1,     1 3 2 0,    2 3 1 0,    3 2 1 0.
)
)It is desired to have a function that yields an integer (0-23)
)that uniquely identifies each of the above sequences. [...]

Included are 2 C functions `perm' and `perm_number', each accompanied by
a small main program.  Compile them like this:

	cc -o perm perm.c
	cc -o perm_number perm_number.c

Example session:

	$ perm 16 0123
	2301
	$ perm 479001599 ab,de+g=ij.l
	l.ji=g+ed,ba
	$ perm_number lkjihgfedcba abcdefghijkl
	479001599

That's right!
--
: This is a shar archive.  Extract with sh, not csh.
: This archive ends with exit, so do not worry about trailing junk.
: --------------------------- cut here --------------------------
PATH=/bin:/usr/bin:/usr/ucb
echo Extracting 'perm.c'
sed 's/^X//' > 'perm.c' << '+ END-OF-FILE ''perm.c'
Xint	perm(n, nullperm, length, dest)
Xlong	n;
Xchar	*nullperm, *dest;
Xint	length;
X{
X	long	f;
X	int	d;
X	char	*p, *q, *r, *malloc();
X
X	if (!(p = malloc(length)))
X		return -1;
X
X	strncpy(p, nullperm, length);
X
X	for (d = --length, f = 1; d > 0; d--)
X		f *= d;
X
X	while (length > 0) {
X		d = n / f;
X		*dest++ = p[d];
X		if (!d)
X			p++;
X		else
X			for (q = p + d, r = q + 1; *q++ = *r++; )
X				;
X		n -= f * d;
X		f /= length--;
X	}
X
X	*dest++ = *p;
X	*dest = '\0';
X
X	free(p);
X
X	return 0;
X}
X
X
Xmain(argc, argv)
Xint	argc;
Xchar	**argv;
X{
X	char	buf[32];
X	long	atol();
X
X	if (argc > 2) {
X		perm(atol(argv[1]), argv[2], strlen(argv[2]), buf);
X		printf("%s\n", buf);
X	}
X}
+ END-OF-FILE perm.c
chmod 'u=rw,g=r,o=r' 'perm.c'
set `wc -c 'perm.c'`
count=$1
case $count in
644)	:;;
*)	echo 'Bad character count in ''perm.c' >&2
		echo 'Count should be 644' >&2
esac
echo Extracting 'perm_number.c'
sed 's/^X//' > 'perm_number.c' << '+ END-OF-FILE ''perm_number.c'
Xlong	perm_number(s, nullperm, n)
Xchar	*s, *nullperm;
Xint	n;
X{
X	long	number = 0;
X	char	*q, *r, *c_index, *t, *malloc(), *index();
X
X	if (!(t = malloc(n)))
X		return -1;
X
X	strncpy(t, nullperm, n);
X
X	while (--n > 0) {
X		if (!(c_index = index(t, *s++))) {
X			number = -1;
X			break;
X		}
X		number += c_index - t;
X		number *= n;
X		if (c_index == t)
X			t++;
X		else
X			for (q = c_index, r = q + 1; *q++ = *r++; )
X				;
X	}
X
X	free(t);
X
X	return number;
X}
X
X
Xmain(argc, argv)
Xint	argc;
Xchar	**argv;
X{
X	if (argc > 2)
X		printf("%ld\n",
X			perm_number(argv[1], argv[2], strlen(argv[2])));
X}
+ END-OF-FILE perm_number.c
chmod 'u=rw,g=r,o=r' 'perm_number.c'
set `wc -c 'perm_number.c'`
count=$1
case $count in
572)	:;;
*)	echo 'Bad character count in ''perm_number.c' >&2
		echo 'Count should be 572' >&2
esac
exit 0
--
   "UNIX was never designed to keep people from doing stupid things, because
    that policy would also keep them from doing clever things."  (Doug Gwyn)