I am trying to create an algorithm to generate test cases. Each test case is an array of $n$ natural integers which are randomly generated using a pseudo-random function. The bound for $n$ is $0 < n \le 256$.

Each array is generated using a "repetitiveness/noise factor", $r$. If $r = n$, the elements of the array will all be individually computed with the pseudo-random function (therefore, the function is called $n$ times). On the lower bound, $r = 1$, all the elements of the array are generated at once (function is called once). As an other example, if $r = n-1$, the first two elements will be calculated at once, while the remaining elements will be computed individually.

Spreading the repetition across the elements should be preferred over calculating a repetition once: $[a, a, b, b, c]$ is preferred over $[a, a, a, b, c]$, even if both cases only call the pseudo-random function 3 times. As such, if $n$ is an even number, and $r = \frac n2$, then the array should consist of $r$ groups of 2 elements computed together.

If my explanation is not clear, perhaps some example data could help:

Given $n = 5$, $r = 5$, resulting array is $[a, b, c, d, e]$

Given $n = 5$, $r = 4$, resulting array is $[a, a, b, c, d]$

Given $n = 5$, $r = 3$, resulting array is $[a, a, b, b, c]$

Given $n = 5$, $r = 2$, resulting array is $[a, a, a, b, b]$

Given $n = 5$, $r = 1$, resulting array is $[a, a, a, a, a]$

  • $\begingroup$ "Each test case is an array of $n$ natural integers". Is it an array or a multiset? "Given $n=5$, $r=4$, resulting array is $[a,a,b,c,d]$". Since $a,b,c,d$ are generated by a random number generator, the actual value of them are allowed to be the same. What is wanted is that $a,b,c,d$ are generated using the generator four times. Right? $\endgroup$ – Apass.Jack Dec 31 '18 at 1:00
  • $\begingroup$ @Apass.Jack It is an array. The values are allowed to be the same as they are random, even if they are computed individually using the function. You are correct. $\endgroup$ – Momo Dec 31 '18 at 1:14

I found a rather simple solution using recursion. Here is an implementation in python3:

def algo(R, N):
  rep = math.ceil(N / R)
  array = [random.randint(0, 256)] * rep
  if N > 1:
    return array + algo(max(R - 1, 1), N - rep)
  return array

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.