如何从1到50有效地选择几个唯一的随机数，不包括x？

问题描述：

我有2个数字，介于0和49之间。我们称它们为x和y。现在我想得到一些不是x或y的其他数字，但也在0和49之间（我正在使用Objective C，但这更多的是我认为的一般理论问题）。如何从1到50有效地选择几个唯一的随机数，不包括x？

方法我认为是：

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

但它似乎有种对我不好，我不知道，我只是想学着做一个更好的程序员，这将是最优雅如何做到这一点的最佳做法？

答

你可以使用一种叫做Fisher-Yates shuffle的东西。这是一个有效的算法，用于从某个集合中生成一个随机排序的值列表。您首先要从要获取随机值的值列表中排除N，然后执行shuffle。

伟大的成果和易于实施。人们还能要求什么？ – 2010-03-23 18:24:34

谢谢，是的，我会试试这个......我已经在其他地方使用了Fisher-Yates shuffle，我刚刚意识到..我没有想到它会因为某种原因而被使用。我觉得我的方法至少应该产生随机洗牌，但结果是说不，所以我会尝试。谢谢！ – Cocorico 2010-03-23 20:20:43

我在回答中实际上没有提到Fisher-Yates有一个很好的理由：我想鼓励读者使用他们的平台提供的shuffle函数，而不是手动实现洗牌。几乎所有标准的in-place数组混排实现（例如，C++中的std :: random_shuffle，Java中的Collections.shuffle等等）都使用Fisher-Yates。 – 2010-03-23 23:44:57

答

你应该在你的案例中对数组（数值[0，...，49]）进行混洗;如果你已经知道它们的值，你也可以排除你的x和y），然后抓住第一个N值（不管你正在寻找多少）从混洗阵列。这样，所有数字都是该范围内的随机数，而不是“之前见过”。

但是从最初的阵列排除x和y。 – 2010-03-23 18:06:38

@invariant：是的，我错过了阅读这个问题。 +1 – 2010-03-23 18:07:04

是的，我打算使用Fisher-Yates shuffle来做这件事......然而让我问你......我的方法是否会产生不正确的随机性？看起来你是这么说的，而且这很奇怪，因为我觉得它应该是逻辑上的，但它似乎不是？ – Cocorico 2010-03-23 20:21:37

答

我会做线沿线的东西更多：您可以添加x，y和新号码的数据结构，你可以作为一个set使用，这样做

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]]);

答

（伪-code;该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，则该算法有意义;如果它们具有可比性，那么你应该对其中一个shuffle（又名排列）的想法。

答

首先，制定一套有效的数字：

// 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拉了几个其他的数字。如果你需要他们是随机的，然后按照LBushkin's answer，但要小心不要意外实现Sattolo's algorithm：

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

如何从1到50有效地选择几个唯一的随机数，不包括x？

相关推荐