Детерминированное перемешивание в Objective C

Этот код на Java является реализацией перетасовки Кнута, но детерминированной, управляемой семенем для генератора случайных чисел.

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;
    }
}

Как я могу реализовать детерминированное перемешивание в Objective C, которое выводит тот же порядок перемешивания при одном и том же начальном числе? Я использую srandom(_shuffleSeed); и random()%(n--) зная, что arc4_random лучше, но это не может быть заполнено.

- (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;
    }
}

В настоящее время два метода перемешивания не дают одинаковых результатов для одних и тех же входных параметров. Я уверен, что я что-то упускаю!


person xtremebytes    schedule 28.06.2015    source источник
comment
Изучив это немного подробнее, использование блочного шифра AES в режиме CTR для генерации случайных чисел, кажется, согласуется с рекомендациями NIST SP800-90A по детерминированным генераторам случайных битов (DRBG). Поскольку реализация AES согласована на разных платформах, детерминированный генератор случайных чисел также должен быть последовательным, но я еще не тестировал! С моей стороны было наивно предполагать, что rand(), random() в Objective C будут совместимы с java.util.Random.   -  person xtremebytes    schedule 29.06.2015


Ответы (1)


Существует множество алгоритмов генерации псевдослучайных чисел, использующих начальное число. Вы не можете предположить, что в стандартной библиотеке Java используется точно такой же алгоритм, как srandom/random в Objective C.

Генератор случайных чисел Java использует:

Класс использует 48-битное начальное число, которое модифицируется с помощью линейной конгруэнтной формулы. (См. Дональд Кнут, Искусство компьютерного программирования, том 3, раздел 3.2.1.)

Он не дает больше никаких гарантий, хотя никогда не изменяется по соображениям обратной совместимости.

Ваши варианты:

  • Возьмите исходный код Java и преобразуйте его в Objective-C (или надеюсь, что кто-то еще сделал это раньше). Обратите внимание, что исходный код Java находится под лицензией GPL или ограничительной лицензией Oracle. Если вы берете версию под лицензией GPL, это влияет на лицензию, которую вы можете использовать для своего собственного кода.
  • Найдите исходный код генератора случайных чисел в Objective-C и преобразуйте его в Java. (Кроме того, могут быть лицензионные ограничения, а исходник может быть недоступен). Или, может быть, алгоритм более точно определен, поэтому вы можете реализовать его на Java исключительно из документации.
  • Найдите другой генератор случайных чисел с реализацией Java и Object-C, которые дают идентичные результаты (или напишите его)
person Erwin Bolwidt    schedule 28.06.2015
comment
Спасибо. Я бы согласился с вашим последним предложением. Вариантом может быть Mersenne Twister. - person xtremebytes; 28.06.2015
comment
На самом деле перенос кода Java на Objective C тоже неплохая идея для той цели, для которой мне нужен этот генератор случайных чисел. Я знаю, что генераторы класса PCG лучше. - person xtremebytes; 28.06.2015