Source Code 1992 March/Source_Code_CD-ROM_Walnut_Creek_March_1992.iso/usenet/altsrcs/1/1666

Internet Message Format | 1990-12-28 | 3.5 KB

From: [e-mail] (Maarten Litmaath)
Newsgroups: rec.puzzles,alt.sources
Subject: Re: Balls
Message-ID: <[e-mail]>
Date: 13 Aug 90 23:55:39 GMT

In article <[e-mail]>,
    [e-mail] (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)