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

[Noel Bush]

This discussion illustrates why Anne's approach that uses a type
attribute to qualify an element makes sense.  It looks likely that there
might be a lot of variations on a theme, and that we should leave room
for growth without cluttering the spec with a lot of tag names.

I guess my criterion for deciding whether to create a new tag name, or
whether to add an attribute that "refines" a particular algorithm, would
be this: Would the "default" behavior for a given element be acceptable
in all cases in which an AIML interpreter didn't know about the
attribute-qualified variant?

I made the case that the current <random> behavior would *not* be
acceptable in all cases where someone used the proposed <shuffle>.  On
the other hand, it could well be that variants of <shuffle> being
discussed (and illustrated in pseudocode) could be acceptably
substituted for by the "plainest" form of shuffle imaginable (i.e., one
that doesn't take into account the additional subtleties that Chris and
Conan brought up).

So could it be that

* <random> remains as-is
* <shuffle> is new and has a default implementation as first described
* <shuffle type="more-random"> is a variant that addresses the concerns
under discussion (perhaps with the specifics left a little more open)
* Over time we might add other attributes to <shuffle> designating other
variants.

?

On Fri, 2002-05-17 at 09:52, Conan Callen wrote:
> 
> 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
> 
> _______________________________________________
> alicebot-archcomm mailing list
> alicebot-archcomm@list.alicebot.org
> http://list.alicebot.org/mailman/listinfo/alicebot-archcomm
>