How can I randomize a list with a certain degree of noise?

Question

If I have a list, say, [1,2,3,4,5], how can I introduce a certain amount of noise to this list?

For example, a high degree of noise would be something completely random. An adversarial noise would be [5,4,3,2,1] A low degree of noise would be [2,1,3,4,5]

Thoughts?

Answer 1

One mechanism would be to create a secondary list which is a weighted combination of the original order plus randomization, then sort the original list by the values of the secondary list.

In the code example provided below, parameter rho is used to determine the weighting. It can be set to any float value between -1 and 1, inclusive. A value of 1 preserves the original order, a value of -1 would correspond to what you call "adversarial" and reverses the order, and a value of 0 yields complete randomization. In other words, rho behaves somewhat like correlation—the magnitude reflects the degree to which original ordering is maintained, and the sign reflects the direction of the ordering.

You haven't specified a language, so here's an implementation in Python since that's likely to be accessible to a large number of people. Note that the function partial_ordering() does not mutate the input list, so data remains unaltered through the sequence of calls.

from math import sqrt
from random import random
from sys import exit

def partial_ordering(data, rho):
    if abs(rho) > 1:
        print("Invalid value for rho:", rho)
        exit(-1)
    n = len(data)
    weight = sqrt(1.0 - rho * rho)
    order_value = [rho * i + weight * n * random() for i in range(n)]
    pairing = [(data[i], order_value[i]) for i in range(n)]
    return [tpl[0] for tpl in sorted(pairing, key=lambda pair: pair[1])]

data = [i+1 for i in range(10)]

print(partial_ordering(data, 1))      # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(partial_ordering(data, -1))     # [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
print(partial_ordering(data, 0))      # [5, 9, 8, 2, 1, 4, 3, 6, 10, 7]
print(partial_ordering(data, -0.8))   # [7, 8, 9, 5, 4, 3, 10, 2, 1, 6]
print(partial_ordering(data, 42))     # Invalid value for rho: 42

Commented output is exact for rho values of 1 and -1, and representative of what you can expect for rho values with magnitudes below 1.