java: shuffle 2d array according to given char array

Question

beginner question here:

I have a given word and should assign numbers to every letter by order of appearance.
Then shuffle the word and print the numbers according to appearance of the letters

• visualization:

word : CODEWORD
sort alphabetically: CDDEOORW

assign numbers:

C D D E O O R W    
0 1 2 3 4 5 6 7

"shuffle" letters according to original word:

C O D E W O R D
0 4 1 3 7 5 6 2

(I don't mind storing the characters in integer format)

• implementation

package hallo;
import java.util.Arrays;

public class test {

    public static void shuffle(char[] k)
    {
        char[] m = k.clone();
        Arrays.sort(m);

        //array where I store my numbers
        int[] numbers = new int[k.length];

        //2d array to assign numbers to letters
        int[][] per = new int[2][m.length];
        // 2d array to store the "shuffled" word
        int[][] per2 = new int[2][k.length];

        //fill numbers array with integers to ascii order
        for(int i=0;i<m.length;i++){
            numbers[i] = i;
            // 0 1 2 3 4 5 6 7
        }

        // fill first 2d array
        for (int i = 0; i < m.length; i++) {
            per[0][i] = m[i];
            per[1][i] = numbers[i];
        }

        // now to fill the second array with "shuffled" word
        for (int j = 0; j < k.length; j++) {
            for (int i = 0; i < k.length; i++) { // k and m length is the same
                if (per[0][i] == k[j]) {
                    per2[0][i] = per[0][i];
                    per2[1][i] = per[1][i];
                    //fill the numbers array with the new order
                    numbers[j] = per[1][i];
                }
            }
        }
        System.out.println("numbers: ->"+Arrays.toString(numbers));
    }

    public static void main(String[] args){
        char[] word = {'C','O', 'D', 'E', 'W', 'O', 'R', 'D'};
        shuffle(word);
        // expected :  0 4 1 3 7 5 6 2
    }

}

the expected output is 0 4 1 3 7 5 6 2 as shown above in the visualization.
but actual output is 0 5 2 3 7 5 6 2

it seems that the characters occurring more than once like O and D cause this problem.

I have tried breaking the for loop as soon as a letter is found or storing numbers of a letter occurrence in a separate array but nothing worked this far. Any help or correction would be greatly appreciated.

Answer 1

The loop which populates numbers[j] does not check if the position has already been added. As a result, the same index is added to the result for every occurrence of a character. You can use a boolean array to mark the indexes that have already been used. And check the characters in the sorted array m only if the index is not used.

public static void shuffle (char[] k) {
    
    char[] m = k.clone();
    Arrays.sort(m);
    
    boolean[] used = new boolean[k.length];
    int[] numbers = new int[k.length];
    
    for(int i=0;i<k.length;i++) {
        for (int j=0; j<m.length; j++) {
            if (k[i] == m[j] && !used[j]) {
                numbers[i] = j;
                used[j] = true;
                break;
            }
            
        }
    }
    
    System.out.println("numbers: ->"+Arrays.toString(numbers));
}

Answer 2

The following code gives me your expected output when using your sample input.

package hallo;

import java.util.Arrays;

public class test {
    private static void shuffle(char[] k) {
        char[] m = k.clone();
        Arrays.sort(m);
        int[] numbers = new int[m.length];
        Arrays.fill(numbers, -1);
        for (int i = 0; i < numbers.length; i++) {
            for (int j = 0; j < k.length; j++) {
                if (k[j] == m[i]  &&  numbers[j] < 0) {
                    numbers[j] = i;
                    break;
                }
            }
        }
        System.out.println(Arrays.toString(numbers));
    }

    public static void main(String[] args) {
        char[] word = {'C', 'O', 'D', 'E', 'W', 'O', 'R', 'D'};
        shuffle(word);
    }
}