Efficient way to generate a random alphabet string?

Question

I want a string of all the characters of the alphabet randomized. Right now, I create a mutable array of the 26 characters, shuffle them with the exchangeObjectAtIndex: method and then add each character to a string that I return.

There has to be a better way to do this. Here is my code:

- (NSString *)shuffledAlphabet {
    NSMutableArray * shuffledAlphabet = [NSMutableArray arrayWithArray:@[@"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"]];

    for (NSUInteger i = 0; i < [shuffledAlphabet count]; ++i) {
        // Select a random element between i and end of array to swap with.
        int nElements = [shuffledAlphabet count] - i;
        int n = (random() % nElements) + i;
        [shuffledAlphabet exchangeObjectAtIndex:i withObjectAtIndex:n];
    }

    NSString *string = [[NSString alloc] init];
    for (NSString *letter in shuffledAlphabet) {
        string = [NSString stringWithFormat:@"%@%@",string,letter];
    }

    return string;
}

Do you want a random string of letters, or do you want a random permutation of the letters of the alphabet (i.e. a "random sequence without repetition")? - The title of your question suggests the first, and your code does the latter. — Martin R, Jan 15 '13 at 15:37
I'm perfectly happy with repetition of letters or simply a shuffled alphabet. The shuffled alphabet was the first thing that came to mind when I was writing out the method. — Joshua, Jan 15 '13 at 15:45
Come on, decide what you want. Two of them are really different. — erkanyildiz, Jan 15 '13 at 15:48
You're right. I need to make it clear: I'd like a permutation of the letters of the alphabet. A 26 character string with random order and no repeating letters. — Joshua, Jan 15 '13 at 17:05

score 7 · Accepted Answer · answered Jan 15 '13 at 15:59

Here's an efficient Fisher-Yates shuffle, adapted to your use case:

- (NSString *)shuffledAlphabet {
    NSString *alphabet = @"ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    // Get the characters into a C array for efficient shuffling
    NSUInteger numberOfCharacters = [alphabet length];
    unichar *characters = calloc(numberOfCharacters, sizeof(unichar));
    [alphabet getCharacters:characters range:NSMakeRange(0, numberOfCharacters)];

    // Perform a Fisher-Yates shuffle
    for (NSUInteger i = 0; i < numberOfCharacters; ++i) {
        NSUInteger j = (arc4random_uniform(numberOfCharacters - i) + i);
        unichar c = characters[i];
        characters[i] = characters[j];
        characters[j] = c;
    }

    // Turn the result back into a string
    NSString *result = [NSString stringWithCharacters:characters length:numberOfCharacters];
    free(characters);
    return result;
}

score 2 · Answer 2 · answered Jan 15 '13 at 16:03

This is the more efficient way to perform a correctly shuffled alphabet generation.

- (NSString *)shuffledAlphabet
{
    const NSUInteger length = 'Z' - 'A' + 1;
    unichar alphabet[length];
    alphabet[0] = 'A';

    for ( NSUInteger i = 1; i < length; i++ )
    {
        NSUInteger j = arc4random_uniform((uint32_t)i + 1);
        alphabet[i] = alphabet[j];
        alphabet[j] = 'A' + i;
    }
    return [NSString stringWithCharacters:alphabet length:length];
}

It uses the "inside-out" version of the Fischer Yates shuffle and avoids modula bias by generating the pseudorandom numbers with arc4random_uniform. Also, it requires a single allocation as all the permutations are performed in a temporary buffer.

There should be links in this answer. I don't understand why they're not displayed. — Nicolas Bachschmidt, Jan 15 '13 at 16:18

score 1 · Answer 3 · edited May 23 '17 at 12:04

1

Generating random numbers in Objective-C does this help? *generate random number *divide by 26 and take reminder *index array[reminder]

edited May 23 '17 at 12:04

Community

1
1

answered Jan 15 '13 at 15:33

Satish

713
1
5
18

omz · Answer 4 · 2013-01-15T16:28:07.050

0

You could pick random elements from the (remaining) alphabet while you build your string instead of shuffling it first:

NSMutableArray *alphabet = [NSMutableArray arrayWithObjects:@"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", nil];
NSMutableString *result = [NSMutableString string];
NSUInteger numberOfLetters = alphabet.count;
for (NSUInteger i = 0; i < numberOfLetters; i++) {
    int n = arc4random() % alphabet.count;
    [result appendString:[alphabet objectAtIndex:n]];
    [alphabet removeObjectAtIndex:n];
}
NSLog(@"%@", result);

This makes the code a bit shorter. Note also that using NSMutableString is more efficient than creating a new NSString each time a letter is added.

edited Jan 15 '13 at 16:28

answered Jan 15 '13 at 15:39

omz

53,243
5
129
141

1

Using a sort algorithm for shuffling an array is not a good idea. First the different combinations don't have the same probability. Secondly, its asymptotic complexity is `O(log(n)*n)` whereas an efficient shuffle algorithm has an complexity of `O(n)`. You should have a look at the responses to [this question](http://stackoverflow.com/questions/790083/does-qsort-demand-consistent-comparisons-or-can-i-use-it-for-shuffling). – Nicolas Bachschmidt Jan 15 '13 at 16:14
1

Thanks for that link. I've removed the alternative version. – omz Jan 15 '13 at 16:28

Efficient way to generate a random alphabet string?

4 Answers4

Linked