It is necessary to obtain an array of size 4, the values ​​of which elements are in the range from 1 to 4 and are not repeated.

Those. array must be, for example, 3 1 4 2 or 1 3 4 2.

What is the optimal algorithm for solving the problem?

  • Typically, such problems are solved by mixing the array of 1, 2, 3, 4. - Vladimir Gamalyan
  • 2
    or in this case it is possible to generate all 24 permutations with handles and then with the usual random select one of them. This is one of the fastest ways in this case. For 6 or more items is no longer suitable. - KoVadim
  • Why? Perfect fit. We generate random from 1 to max. quantities, and expand the number in the option. Generating all the options is not necessary. - Akina
  • one
    And what is your optimality criterion? - VladD

5 answers 5

You can use the static shuffle method of the Collections class:

 ArrayList<Integer> data = new ArrayList<Integer>(); for (int i = 1; i <= 4; i++) data.add(i); Collections.shuffle(data);

And then you can use the data.toArray () to get the necessary array.

  • An interesting option, thank you, I will test it by "chance". - user214046
  • one
    @ Alexander this method implements the Fisher-Yates shuffling algorithm - Mikhail Vaysman

Using one of the options for Fisher-Yates shuffling :

 public static void main(String[] args) { int[] array = { 1, 2, 3, 4 }; Random rand = new Random(); for (int i = array.length - 1; i > 0; i--) { int index = rand.nextInt(i + 1); int swap = array[index]; array[index] = array[i]; array[i] = swap; } System.out.println(Arrays.toString(array)); }

    In addition to the array shuffle option, another one that does not require pre-filling the array:

     int n = 4; int[] a = new int[n]; for (int i = 0; i < n; ++i) { int j = rand.nextInt(i + 1); a[i] = a[j]; a[j] = i + 1; }

    Another advantage of this approach is that in the process of shuffling, you can increase the size of the array (with the correction variable n).

    If you need a sequence starting from zero, then you can remove + 1 in the last but one line.

    Link to a working example.

    • Interestingly. I did not expect it to work. And with probabilities, is everything just fine? - Qwertiy ♦
    • @Qwertiy think no worse than Fisher-Yates, because This is his turned version . - Vladimir Gamalyan
    • @Qwertiy tested on 100 million code runs. Probabilities almost do not differ from 0.25, so everything is fine. - Regent
    • Thank you, I will consider the option for speed, relative to other algorithms - user214046
    • @Alexander "turned out" algorithm, as well as the modern algorithm from my answer, works in linear time. For an array of 4 elements, you will not notice the difference in speed. Longer work options with IntStream and Collections.shuffle , I think, can be seen only if you run the code a thousand times. - Regent

    You can do this:

     private static int[] getArray(int dimension) { Random random = new Random(); return IntStream .generate(() -> random.nextInt(dimension) + 1) .distinct() .limit(dimension) .toArray(); }

      Crooked, slows down the program, but you can:

       public class Name { static int items = 4; static int wait = 500; static List<Integer> a = new ArrayList<>(); public static void main(String[] args) throws InterruptedException { for (int id = 0; id < items; id++) new Rand(id).start(); Thread.sleep(wait); for (int i = 0; i < items; i++) System.out.println(a.get(i)); } public static synchronized void addA(int i) { a.add(i); } static class Rand extends Thread { int id; public Rand(int id) { this.id = id; } @Override public void run() { try { Thread.sleep(new Random().nextInt(wait)); } catch (InterruptedException e) {e.printStackTrace();} addA(id); } } }
      • In a nutshell: we start items' streams, they add values ​​to the array "a", equal to their id (id is given in order of creation of threads) - Max.