How to shuffle characters in a string without using Collections.shuffle(...)?

Question

How do I shuffle the characters in a string (e.g. hello could be ehlol or lleoh or ...). I don't want to use the Collections.shuffle(...) method, is there anything simpler?

Answer 1

I dont know anything simpler. But you can use the Math.rand() functionality to generate a random number within the range of the character's length without replace and that would give you a shuffled output

public class Shuffle {
    public static void main(String[] args) {
        Shuffle s = new Shuffle();
        s.shuffle("hello");

    }
    public void shuffle(String input){
        List<Character> characters = new ArrayList<Character>();
        for(char c:input.toCharArray()){
            characters.add(c);
        }
        StringBuilder output = new StringBuilder(input.length());
        while(characters.size()!=0){
            int randPicker = (int)(Math.random()*characters.size());
            output.append(characters.remove(randPicker));
        }
        System.out.println(output.toString());
    }
}
/*
Sample outputs
hlleo
llheo
leohl
lleho
*/

Answer 2

Not great performance, but quite readable in my opinion:

public static String shuffleString(String string)
{
  List<String> letters = Arrays.asList(string.split(""));
  Collections.shuffle(letters);
  String shuffled = "";
  for (String letter : letters) {
    shuffled += letter;
  }
  return shuffled;
}

Answer 3

How about this:

public static String shuffle(String text) {
    char[] characters = text.toCharArray();
    for (int i = 0; i < characters.length; i++) {
        int randomIndex = (int)(Math.random() * characters.length);
        char temp = characters[i];
        characters[i] = characters[randomIndex];
        characters[randomIndex] = temp;
    }
    return new String(characters);
}

Answer 4

What an annoying problem. I finally ended up with this:

import java.util.Collections;
import com.google.common.primitives.Chars;
import org.apache.commons.lang3.StringUtils;

String shuffle(String s) {
    List<Character> chars = Chars.asList(s.toCharArray());
    Collections.shuffle(chars);
    return StringUtils.join(chars.stream().toArray());
}

Yes, two libraries :)

Answer 5

E.g.:

static String shuffle(String text){
    if (text.length()<=1)
        return text;

    int split=text.length()/2;

    String temp1=shuffle(text.substring(0,split));
    String temp2=shuffle(text.substring(split));

    if (Math.random() > 0.5) 
        return temp1 + temp2;
    else 
        return temp2 + temp1;
}    

Answer 6

class ShuffleString
{

    public static String shuffle(String s)
    {

        String shuffledString = ""; 

        while (s.length() != 0)
        {
            int index = (int) Math.floor(Math.random() * s.length());
            char c = s.charAt(index);
            s = s.substring(0,index)+s.substring(index+1);
            shuffledString += c;
        }

        return shuffledString;

    }

}


public class foo{
    static public void main(String[] args)
    {

        String test = "hallo";
        test = ShuffleString.shuffle(test);
        System.out.println(test);
    }
}

Output: ahlol

Answer 7

Here's code that requires neither recursion, nor converting to a Collection.

public static String shuffle(String string) {
    StringBuilder sb = new StringBuilder(string.length());
    double rnd;
    for (char c: string.toCharArray()) {
        rnd = Math.random();
        if (rnd < 0.34)
            sb.append(c);
        else if (rnd < 0.67)
            sb.insert(sb.length() / 2, c);
        else
            sb.insert(0, c);
    }       
    return sb.toString();
}

Answer 8

Not sure why you wouldn't want to use shuffle, unless it's for school. ;)

And if you're concerned with performance, you definitely can't use any solution that concatenates strings with "+".

Here's the most compact solution I could come up with:

public static String shuffle(String string) {
    if (StringUtils.isBlank(string) {
        return string;
    }

    final List<Character> randomChars = new ArrayList<>();
    CollectionUtils.addAll(randomChars, ArrayUtils.toObject(string.toCharArray()));
    Collections.shuffle(randomChars);
    return StringUtils.join(randomChars, "");
}

Answer 9

Without external libraries, for those who do not mind using Collections.shuffle():

static String shuffle(String string){

    List<Character> list = string.chars().mapToObj(c -> new Character((char) c))
                                         .collect(Collectors.toList());
    Collections.shuffle(list);
    StringBuilder sb = new StringBuilder();
    list.forEach(c -> sb.append(c));

    return sb.toString();
}

Answer 10

In Kotlin, you can do the following.

val helloCharArray = "hello".toCharArray()
helloCharArray.shuffle()
val shuffledHello = helloCharArray.concatToString()

Answer 11

You could iterate over all the characters, comparing each one with the next. Then if Math.rand() > 0.5 swap this character with the next, otherwise move on to the next character.

Answer 12

        String shuffled;
        do {
            shuffled = Stream.of(text.split("")).sorted((o1, o2) -> ThreadLocalRandom.current().nextInt(3) - 1).collect(Collectors.joining());
        }while(shuffled.equals(text));

Answer 13

If you still want to restore the original String later on, try something like this:

public static class ShuffledString
{
    private List<Integer> indices;
    private String string;

    public ShuffledString(List<Integer> indices, String string)
    {
        this.indices = indices;
        this.string = string;
    }

    public List<Integer> getIndices()
    {
        return indices;
    }

    public String getRegularString()
    {
        StringBuilder stringBuilder = new StringBuilder();

        for (int stringIndex = 0; stringIndex < indices.size(); stringIndex++)
        {
            int characterIndex = indices.indexOf(stringIndex);
            stringBuilder.append(string.charAt(characterIndex));
        }

        return stringBuilder.toString();
    }
}

public static ShuffledString shuffle(String input)
{
    List<Integer> indices = new ArrayList<>();

    StringBuilder output = new StringBuilder(input.length());
    while (indices.size() < input.length())
    {
        int randomIndex;

        while (indices.contains(randomIndex = (int) (Math.random() * input.length())))
        {

        }

        indices.add(randomIndex);
        output.append(input.charAt(randomIndex));
    }

    return new ShuffledString(indices, output.toString());
}

Answer 14

In Java 8+ this can be done using Collectors.shuffle(...) in three lines as follows:

1. Convert the String into a List of Characters
2. Shuffle the list
3. Convert the shuffled List of Characters back into a String

Code:

public static String shuffle(final String str) {
    List<Character> chars = str.chars().mapToObj(e->(char)e).collect(Collectors.toList());
    Collections.shuffle(chars);
    return chars.stream().map(e->e.toString()).collect(Collectors.joining());
}

Demo:

Rextester demo

Answer 15

Using commons-lang3:

import org.apache.commons.lang3.ArrayUtils;

String shuffle(String text) {
    char[] chars = text.toCharArray();
    ArrayUtils.shuffle(chars);
    return String.valueOf(chars);
}

Answer 16

One more short implementation using Stream API:

 String shuffle(String str) {       
    return new Random().ints(0, str.length()).distinct().limit(str.length()) // shuffle indexes
            .mapToObj(i->""+str.charAt(i)).collect(Collectors.joining());    // collect letters
 }

Answer 17

Some Strings may contain symbols consisting of multiple characters.

In order to get around this, you can convert the String to code points, shuffle the array and convert them back to a String.

public static String shuffle(String toShuffle){
    int[] codePoints = toShuffle.codePoints().toArray();
    shuffle(codePoints);
    return new String(codePoints, 0, codePoints.length);
}

Shuffling the array could be done like this or using any other method:

//code from https://stackoverflow.com/a/1520212/10871900
private static void shuffle(int[] ar)
  {
    // If running on Java 6 or older, use `new Random()` on RHS here
    Random rnd = ThreadLocalRandom.current();
    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;
    }
  }

As a less-performant alternative, you could use wrapper objects and shuffle the stream:

public static String shuffle(String toShuffle){
    int[] codePoints = toShuffle
        .codePoints()
        .boxed()
        .sorted((o1, o2) -> ThreadLocalRandom.current().nextInt(-1, 2) //https://stackoverflow.com/a/55352119/10871900 
        .mapToInt(i->i)
        .toArray();
    return new String(codePoints, 0, codePoints.length);
}