samedi 27 juin 2015

Deterministic shuffle in Objective C

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!

Aucun commentaire:

Enregistrer un commentaire