c - 普通 C 中的快速随机洗牌功能

Question

多年来，我一直在考虑这个问题，但从未成功实现过。我说的是一个快速、高效的 C 函数，它在输入中接受一个整数值(例如 16 位)，并在输出中给出完全不同的相同位大小的数字，但“考虑到”所有数字已经给出了，虽然不是通过使用真实的内存，而是通过数学魔法。抱歉，英语不是我的母语，我的意思是该函数应该随机一对一映射，但不能有任何重复。

我想象的可能的应用程序是像素交叉淡入淡出图形例程之一，您可以在其中用新图片逐个像素地替换屏幕上的旧图片。坐标应该是随机选择的，一旦一个像素被替换，它就不应该被再次寻址(没有重复)。所有这一切自然而然地通过一个基于数学的小型、快速和高效的函数(使用内存很容易实现，但这不是我想要的)。

显然，“位反转”解决方案不会起作用，因为它看起来不是随机的。甚至交换例如第 3 位和第 11 位，等等。创造更多的“困惑”，反转一些位，等等。看起来不太好，所以我正在寻找一个纯数学的，看起来很随机的函数，可能至少 16 位，并使用尽可能少的内存(没有预先计算的表格，因为我最终使用它的第一个应用程序是在微 Controller 系统上使用公共(public)域硬件和软件制作老式游戏)。

你能帮忙吗？

Answer 1

您正在寻找的基本上是与您想要淡入淡出的像素数相对应的组的循环生成器。在最一般的情况下，这是您组的大小的任意互质。通过以像素数为模进行所有计算，您得到了随机性的外观，但实际上并不是随机的。

假设您有一个大小为 32 的域，并以 5 的种子开始。通过不断添加 15 的互质数，您将得到以下序列

(5, 20, 3, 18, 1, 16, 31, 14, 29, 12, 27, 10, 25, 8, 23, 4,...)

对于您的要求，这可能看起来足够随机。