Michael.Pohoreski

Buddhabrot

Single core and multi-core versions of the Buddhabrot renderer are now hosted on [GitHub Michaelangel007/buddhabrot]. This [2880x2160 bitmap @ 32,768 depth] took 42 minutes utilizing 8 cores on an i7 @ 2.6 GHz!

See my [ http://en.wikipedia.org/wiki/User_talk:Michael.Pohoreski ] discussion page if you want to leave feedback. Thx.

Ray Marching

• "HOWTO: Get Started with Ray Marching"

Combinations & Permutations

Note: A full white paper _"Understanding Permutations and Combinations for Programmers"_ is forthcoming ...

---

I originally posted this beautiful symmetry between Permutations (Variable Bit Decoding) and Combinations (Constant Bit Decoding) to the Permutations page.

This is the last revision it appeared. http://en.wikipedia.org/w/index.php?title=Permutation&oldid=342103380#Encoding_and_decoding

Encoding and decoding

One can map every possible permutation state of a given set of size n to a unique factoradic integer k , where k ranges from 1 to n! . Iterating the previous or next permutation becomes a trivial add or subtract one. One can also compactly store this permutation state, compared to storing the permutation itself (as we only need to store Ceiling(Log(n!) / Log(2)) bits compared to n*Ceiling(Log(n) / Log(2)) bits.)

i.e. Given a size of 3, iterating all possible values for k gives the following permutations:

1. ABC
2. ACB
3. BAC
4. BCA
5. CAB
6. CBA

i.e. One could represent a deck of cards using to Log(52!)/Log(2) = 226 bits compared to the standard 6-bits per card * 52 cards = 312 bits.

The question becomes:

1. how does one encode the permutation state into a unique value k, and
2. how does one decode a specific value k into the permutation state.

Encoding and Decoding a given sequence to the unique integer is a variation on Variable Bit Decoding, where the base changes size every iteration. The following sample code demonstrates the beautiful symmetry between Permutations (Variable Bit Decoding) and Combinations (Constant Bit Decoding)

void String_Reverse( char *pSrc, int nLen )
{
    if( nLen > 1 ) {
        char *pMid = pSrc + (nLen >> 1); // floor(nLen/2)
        char *pDst = pSrc + nLen - 1;
        char  nTmp;
        while( pSrc < pMid ) {
             nTmp   = *pSrc; // t <- s
            *pSrc++ = *pDst; //      s <- d
            *pDst-- =  nTmp; //           d <- t
        }
    }
}

// Also known as: itoa() !
void Constant_Bit_Decoding( int n, char * const pOutput_, const int nBase )
{
    int  d, r;
    char aDigits[] = "0123456789ABCDEF";
    int  nDigits = 0; // variable length output!
    char *pDst = pOutput_;

    if( nBase > 0 )
        do
        {
            d = n / nBase; // nBase = constant
            r = n % nBase; // nBase = constant
            n /= nBase;
            *pDst++ = aDigits [ r ];

            // Combination: re-use all elements
            nDigits++;
        } while( n > 0 ); // combination: n > 0

    // combination: reverse string
    String_Reverse( pOutput_, nDigits );
    *pDst = 0;
}

// Unpack Permutation Enumeration
// See: "Procedures of encoding and decoding of permutations"
void Variable_Bit_Decoding( int n, char * const pOutput_, int nBase )
{
    int  d, r;
    char aDigits[] = "0123456789ABCDEF";
    int  nDigits = nBase; // constant length output!
    char *pDst = pOutput_;

    if( nBase > 0 )
        do
        {
            d = n / nBase; // nBase = variable
            r = n % nBase; // nBase = variable
            n /= nBase;
            *pDst++ = aDigits[ r ];

            // Permutation: Remove 'r'th element
            int nDigits = nBase - r - 1;
            if( nDigits > 0 ) {
                memcpy( aDigits + r, aDigits + r + 1, nDigits );
            }
            nBase--;
        } while( nBase > 0 ); // permutation: nbase > 0
    // permutation: nothing to do
    *pDst = 0;
}

int main(int nArg, char* aArg[] )
{
    int nBase = 3;
    int nMax = 6; // nBase!
    char aBuffer[ 32 ];

    // print off all combinations of [0 ...nMax] in base nBase
    printf("Combinations:\n#    Base %d\n", nBase );
    for( int iEncoded = 0; iEncoded < nMax; iEncoded++ ) {
        Constant_Bit_Decoding( iEncoded, aBuffer, nBase );
        printf( "%d -> %s\n", iEncoded, aBuffer );
    }
    printf("\n");

    // print off all permutations of nBase!
    printf("Permutations:\n#    Enumerate %d!\n", nBase );
    for( int iEncoded = 0; iEncoded < nMax; iEncoded++ ) {
        Variable_Bit_Decoding( iEncoded, aBuffer, nBase );
        printf( "%d -> %s\n", iEncoded, aBuffer );
    }
    printf("\n");

    return 0;
}

Minor edit: Fixed spelling.