How to get rid of letters randomly generated after being used?

Question

I'm currently writing a program that requires me to generate random letters from the alphabet and assign them to other letters. (It's an encryption program). The problem is, once I've generated the first few letters, some are generated again.

For example, I want to let a = c (randomly generated letter) But now that c is used, I don't want the other 25 letters to be equal to c. So I don't want b = c I don't know how to go about this as it seems easy enough but I can't manage to do it.

Here is that bit of my code.

for (int i = 0; i<26; i++)
        {
            Random r = new Random();
            cipherArray[i] =(char)(cipherText.charAt(r.nextInt(cipherText.length())));
        }
            return cipherArray;

Any help is appreciated, thank you.

Store the generated letters in a `Map` and check if the key exists. If it does, generate another until you find one that doesn't. Another way to do it would be to put all 26 letters into an array and shuffle it. All the letters in the shuffled array will be unique and you can just assign them in that order to each letter. — Ryan J, Dec 30 '14 at 21:13
Keep track of the ones you've already generated and have an if statement that generates a new one if it's already taken — reggaeguitar, Dec 30 '14 at 21:14

score 6 · Answer 1 · answered Dec 30 '14 at 21:17

6

You could try the following.

public static void main(final String[] args) {
    List<Character> chars = new ArrayList<>(26);
    for (char c = 'a'; c <= 'z'; c++) {
        chars.add(c);
    }

    Collections.shuffle(chars);
}

It creates a List of the characters 'a' to 'z' and shuffles it.

answered Dec 30 '14 at 21:17

Markus Patt

467
3
11

Hey, sorry I'm only in first year computer science but what exactly does "List chars = new ArrayList<>(26);" do? – Herofire Dec 30 '14 at 21:22
It creates a new ArrayList (a Collection class, which uses an array internally) and stores it in the variable "chars", which is of type "List". List is an interface, which is implemented by ArrayList. The "" behind the "List" is a generic declaration. The compiler will check, that only Characters are added to the list. The argument "26" to the Constructor tells the list to create an ArrayList that will be able to store 26 entries. Of course it is still able to resize itself. – Markus Patt Dec 30 '14 at 21:25
You can do this without a loop by just explicitly creating the array and using `Arrays.asList` to pass it to `Collections.shuffle`. `List chars = Arrays.asList('a','b','c',...,'z'); Collections.shuffle(chars);` – Ryan J Dec 30 '14 at 21:30
1

But programmers are lazy. ;) And creating a for loop is faster that explicitly writing the array. (At least in an IDE) – Markus Patt Dec 30 '14 at 21:32
@MPirious Nothing wrong with using a loop, but for less-trivial examples, this provides another method for which avoiding loops can be used. – Ryan J Dec 30 '14 at 21:34
Will I then still use the random generator to generate random numbers from the list? – Herofire Dec 30 '14 at 22:34
No, `chars` is randomized. `Collections.shuffle` uses a `Random` instance internally. If you like - or need to - you can pass an instance of `Random` as second parameter to `shuffle`. – Markus Patt Dec 30 '14 at 22:46
Hey sorry, last question I promise. How do I call on the list like an array? Like I can't do char[2] to call on the third element of the list like an array, so how would I do it? Really appreciate the help btw, so grateful. – Herofire Dec 30 '14 at 23:57
Read the JavaDoc: http://docs.oracle.com/javase/8/docs/api/java/util/List.html#get-int- – Markus Patt Dec 30 '14 at 23:59

score 0 · Answer 2 · edited May 23 '17 at 12:05

The fastest solution is to use Fisher–Yates shuffle; java implementation exists in this SO link.

However, although it is considered a really fast and unbiased algorithm, in your case, the main problem when using Fisher–Yates shuffle (and apparently Collections.shuffle that uses it), is that it doesn't guarantee all letters will change their initial index. You may end up having a couple of letters unchanged, which sometimes is not good (imagine some of your vowels do not change; then it may be easy to decrypt).

If the aforementioned issue is a requirement, then there are many solutions to guarantee that each character has indeed changed. I only enlist some of them.

a) Best approach, use Sattolo's algorithm.

 public static void SattoloShuffle(char[] a) {
    int n = a.length;
    Random random = new Random();
    int r;
    char temp;

    for (int i = n; i > 1; i--) {
        // choose index uniformly in [0, i-1)
        r = random.nextInt(i-1);
        temp = a[r];
        a[r] = a[i-1];
        a[i-1] = temp;
    }
}

b) A greedy approach would be to iteratively run shuffle until you have all your chars changed from their initial position.

c) You could also use an array with your characters from a-z and then create your desired shuffled array by randomly picking characters ensuring that the same character is not changed with itself e.g.:

    char[] initialDictionary = new char[] { 'a', 'b', 'c', 'd', 'e', 'f',
            'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r',
            's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
    int n = initialDictionary.length;
    char[] encryptedDictionary = new char[n];

    int i = 0;
    int randomIndex;
    Random random = new Random();
    while (i < n) {
        randomIndex = random.nextInt(n);
        if (randomIndex != i && initialDictionary[randomIndex] != '0') {
            encryptedDictionary[i++] = initialDictionary[randomIndex];
            initialDictionary[randomIndex] = '0'; // use 0 to flag chars already used
        }
    }

d) In the same sense with the previous solution, you can use Lists but after selecting a valid character, remove this char from the initial list.

How to get rid of letters randomly generated after being used?

2 Answers2