我有一个大小为P
的数组A =[a1,a2,a3,...aP]
。 我需要从数组A
中随机选出q
个元素。
我计划使用一个循环进行q
次迭代,在每次迭代中随机选择一个A中的元素。 但是我该如何确保在每次迭代中选择的数字都不同?
我有一个大小为P
的数组A =[a1,a2,a3,...aP]
。 我需要从数组A
中随机选出q
个元素。
我计划使用一个循环进行q
次迭代,在每次迭代中随机选择一个A中的元素。 但是我该如何确保在每次迭代中选择的数字都不同?
# Shuffled list of indexes into @deck
my @shuffled_indexes = shuffle(0..$#deck);
# Get just N of them.
my @pick_indexes = @shuffled_indexes[ 0 .. $num_picks - 1 ];
# Pick cards from @deck
my @picks = @deck[ @pick_indexes ];
1/$position
的机会,它是$picks_left / $position
。每次成功选择后,你都要减少$picks_left。你从高位置到低位置工作。与之前不同,你不会覆盖。my $picks_left = $picks;
my $num_left = @$deck;
my @picks;
my $idx = 0;
while($picks_left > 0 ) { # when we have all our picks, stop
# random number from 0..$num_left-1
my $rand = int(rand($num_left));
# pick successful
if( $rand < $picks_left ) {
push @picks, $deck->[$idx];
$picks_left--;
}
$num_left--;
$idx++;
}
1. (2 picks, 4 items): 2/4 = 1/2
很简单。下一个元素有一半的概率已经被选中,这种情况下它的概率是1/3。否则它的概率是2/3。进行计算...
2. (1 or 2 picks, 3 items): (1/3 * 1/2) + (2/3 * 1/2) = 3/6 = 1/2
3. (0, 1 or 2 picks, 2 items): (0/2 * 1/4) + (1/2 * 2/4) + (2/2 * 1/4) = 2/8 + 1/4 = 1/2
4. (0 or 1 pick, 1 items): (0/1 * 2/4) + (1/1 * 2/4) = 1/2
虽然不是严格的证明,但这足以让您相信它是有效的。
List::Gen
的设计目标与 perl5i
不同,包括能够处理无限范围的数字。它不会复制和洗牌整个数组以选择元素,这是完全错误的。如果这样做,那么从无限源(如 <1..*>->pick(5)->say
)中进行选择就不能工作(但它确实可以)。 - Eric Stromperl5i
版本的 pick
是排序的?(至少在你请求所有元素时是这样的,它会回退到 List::Util::shuffle
并正常工作)希望在下一个版本发布之前能够解决这个问题。 - Eric Strommy $pick = $self->shuffle->take($n);
,并继续认为它必须在取 $n
之前对 $self
进行洗牌。你的洗牌算法只能洗牌前 $n$ 个元素?这很棒。我将完全删除 List::Gen 的引用,它并不是非常相关。另外,感谢指出排序问题。虽然我没有考虑过,但我理解你的观点。 - SchwernFrom perldoc perlfaq4
:
How do I shuffle an array randomly?
If you either have Perl 5.8.0 or later installed, or if you have Scalar-List-Utils 1.03 or later installed, you can say:
use List::Util 'shuffle'; @shuffled = shuffle(@list);
If not, you can use a Fisher-Yates shuffle.
sub fisher_yates_shuffle { my $deck = shift; # $deck is a reference to an array return unless @$deck; # must not be empty! my $i = @$deck; while (--$i) { my $j = int rand ($i+1); @$deck[$i,$j] = @$deck[$j,$i]; } } # shuffle my mpeg collection # my @mpeg = <audio/*/*.mp3>; fisher_yates_shuffle( \@mpeg ); # randomize @mpeg in place print @mpeg;
List::Gen
:my $gen = <1..10>;
print "$_\n" for $gen->pick(5); # prints five random numbers
->pick
的重点在于它是惰性计算的。这使得从非常大、变化、难以访问或无限数据源中随机选择元素成为可能。这必然会带来性能上的成本。当以列表上下文调用->pick($n)
时,我将考虑使用急切算法,因为这种用法需要一次性计算所有元素,可以更加优化。 - Eric Strom# randomly permutate @array in place
sub fisher_yates_shuffle
{
my $array = shift;
my $i = @$array;
while ( --$i )
{
my $j = int rand( $i+1 );
@$array[$i,$j] = @$array[$j,$i];
}
}
fisher_yates_shuffle( \@array ); # permutes @array in place
q
个随机元素后停止洗牌来优化此操作。(按照现在的写法,你需要选择最后的q个元素。)List::Util::shuffle
,则无法使用我提到的优化;如果P非常大而q要小得多,则可能会成为一个因素。 - Ted Hopp你可以构造一个大小为P的布尔类型二维数组,并将选中的数字存储为true。当选择数字时,请检查第二个表格;如果是“true”,则必须选择下一个。