KEEP K.I.S.S.

tk's blog

Ruby 中的 Array Shuffle 算法

tk posted @ May 28, 2012 10:54:23 AM in C with tags shuffle 洗牌算法 , 2412 阅读

其实就是数组的洗牌算法,洗牌算法主要是生成一组互不相同的伪随机数列,可用于随机排序等等。

如果单纯依赖 C 库的 rand 去生成随机数来做的话,容易发生碰撞,尤其在需要生成的数列个数比较大的情况下。

Ruby 的 Array 有一个 shuffle 的方法,用于生成随机排序的元素新数组:

(1..12).to_a.shuffle 

=> [12, 9, 6, 5, 3, 1, 8, 4, 11, 7, 10, 2]

其实现如下:

static VALUE
rb_ary_shuffle_bang(VALUE ary)
{
    VALUE *ptr;
    long i = RARRAY_LEN(ary);
    rb_ary_modify(ary);
    ptr = RARRAY_PTR(ary);
    while (i) {
        long j = (long)(rb_genrand_real()*i);
        VALUE tmp = ptr[--i];
        ptr[i] = ptr[j];
        ptr[j] = tmp;
    }
    return ary;
} 

很简单,用 C 写个示例如下:

#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define ARRAY_SIZE(a)  ((sizeof(a) / sizeof(*(a))))

static void
shuffle(int *arr, size_t len)
{
    int i;
    i = len;
    while (i) {
        size_t j = (size_t)(rand() % i);
        i--;
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;       
    }
}

int main(int argc, char *argv[])
{
    int array[] = {
        1, 2, 3, 4, 5, 6,
        7, 8, 9, 10, 11, 12
    };
    srand(time(NULL));
    shuffle(array, ARRAY_SIZE(array));
    for (int i = 0; i < ARRAY_SIZE(array); i++) {
        printf("%d, ", array[i]);
    }
    printf("\n");
    return 0;
}
  • 无匹配
  • 无匹配
CBSE 7th Class Model 说:
Sep 19, 2022 05:24:12 PM

For the upper primary school class 7th standard board pupils enrolled in public or private schools nationwide, the Central Board of Secondary Education has issued sample model papers with study guides and prior years' old test previous papers in PDF format. CBSE 7th Class Model Paper For evaluation-1, evaluation-2, evaluation-3, and evaluation-4 exams held under Term-1, Term-2, Term-3, and Term-4 exams of Paper-1 & Paper-2 or Part-A & Part-B Section for all subjects of the course for all Hindi medium, English medium, Urdu medium, and another regional language student, the board has designed those CBSE 7th Class Model Paper 2023.

things to do 说:
Jun 05, 2023 05:36:27 PM

What are the best <a href="https://www.thingstodo-near.me" title="things to do near me">things to do near me</a> in Quebec, - one of the most famous cities of Canada?


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter