Given a String array, how to create a second array which is a rearrangement of the original?

Question

I am trying to create a method to takes an array of names and returns a copy of the list with the names randomly rearranged. The code below returns a new list with duplicated names. what can I do to shuffle names of the new list instead?

public static String[] shuffle(String []names)
{
    int num =0;  
    String [] newArray = new String [names.length];
    Random r = new Random (); 
    for(int i = 0; i<names.length; i++){
        num = r.nextInt(names.length);
        if((i-1)!=num){
            newArray[i]=names[num];
        }
    }
    return newArray;
}

amit · Answer 1 · 2012-10-12T23:19:52.140

You can use Collections.shuffle() to shuffle a list.

If you are eager to do it by your own - have a look on fisher-yates shuffle.
(Pseudo code:)

for (i = n-1; i >= 0; i--) 
    swap(names,i,r.nextInt(i+1));

(Where swap() is a standard swapping function to swap two elements in an array)

(Note, if you want a new instance with the shuffled array - just copy it using Arrays.copyOf() before running the algorithm.

score 1 · Answer 2 · answered Oct 12 '12 at 23:12

1

Collections.shuffle(list)

Info

You can use the ToList to make it a list for the shuffle and then back to an array with ToArray.

This may not be the most efficient but it is the easiest.

answered Oct 12 '12 at 23:12

Brad Semrad

1,501
1
11
19

score 1 · Accepted Answer · edited Oct 13 '12 at 00:10

1

Like others have suggested there are already other cleaver/easy ways to do this, but to solve the issue in your code you need to make the newArray a copy of the names array (you can can use Arrays.copyOf) and then properly swap the values, like:

if(i!=num){
   String aux=newArray[i];
   newArray[i]=newArray[num];
   newArray[num]=aux;
}

edited Oct 13 '12 at 00:10

amit

175,853
27
231
333

answered Oct 12 '12 at 23:30

dan

13,132
3
38
49

No. (1) The algorithm will not return a permutation - it might contain duplicates. (2) There is no point in `aux` at this point, `newArray[i] == null`, so you are basically manipulating the original and putting `null`s in it (which might later flow to `newArray` in later permutations). Also, if you are thinking about a swap in the same array, then this solution is biased, since the random number must be selected in range `[0,i]` to get a uniformly distributed permutation. – amit Oct 12 '12 at 23:47
Thanks @amid, you were partially right. I was not creating duplicates, because I assumed that I was working on the original array. I updated my answer. Also nextInt is generating uniformly distributed values so he will get a correct permutation. – dan Oct 12 '12 at 23:57
Each int will be uniformly distributed, but the permutation itself won't be.(some solutions are more likely then others, this is not a desired feature) [This thread](http://stackoverflow.com/q/5131341/572670) discusses this issue. (It is a bit complex issue I admit, but it is an important one). Moreover - the solution still does not work - (last line is still `names` rather then `newArray`, and you need to fill `newArray` before starting, otherwise - it is just bunch of `null`s moving around) – amit Oct 13 '12 at 00:02
@amid Producing permutations like this it will not produce uniform distributed permutations, but the permutation is still valid. And he needs only one permutation. My answer was ment only to help him figure what was the issue in his code. Anyway, thanks I learned something new. – dan Oct 13 '12 at 00:09

score 0 · Answer 4 · answered Oct 12 '12 at 23:14

0

public String[] shuffle(String[] ss) {
  List<String> list = Collections.shuffle(Arrays.asList(ss));
  return list.toArray(new String[ss.length]);
}

answered Oct 12 '12 at 23:14

maerics

151,642
46
269
291

Given a String array, how to create a second array which is a rearrangement of the original?

4 Answers4