0

I'm currently working on a Travelling salesman problem and i'm having trouble generating random paths with the same start and end value

This is my current path(path of cities visited)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 38 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 14 39 40 41 42 43 44 45 46 47 48 49 50 51 0

See how the last node arrives back at 0(TSP logic)

Now i'm trying to shuffle this array randomly because random start points generate better results then others However I know how to shuffle the array using Collections but that would shuffle every value randomly

Basically i'm trying to create a method to shuffle an array randomly WITH THE EXCEPTION THE START and END VALUES must be the same and every number must be distinct 0-51

This is my current code, it basically shuffles the array and sets the last index to the first index

  static void shuffleArray(int[] ar)
   {
// If running on Java 6 or older, use `new Random()` on RHS here
Random rnd = new Random();
for (int i = ar.length - 1; i > 0; i--)
{
  int index = rnd.nextInt(i + 1);
  // Simple swap
  int a = ar[index];
  ar[index] = ar[i];
  ar[i] = a;
}

ar[ar.length-1]=ar[0];
 }

however this is giving me duplicate values for some reason

rahul chawla
  • 15
  • 6
  • http://idownvotedbecau.se/nocode/ --- Show the code you do have, i.e. how *you* shuffle using `Collections`. Then we'll show you how [`subList()`](https://docs.oracle.com/javase/8/docs/api/java/util/List.html#subList-int-int-) works. Or you could just read the javadoc I linked to. – Andreas Mar 11 '18 at 05:58
  • @Andreas doneee – rahul chawla Mar 11 '18 at 18:23
  • No, basically andreas, I want to generate a random path, a path where the start point and end point is the same, if I want to SHUFFLE THE ARRAY I also want to change the start path because some start points have much better results, however I want to keep the consistence that their are no duplicates and the start and end values are the SAME. example 0 2 4 6 8 5 0 -> 1 2 4 6 8 5 0 1 – rahul chawla Mar 11 '18 at 18:51
  • @Andreas ....... – rahul chawla Mar 11 '18 at 18:51
  • You're getting a duplicate value because your have one duplicate value to begin with, i.e. the value in first and last position. Shuffle the array, **excluding** the last index, i.e. start the loop at `ar.length - 2`, and you're good. – Andreas Mar 11 '18 at 18:55
  • Seems to work! Can you explain why though? @Andreas – rahul chawla Mar 11 '18 at 18:58
  • Why what? I don't understand your question. The value at last index should always be same as value at first index, which is why you have the last statement in that method. So you excluding that *duplicate* value from the shuffle. All the other values are unique, and your shuffle is good, so they are still unique after shuffling. What's hard to understand here? Or are you saying you don't actually understand how the shuffle works? That you copied the code from somewhere without understanding it? Then perhaps a bit of research would do you good. – Andreas Mar 11 '18 at 19:04

1 Answers1

2

Could you not remove the start and end position, shuffle the array, and then add the start and end position again?

Paul C
  • 303
  • 5
  • 15