dimanche 23 mai 2021

Change output of random list shuffle slightly when changing seed slightly

Problem:

I would like to randomly shuffle a list, but using a seed value s so that, when changing s value only slightly, the shuffle's output also only changes slightly.

Details:

I have a sorted list of elements, for example:

[0,1,3,5,7]

This list should be shuffled multiple times, each time using a seed value s. When two seed values s1 and s2 = s1 + d lie close to each other, then the shuffled lists should also be "similar".

By "similar", I mean that elements in the new shuffled list are either the same as they were when using the original seed value s1, or they are replaced only by values which are close to them in the original list (for example their direct neighbors in the original list).

Example for the above list (note how adding the small value d only perturbs the list slightly, i.e. many values stay the same and if they change, they are usually replaced by their neighbors in the original list):

Seed: Output:
s [5,0,1,7,3]
s + d [5,0,3,7,1]
s + 2d [7,0,3,5,1]
s + 3d [7,0,1,3,5]

Is there an algorithm for this? Is there a common name for this problem (or other search terms I could use)?

Ideas I had thus far:

I could use simplex/perlin noise to sample elements: I generate a number between 0 and 1 and then use it to choose the next element from the list (0 meaning I choose the first element, 1 meaning I choose the last). Since these noise types can be "smooth", adding d will change the random value only slightly, meaning it will usually select elements in proximity of the ones it picked before adding d. However, I have a very hard time choosing a "good" frequency for the noise (high frequencies will remove the smoothness I need, low frequencies will result in no change when adding d). Also, once the list shrinks as I pick elements, the effect of d will decrease, because the range 0 to 1 will be mapped to fewer elements - and I don't really know if this is a problem yet...?




Aucun commentaire:

Enregistrer un commentaire