Shuffeling string, так что в оригинальном месте нет объекта

Question

Есть ли способ перетасовать массив строк так, чтобы в исходной позиции ни одна строка не была? Вращение не является опцией

Answer 1

Вы можете реализовать Fisher-Yates Shuffle, но на каждой итерации исключить текущую позицию из случайного диапазона. На самом деле это a common mistake, что снижает качество перетасовки.

EDIT: чтение, я вижу, что это на самом деле имеет имя: Sattolo's Algorithm.

Answer 2

Это всего лишь один метод. Я уверен, что есть более быстрые или более эффективные методы, но это работает отлично.

static Random r; 
public static String[] shuffle(String[] input) 
{ 
    if(r == null) r = new Random(); 

    String[] output = new String[input.length]; 
    ArrayList<Integer> indices = new ArrayList<Integer>(); 

    for(int i = 0; i < input.length; i++) indices.add(i); 

    for(int i = 0; i < output.length; i++) 
    { 
     int randomIndicesIndex = r.nextInt(indices.size()); 
     int randomIndex = indices.get(randomIndicesIndex); 
     indices.remove(randomIndicesIndex); 
     output[i] = input[randomIndex]; 
    } 

    return output; 
} 

Когда вызывается в цикле, он выводит этот результат:

01: Hilda, Quinn, Lyon, Danny, Rob, Clyde, Joe, Jeff, Samantha 
02: Hilda, Samantha, Clyde, Danny, Lyon, Joe, Quinn, Rob, Jeff 
03: Rob, Samantha, Hilda, Joe, Danny, Jeff, Lyon, Clyde, Quinn 
04: Jeff, Lyon, Joe, Quinn, Clyde, Hilda, Rob, Danny, Samantha 
05: Danny, Jeff, Hilda, Lyon, Joe, Samantha, Rob, Clyde, Quinn 
06: Lyon, Danny, Jeff, Quinn, Rob, Hilda, Clyde, Samantha, Joe 
07: Clyde, Hilda, Rob, Samantha, Lyon, Quinn, Danny, Jeff, Joe 
08: Clyde, Jeff, Samantha, Danny, Quinn, Hilda, Joe, Lyon, Rob 
09: Jeff, Samantha, Danny, Clyde, Rob, Joe, Quinn, Lyon, Hilda 
10: Clyde, Samantha, Danny, Lyon, Rob, Hilda, Quinn, Jeff, Joe