Mdthbs

I need to create a circle with numbers from 1 to n , however it is necessary to respect some rules:

1. All numbers from 1 to n are used in the circle only once.


2. The sum of two consecutive numbers is a prime number


3. The sum of a number with what is diametrically opposite it is also a prime number

So I need to create an algorithm that receives an integer n
and determines whether there is a circle of size n, if it exists.

For example:

Program response: 1 6 7 16 15 8 5 12 11 18 13 10 3 4 9 14 17 2

I managed to get the expected result, but I do not know if I made the faster way, or if there is something badly written.

import java.sql.Date;

import java.text.SimpleDateFormat;

import java.util.ArrayList;

import java.util.Vector;



import javax.swing.JOptionPane;



public class QuintoDesafio {



    private static int j;

    private static int k;



    private static Vector primes  = new Vector();



    public static void main(String[] args) 

    { 



        long start = System.currentTimeMillis();  



        ArrayList list = new ArrayList();



        primes.add( new Integer( 2 ) );

        primes.add( new Integer( 3 ) );

        primes.add( new Integer( 5 ) );

        primes.add( new Integer( 7 ) );

        primes.add( new Integer( 11 ) );

        primes.add( new Integer( 13 ) );

        primes.add( new Integer( 17 ) );

        primes.add( new Integer( 19 ) );

        primes.add( new Integer( 23 ) );

        primes.add( new Integer( 31 ) );

        primes.add( new Integer( 37 ) );

        primes.add( new Integer( 41 ) );



        String n = JOptionPane.showInputDialog( "Input n (even) ");

        int ene = Integer.parseInt( n );



        for ( int i=1; i <= ene; i++ ) {

            list.add( new Integer(i) );

        }

        exchange(list, 0);



        long end  = System.currentTimeMillis();   

        System.out.println(new SimpleDateFormat("ss.SSS").format(new Date(end - start)));  

    }



    static void exchange(ArrayList arr, int k){

        boolean passed = true; 



        for(int i = k; i < arr.size(); i++){

            java.util.Collections.swap(arr, i, k);

            exchange(arr, k+1);

            java.util.Collections.swap(arr, k, i);

        }

        if (k == arr.size() -1){

            int half = arr.size()/2;



            for ( int j=0; j<arr.size(); j++ ) {

                int one = (int) arr.get(j);

                int two;

                if ( j+1 == arr.size() ) {

                    two = (int) arr.get(0);

                } else {

                    two = (int) arr.get(j+1);

                }

                Integer number_test = new Integer( one+two );

                if ( !primes.contains( number_test )) {

                    passed = false;

                }

            }



            for ( int j=0; j<half; j++ ) {

                int one = (int) arr.get(j);

                int two = (int) arr.get(j+half);

                Integer number_test = new Integer( one+two );

                if ( !primes.contains( number_test )) {

                    passed = false;

                }

            }

            if ( passed ) {

                System.out.println(java.util.Arrays.toString(arr.toArray()));

            }

        }

    }

}

```

First, Vector shouldn't be used here. It's essentially a synchronized ArrayList, and you don't need any synchronization in this case. Just change it to an ArrayList.

This has the potential to be a little faster.

Second, you're using a raw ArrayList which isn't typesafe:

list.add("Some nonsense"); // Doesn't cause an error

and is necessitating your (int) type-casts later on. Specify that the list is holding integers using generics, and it will be typesafe. Read the < > as "of" here:

// Note how we specify what the list can hold

// An ArrayList of Integers

ArrayList<Integer> list = new ArrayList<>();



list.add("Some nonsense") // This causes an error now at compile time

You're also doing odd stuff with the Integer constructor. You don't need to manually cast unboxed integers like Integer(2). 2 will be "auto-boxed" into its object wrapper as necessary implicitly.

You're calling Integer/parseInt outside of a try; which is risky. If the user enters bad input, your whole program with crash. Wrap it up and handle failure (yes, users will enter bad input):

try {

    int ene = Integer.parseInt(n);

    // Code using "ene"



} catch (NumberFormatException e) {

    // Just an example. You'll need to do something more involved, like re-asking for input

    System.out.println("Parse failed");

}

Just as an example of what I mentioned earlier:

static void exchange(ArrayList arr, int k){

    ...

    int one = (int) arr.get(j);

    int two = (int) arr.get(j + half);

    Integer number_test = new Integer(one + two);

Make the parameter generic, and do away with the casts and boxing. Just write:

static void exchange(ArrayList<Integer> arr, int k){

    ...

    int one = arr.get(j);

    int two = arr.get(j + half);

    int number_test = one + two;

And then similarly below that.

Also, Java prefers camelCase, not snake_case. It's best to stick to the conventions of the language you're using.

import java.sql.Date;

is a little worrying. You shouldn't really be raiding a SQL library just to make use of some date object. Java has a java.time package for this purpose.

Just as a tip,

int two;

if (j + 1 == arr.size()) {

    two = arr.get(0);



} else {

    two = arr.get(j + 1);

}

Can also be written as:

int two = j + 1 == arr.size() ? arr.get(0) : arr.get(j + 1);

or, alternatively:

int two = arr.get(j + 1 == arr.size() ? 0 : j + 1);

Depending on how much duplication you can tolerate. The ? : part is known as the "ternary operator"/a "conditional expression".

if (!primes.contains(number_test)) {

This is quite expensive when done on a List like an ArrayList. If you need to use contains, you should probably be using a Set like a HashSet. Membership lookups are much faster using sets. The time difference will become increasingly noticeable as primes grows.

Your algorithm, if I understand it correctly, is to recursively enumerate all permutations and then check every one of them until a solution is found. There is a very simple improvement to that which can skip huge chunks of the search space: try to detect violations of the constraints as early as possible.

For example, if the current permutation starts with "1, 3, .." and we are in the process of calling exchange recursively to create the "tails" of these permutations, then all work done by these recursive calls will ultimately be useless. At this point it is unavoidable that the "1, 3" pair will violate the second constraint no matter what the rest of the permutation will be. If this situation was detected, we could return straight away and continue with "1, 4, ..". It should be possible to adapt your current check to work on a partial configuration, and use it to prune in this way.

To give a sense of the impact, with this pruning and nothing especially clever, my code takes 0.06s on ideone for that circle of 18 elements.