Fw: [alicebot-archcomm] [discuss] <shuffle>

[Conan Callen]

There is a problem if the current item is swapped with an item at the end of
the array.
>                 swap A2[n] with A2[length of A2 - SwapIndex]
This looks like it would cause the items pushed to the end of the list to
get caught in an endless cycle.

To solve this the item is only pushed back x items. For instance, if you
dont want an item to re-occur for at least 3 (x = 3) iterations , its only
nessessary to push the item back in the array x items. This is the swap
offset.

Runtime - If the list is huge (hundreds or thousands of items) and x is
large then the grow rate could be large. If x is kept small the runtime
should not be bad. The list needs to be of some minum length for this
algorithm to be of use.

This psudo code is a little cleaner but still needs a lot of work. I didnt
compile or test it.

Begin Shuffle

Copy the last x items from the orginal array (a1) into a second array (a2)
(which only needs to be of length x).

index_type t; // temp variable used for swapping indexes
int o = x; // swap offset (how far to push an element back into the list)

for (n1 = 0 to x)
{
    for (n2 = 0 to x)
    {
        // SwapLoop - should not execute more then x-1 times.
        while (a1[n1] ==  a2[n2])
        {
            // If this is not the first time through the while loop
increment the swap offset,
            // so that we dont try to swap with the same element over and
over.
             if (n1)
                 o++; // Increment the swap offset

             // Do the swap.
             t = a1[n1 + o] ;
             a1[n1 + o] = a1[n1];
             a1[n1] = t;
        }
    }
}

Conan