ArrayList randomize with index change for all elements

Question

How can I randomize arrayList so that old index must not be the same as new index for all elements

for example with a list with 3 items

after arrayList randomize

old index<->new index

1<-->2 <--different
2<-->1 <--different
3<-->3 <--same is not allowed

I want to make sure it will be

1<-->3 <--different
2<-->1 <--different
3<-->2 <--different

Answer 1

Collections.shuffle(List<?> list)

This should work with Lists which don't contain null values:

static <T> void shuffleList(List<T> list) {
    List<T> temp = new ArrayList<T>(list);
    Random rand = new Random();

    for (int i = 0; i < list.size(); i++) {
        int newPos = rand.nextInt(list.size());
        while (newPos == i||temp.get(newPos)==null) {
            newPos = rand.nextInt(list.size());
        }
        list.set(i, temp.get(newPos));
        temp.set(newPos,null);
    }
}

For list with null values:

static <T> void shuffleList(List<T> list) {
    List<T> temp = new ArrayList<T>(list);
    Integer [] indexes=new Integer[list.size()];
    for (int i=0;i<list.size();i++){
        indexes[i]=i;
    }
    Random rand = new Random();

    for (int i = 0; i < list.size(); i++) {
        int newPos = rand.nextInt(list.size());
        while (newPos == i||indexes[newPos]==null) {
            newPos = rand.nextInt(list.size());
        }
        list.set(i, temp.get(newPos));
        indexes[newPos]=null;
    }
}

Answer 2

That's something you have to implement yourself.

• The shuffle is probably a series of random swaps (e.g. swap 1 -> 4, swap 3 -> 2).
• Keep track of each element's new position (e.g. 4 3 2 1 5 for a list with 5 elements and the above shuffle operations).
• If any element is still at it's old place (5 in that example), keep on shuffling.

Sounds like fun.

Answer 3

var numExist = [];
while(numExist.length!=array.length){
  var randomizer = new Random();
  int i =0;
  var num = randomizer.nextInt(array.length);
  if(!numExist.contains(num)){
    array[i]=array[num];
    numExist.add(num);
    i++;
  }
}

Answer 4

The following is a variation of Fisher-Yates which caters to the possibility that at least one item will remain in its original position.

The current Collections.shuffle() does not perform a complete randomization of the list.

   public static void shuffle(List<Integer> list) {
      Random r = new Random();
      int size = list.size();
      boolean flag = true;
      for (int i = size - 1; i >= 0 && flag; i--) {
         int pos = r.nextInt(i + 1);
         if (list.get(i) == pos) {
            if (i == 0) {
               flag = false;
               break;
            }
            // counter the upcoming decrement by incrementing i
            i++;
            continue;
         }
         int temp = list.get(i);
         list.set(i, list.get(pos));
         list.set(pos, temp);
      }

// At this juncture, list.get(0) points to itself so choose a random candidate
// and swap them.

      if (!flag) {
         int pos = r.nextInt(size - 1) + 1;
         int temp = list.get(0);
         list.set(0, list.get(pos));
         list.set(pos, list.get(0));
      }
   }

There may still be eventual problems but I used the following code to test the shuffle with no problems detected.

      for (int k = 0; k < 100000; k++) {
         List<Integer> list =
               IntStream.range(0, 52).boxed().collect(Collectors.toList());
         System.out.println("Test run #" + k);
         // Collections.shuffle(list);
         shuffle(list);
         for (int i = 0; i < list.size(); i++) {
            if (i == list.get(i)) {
               System.out.printf("Oops! List.get(%d) == %d%n", list.get(i), i);
            }
         }
      }