java ArrayList随机化所有元素的索引更改

Question

我如何随机化arrayList 因此，对于所有元素，旧索引不能与新索引相同

比如 有一个包含3个项目的列表

在arrayList之后随机化

旧指数<->；新索引

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

我想确认一下

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

Answer 1

以下是Fisher-Yates的一个变体，它迎合了至少一个项目将保持其原始位置的可能性

当前的Collections.shuffle()没有对列表执行完全的随机化

   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));
      }
   }

可能最终还是会有问题，但我使用了以下代码来测试 洗牌时没有发现问题

      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);
            }
         }
      }