Dictionary to map an alphabet -- with unique keys & values

Question

I need to create a Dictionary that expresses a mapping between each char in an alphabet and another char in that alphabet, where both the key and value are unique -- like a very simple cipher that expresses how to code/decode a message. There can be no duplicate keys or values.

Does anyone see what is wrong with this code? It is still producing duplicate values in the mapping despite the fact that on each iteration the pool of available characters decreases for each value already used.

        string source_alphabet = _alphabet; //ie "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
        string target_alphabet = _alphabet;

        Dictionary<char, char> _map = new Dictionary<char, char>();

        for (int i = 0; i < source_alphabet.Length; i++)
        {
            int random = _random.Next(target_alphabet.Length - 1); //select a random index

            char _output = target_alphabet[random]  //get the char at the random index

            _map.Add(source_alphabet[i], _output); //add to the dictionary

            target_alphabet = target_alphabet.Replace(_output.ToString(), string.Empty); 
            // remove the char we just added from the remaining alphabet
        }

Thanks.

this type of code does not guarantee that `random` is always different from `i` - thus duplicates can (and usually will) happen... — Yahia, Sep 14 '11 at 17:27
That shouldn't matter because random doesn't need to be different from i. A character that has already been added as a value to the dictionary shouldn't even be in the available pool of chars to choose from. If by chance A ends up mapping to A that's fine. Its just that there can't be any duplicate values in the dictionary. — Sean Thoman, Sep 14 '11 at 17:31
Delete the char from the target_alphabet every time after random index has been generated. — mishau, Sep 14 '11 at 17:32

score 1 · Accepted Answer · edited May 23 '17 at 10:24

I would consider performing a simple Fisher Yates shuffle over one or both sequences of the alphabet, then you can simply iterate over the output and put together your mapper.

Pseudocode

Shuffle(sequence1)
Shuffle(sequence2)

for index 0 to 25
    dictionary add sequence1[index], sequence2[index]

When you try to select a random value each time, then there is a high probability that you will get a collision and therefore have a non-unique value selected. The answer is usually to shuffle, then select in order.

Yahia · Answer 2 · 2011-09-14T17:43:33.667

1

"a quick fix" though not optimal would be (if mapping A to A is NOT allowed)

 int random = _random.Next(target_alphabet.Length - 1);
 while ( source_alphabet[i] == target_alphabet[random] ) {random = _random.Next(target_alphabet.Length - 1);};

if mapping A to A is allowed then ignore the above change... BUT at least change the last line to

target_alphabet = target_alphabet.Remove ( random, 1 );

edited Sep 14 '11 at 17:43

answered Sep 14 '11 at 17:30

Yahia

69,653
9
115
144

Not sure why but I still get duplicates, whether I use .Replace() or .Remove() or the Array.FindAll() method that mishau posted. I think there maybe something else going on b/c this should work. – Sean Thoman Sep 14 '11 at 17:51
Then there must be something in the code not shown... is this multi-threaded ? any static variables ? any "duplicate" variable names which could cause some issues ? – Yahia Sep 14 '11 at 17:54

score 0 · Answer 3 · answered Sep 14 '11 at 17:30

0

I guess you could add another "for" loop on the target_alphabet inside the existing "for" loop and check for the characters not be same with a small "if" condition and continue the inner loop if same or break if not.

answered Sep 14 '11 at 17:30

Praveen

1,449
16
25

mishau · Answer 4 · 2011-09-14T17:49:57.587

This works.

 for (int i = 0; i < source_alphabet.Length; i++)
    {
        int random = _random.Next(target_alphabet.Length - 1); //select a random index

        char _output = target_alphabet[random];  //get the char at the random index


        _map.Add(source_alphabet[i], _output); //add to the dictionary

        // remove the char we just added from the remaining alphabet
        target_alphabet = target_alphabet.Remove(random, 1);


    }

Dictionary to map an alphabet -- with unique keys & values

4 Answers4