Deterministic shuffle in Objective C

Question

This code in Java is the implementation of Knuth's shuffle, but a deterministic one, controllable by the seed to the random number generator.

public String shuffleString(String data, long shuffleSeed) {
    if(shuffleSeed!=0) {
        Random rnd = new Random(shuffleSeed);
        StringBuilder sb = new StringBuilder(data);
        int n = data.length();
        while(n>1) {
            int k = rnd.nextInt(n--);
            char t = sb.charAt(n);
            sb.setCharAt(n, sb.charAt(k));
            sb.setCharAt(k, t);
        }
        return sb.toString();
    }
    else {
        return data;
    }
}

How can I implement a deterministic shuffle in Objective C that outputs the same shuffle order given the same seed? I am using srandom(_shuffleSeed); and random()%(n--) knowing that arc4_random is better but that cannot be seeded.

- (NSString*) shuffleString:(NSString*) data withShuffleSeed:(int) shuffleSeed {
    if(shuffleSeed!=0) {
        srandom(_shuffleSeed);
        NSMutableString *result = [[NSMutableString alloc] initWithString:data];
        unsigned long n = data.length;
        while(n>1) {
            unsigned long k = random()%(n--);
            unichar t = [result characterAtIndex:n];
            NSRange r1 = {n,1};
            [result replaceCharactersInRange:r1 withString:[NSString stringWithFormat:@"%c", [result characterAtIndex:k]]];
            NSRange r2 = {k,1};
            [result replaceCharactersInRange:r2 withString:[NSString stringWithFormat:@"%c", t]];
        }
        return result;
    }
    else {
        return data;
    }
}

Currently, the two shuffle methods do not generate the same result for the same input parameters. I am sure I am missing something!

Answer 1

There are many pseudo-random number generating algorithms that use a seed. You can't assume that the one in the Java standard library uses exactly the same algorithm as srandom/random in Objective C.

The Java random generator uses:

The class uses a 48-bit seed, which is modified using a linear congruential formula. (See Donald Knuth, The Art of Computer Programming, Volume 3, Section 3.2.1.)

It doesn't make any more guarantees, although it is never changed for backward compatibility reasons.

Your options are:

• Take the Java source and convert it to Objective-C (or hope that somebody else has done this before). Note that the Java source is licensed under the GPL, or a restrictive Oracle license. If you take the version under the GPL license, that has an impact on the license that you can use for your own code.
• Search for the source of the random generator in Objective-C and convert that to Java. (Which may also have license restrictions, and the source may not be available). Or maybe the algorithm is more properly specified so you can implement it in Java solely from the documentation.
• Find another random generator that has a Java and an Object-C implementation that give identical results (or write one)