c - C 中的洗牌函数

Question

洗牌函数定义为

Shuffle( A[n-1],A[n-2].....A[1],A[0]) = A[n-2]A[n-3]......A[1],A[0],A[n-1]

其中 A[i] 中的 i 表示数组中索引的二进制表示形式中的第 I 位。

例如，数组中第三个元素的混洗是第五个数组元素。即..

随机播放(A[010])= A[100]。 (假设数组大小为8个元素)

我们看到第 n-1 位“0”被左循环移位。所以 A[4] 的值被复制到 A[2] 中。我们能否在不对数组中的所有元素使用临时数组的情况下执行此操作...

我想在简单的纯 C 中实现这个功能，但我就是不明白如何更改这些位...

建议请...

Answer 1

您是否考虑过 Knuth Shuffle ？

这是来自 RosettaCode 的 C 语言示例:

#include <stdlib.h>
#include <string.h>

int rrand(int m)
{
  return (int)((double)m * ( rand() / (RAND_MAX+1.0) ));
}

#define BYTE(X) ((unsigned char *)(X)) 
void shuffle(void *obj, size_t nmemb, size_t size)
{
  void *temp = malloc(size);
  size_t n = nmemb;
  while ( n > 1 ) {
    size_t k = rrand(n--);
    memcpy(temp, BYTE(obj) + n*size, size);
    memcpy(BYTE(obj) + n*size, BYTE(obj) + k*size, size);
    memcpy(BYTE(obj) + k*size, temp, size);
  }
  free(temp);
}