Tell the algorithm that will fill the array with random numbers between which there will be a difference of 5 more or less from the number that is already in the array, for example, the array should be like this: [26,1,6,20,11] , where in the array there can be any numbers and in any order, but with the proviso that they are separated from each other by 5 or less. It is like a range.

The numbers can be in any order, the sequence but the values ​​of these numbers should not be + -5 from the already existing number in the array.

THOSE. this may be: [10,5,20,15] or so: [100,5,20] .

And so It can not be: [9,5,11,3] or so also can not: [100,104,96]

    2 answers 2

    Let's look at the geometric interpretation of your assignment.

    Let our range of admissible numbers [a, b] , and we need to create an array of length n . Then we need to throw n different numbers on the segment [a, b] n so that the distance between them is at least 5.

      [ a _ _ _ _ _ * _ _ _ _ _ _ * _ _ _ _ _ _ _ _ _ _ _ _ _ b ] | | |<--- >=5 --->|

    We add to each of the numbers a “neighborhood” with a diameter of 2. Then it turns out that we need to inscribe in the segment [a - 2, b + 2] n such non-intersecting neighborhoods:

     [ A _ _ _ _ _ * * * * * _ _ * * * * * _ _ _ _ _ _ _ _ _ _ _ _ _ B ]

    ( A = a - 2 , B = b + 2 ). In this case, the beginning of the neighborhood must also have integer coordinates.

    We collapse each of the neighborhoods into a point, and the length of the entire segment will decrease by 4 * n .

    Now our picture is simplified: for the segment of length (b + 2) - (a - 2) + 1 - 4 * n you need to throw n different points. And this is a well-known task. It is solved with the help of the classic random sampling with a tank , here is the code in C #. We modify it for our needs:

     int[] Generate(int a, int b, int n) { int max = (b + 2) - (a - 2) + 1 - 4 * n; if (n > max) throw new Exception("Задача неразрешима"); int[] result = ReservoirSampling(n, max); // выборка неотсортирована, сортируем Arrays.sort(result); // и возвращаем нужные индексы: for (int i = 0; i < n; i++) result[i] += a + (4 * i); return result; } int[] ReservoirSampling(int n, int max) { Random r = new Random(); // этот экземпляр нужно сделать глобальным int[] result = new int[n]; for (int i = 0; i < n; i++) result[i] = i; for (int i = n; i < max; i++) { int j = r.nextInt(i + 1); if (j < n) result[j] = i; } return result; }

    Check: http://ideone.com/yCLwqg

      Maybe I did not quite understand the question, but what prevents me from choosing an arbitrary number, filling the array with numbers each time increasing the previous number by n, and then mixing the elements of the array?

      The code will look like this:

       int number = 5; int count = 10; List<Integer> list = new ArrayList<>(count); list.add(ThreadLocalRandom.current().nextInt(100)); for (int i = 1; i < count; i++) list.add(list.get(i - 1) + number); Collections.shuffle(list); System.out.println(list);

      Conclusion

      [111, 106, 116, 91, 121, 81, 96, 76, 101, 86]

      • If you simply increase each time, you can climb over the upper limit. - VladD
      • Something I do not see in the question of mentioning the upper limit, but if we are talking about overflow, then nothing prohibits taking a random number with an eye on Integer.MAX_VALUE - Artem Konovalov
      • Okay, I agree. But then another problem: your algorithm does not give all possible solutions. For example, he will never give out [1, 7, 512] . This is in theory not very good, the result is not accidental. - VladD