Как эффективно выбрать несколько уникальных случайных чисел от 1 до 50, исключая x?

Question

У меня есть 2 числа от 0 до 49. Давайте назовем их x и y. Теперь я хочу получить пару других чисел, которые не являются x или y, но также находятся между 0 и 49 (я использую Цель C, но я думаю, что это скорее вопрос общей теории?).

Метод, о котором я подумал:

 int a;
 int b;
 int c;

 do {
  a = arc4random() % 49;
 } while ((a == x) || (a == y));

 do {
  b = arc4random() % 49;
 } while ((b == x) || (b == y) || (b == a));

 do {
  c = arc4random() % 49;
 } while ((c == x) || (c == y) || (c == a) || (c == b));

Но мне это кажется немного плохим, я не знаю, я просто пытаюсь научиться быть лучшим программистом, какой самый элегантный способ сделать это для лучших практик?

Answer 1

Вы можете использовать то, что называется Fisher-Yates shuffle Это эффективный алгоритм для создания случайно упорядоченного списка значений из некоторого набора. Сначала вы должны исключить N из списка значений, из которых можно получить случайные значения, а затем выполнить случайное перемешивание.

Answer 2

Вам следует перетасовать массив чисел (в вашем случае значений [0, ..., 49]; вы также можете исключить ваши x и y из этого массива, если вы уже знаете их значения), затем возьмите первые N значений (сколько бы вы ни искали) из перемешанного массива. Таким образом, все числа случайным образом находятся в этом диапазоне и не «видны раньше».

Answer 3

Я бы сделал что-то более похожее на:

NSMutableSet * invalidNumbers = [NSMutableSet set];
[invalidNumbers addObject:[NSNumber numberWithInt:x]];
[invalidNumbers addObject:[NSNumber numberWithInt:y]];

int nextRandom = -1;
do {
  if (nextRandom >= 0) {
    [invalidNumbers addObject:[NSNumber numberWithInt:nextRandome]];
  }
  nextRandom = arc4random() % 49;
} while ([invalidNumbers containsObject:[NSNumber numberWithInt:nextRandom]]);

Answer 4

Сначала создайте набор действительных чисел:

// Create a set of all the possible numbers
NSRange range = { 0, 50 };// Assuming you meant [0, 49], not [0, 49)
NSMutableSet *numbers = [NSMutableSet set];
for (NSUInteger i = range.location; i < range.length; i++) {
    NSNumber *number = [NSNumber numberWithInt:i];
    [numbers addObject:number];
}

// Remove the numbers you already have
NSNumber *x = [NSNumber numberWithInt:(arc4random() % range.length)];
NSNumber *y = [NSNumber numberWithInt:(arc4random() % range.length)];
NSSet *invalidNumbers = [NSSet setWithObjects:x, y, nil];
[numbers minusSet:invalidNumbers];

Тогда, если вам не нужно, чтобы числа были гарантированно случайными, вы можете использовать -anyObject и -removeObject, чтобы вытащить пару других чисел. Если вам нужно, чтобы они были случайными, тогда следуйте ответу Л.Бушкина , но будьте осторожны, чтобы случайно не реализовать алгоритм Саттоло :

// Shuffle the valid numbers
NSArray *shuffledNumbers = [numbers allObjects];
NSUInteger n = [shuffledNumbers count];
while (n > 1) {
    NSUInteger j = arc4random() % n;
    n--;
    [shuffledNumbers exchangeObjectAtIndex:j withObjectAtIndex:n];
}

Answer 5

Вы можете добавить x, y и новый номер к структуре данных, которую вы можете использовать как set и сделать что-то вроде (в псевдокоде; структуре set нужно что-то вроде push для добавления значений и in для проверки членства):

number_of_randoms = 2;

set.push(x);
set.push(y);

for (i = 0; i<number_of_randoms; i++) {
  do {
    new_random = arc4random() % 49;
  } while !set.in(new_random);
  set.push(new_random);
}

Так что, если у objc есть что-то подходящее, это легко ... [ага, да, см. Пост Дэйва Делонга].

Этот алгоритм имеет смысл, если number_of_randoms намного меньше 49; если они сопоставимы, то вам следует воспользоваться одной из идей случайного (ака перестановка ).