在不重复的情况下选择位图中每个像素的公式

Question

我正在寻找一种算法，我现在正在使用 swift 编程，但是伪代码或任何相当相似的 "C family" 语法都可以。

想象一下一个很大的值列表，例如位图中的像素。您希望以视觉上随机的顺序挑选每一个，一次挑选一个，不要两次挑选相同的，最后总是会全部挑选。

我以前在 Fractal 生成器中使用过它，这样它就不仅仅是逐行渲染，而是以一种随机的方式慢慢构建它，但那是很久以前的事了，在 Java 小程序中，并且我没有密码了。

我不相信它使用了任何伪随机数生成器，我喜欢它的主要一点是它不会使渲染时间比逐行方法花费更长的时间。除非我遗漏了什么，否则我看过的任何改组算法都会使渲染花费更长的时间来处理如此大量的值。

编辑：我使用了改组数组的方法。我会在应用程序加载时随机播放一次，反正不会花那么长时间。这是我的 "Dealer" class.

的代码

import Foundation
import Cocoa
import Quartz

class Dealer: NSObject
{
  //########################################################
  var deck = [(CGFloat,CGFloat)]()
  var count = 0
  //########################################################
  init(_ w:Int, _ h:Int)
  {
    super.init()
    deck.reserveCapacity((w*h)+1)
    for y in 0...h
    {
      for x in 0...w
      {
        deck.append((CGFloat(x),CGFloat(y)))
      }
    }
    self.shuffle()
  }
  //########################################################
  func shuffle()
  {
    var j:Int = 0
    let total:Int = deck.count-1
    for i:Int in 0...total
    {
      j = Int(arc4random_uniform(UInt32(total)))
      deck.swapAt(i, j)
    }
  }
  //########################################################
  func deal() -> (CGFloat,CGFloat)
  {
    let result = deck[count]
    let total:Int = deck.count-1
    if(count<total) { count=count+1 } else { count=0 }
    return(result)
  }
  //########################################################
}

init 被调用了一次，它调用了 shuffle，但如果你愿意，可以在需要时再次调用 shuffle。每次您需要 "card" 时，您都会调用 Deal。当 "deck" 完成时，它循环到开头。

Answer 1

您需要实现一个具有理论上已知周期的 pseudo-random 数字生成器，该周期大于但非常接近列表中的元素数。假设 R() 是实现这样一个 RNG 的函数。

然后：

for i = 1...N
    do
        idx = R()
    while idx > N
    output element(idx)
end

如果RNG的周期大于N，则保证该算法完成，绝不会输出同一个元素两次
如果 RNG 的周期接近 N，则此算法将很快（即 do-while 循环将主要执行 1 次迭代）。
如果RNG质量好，视觉输出会好看；在这里你必须做实验并决定什么对你来说足够好

要找到周期为 exactly-known 的随机数生成器，您应该研究有关随机数生成器的理论，该理论非常广泛（可能过于广泛）； Wikipedia 有有用的链接。从Linear congruential generators开始：它们很简单，而且有可能质量足够好。

Answer 2

如果您有足够的内存 space 来存储所有像素位置，您可以随机排列它们：

const int xs=640;            // image resolution
const int ys=480;
color pixel[sz];             // image data
const int sz=xs*ys;          // image size 
int adr[sz],i,j;
for (i=0;i<sz;i++) adr[i]=i; // ordered positions
for (i=0;i<sz;i++)           // shuffle them
 {
 j = random(sz);             // pseudo-randomness with uniform distribution 
 swap(pixel[i],pixel[j]);
 }

这样你就可以保证每个像素都被使用一次，而且很可能所有的像素都被打乱了......

Answer 3

这是一个基于 linear feedback shift registers 的工作示例。由于 n 位 LFSR 的最大序列长度为 2ⁿ−1 步，这将当像素数小于 2 的幂时，效果最佳。对于其他尺寸，pseudo-random 坐标将被丢弃，直到获得位于指定坐标范围内的像素。这仍然是相当有效的；在最坏的情况下（其中 w×h 是 2 的幂），每个坐标对平均有两次 LSFR 迭代。

以下代码在 Javascript 中，但将其移植到 Swift 或任何其他语言应该很容易。

注意：对于像 1920×1024 这样的大 canvas 区域，使用较小尺寸（例如 128×128）的重复图块会更有意义。平铺将是不可察觉的。

var lsfr_register, lsfr_mask, lsfr_fill_width, lsfr_fill_height, lsfr_state, lsfr_timer;
var lsfr_canvas, lsfr_canvas_context, lsfr_blocks_per_frame, lsfr_frame_rate = 50;

function lsfr_setup(width, height, callback, duration) {
    // Maximal length LSFR feedback terms
    // (sourced from http://users.ece.cmu.edu/~koopman/lfsr/index.html)
    var taps = [ -1, 0x1, 0x3, 0x5, 0x9, 0x12, 0x21, 0x41, 0x8E, 0x108, 0x204, 0x402,
                 0x829, 0x100D, 0x2015, 0x4001, 0x8016, 0x10004, 0x20013, 0x40013,
                 0x80004, 0x100002, 0x200001, 0x400010, 0x80000D, 0x1000004, 0x2000023,
                 0x4000013, 0x8000004, 0x10000002, 0x20000029, 0x40000004, 0x80000057 ];
    nblocks = width * height;
    lsfr_size = nblocks.toString(2).length;
    if (lsfr_size > 32) {
        // Anything longer than about 21 bits would be quite slow anyway
        console.log("Unsupposrted LSFR size ("+lsfr_size+")");
        return;
    }
    lsfr_register = 1;
    lsfr_mask = taps[lsfr_size];
    lsfr_state = nblocks;
    lsfr_fill_width = width;
    lsfr_fill_height = height;
    lsfr_blocks_per_frame = Math.ceil(nblocks / (duration * lsfr_frame_rate));
    lsfr_timer = setInterval(callback, Math.ceil(1000 / lsfr_frame_rate));
}

function lsfr_step() {
    var x, y;
    do {
        // Generate x,y pairs until they are within the bounds of the canvas area
        // Worst-case for an n-bit LSFR is n iterations in one call (2 on average)
        // Best-case (where w*h is one less than a power of 2): 1 call per iteration
        if (lsfr_register & 1) lsfr_register = (lsfr_register >> 1) ^ lsfr_mask;
        else lsfr_register >>= 1;
        y = Math.floor((lsfr_register-1) / lsfr_fill_width);
    } while (y >= lsfr_fill_height);
    x = (lsfr_register-1) % lsfr_fill_width;
    return [x, y];
}

function lsfr_callback() {
    var coords;
    for (var i=0; i<lsfr_blocks_per_frame; i++) {
        // Fetch pseudo-random coordinates and fill the corresponding pixels
        coords = lsfr_step();
        lsfr_canvas_context.fillRect(coords[0],coords[1],1,1);
        if (--lsfr_state <= 0) {
            clearInterval(lsfr_timer);
            break;
        }
    }
}

function start_fade() {
    var w = document.getElementById("w").value * 1;
    var h = document.getElementById("h").value * 1;
    var dur = document.getElementById("dur").value * 1;
    lsfr_canvas = document.getElementById("cv");
    lsfr_canvas.width = w;
    lsfr_canvas.height = h;
    lsfr_canvas_context = lsfr_canvas.getContext("2d");
    lsfr_canvas_context.fillStyle = "#ffff00";
    lsfr_canvas_context.fillRect(0,0,w,h);
    lsfr_canvas_context.fillStyle = "#ff0000";
    lsfr_setup(w, h, lsfr_callback, dur);
}

Size:
<input type="text" size="3" id="w" value="320"/>
×
<input type="text" size="3" id="h" value="240"/>
in
<input type="text" size="3" id="dur" value="3"/>
secs
<button onclick="start_fade(); return 0">Start</button>
<br />
<canvas id="cv" width="320" height="240" style="border:1px solid #ccc"/>

在不重复的情况下选择位图中每个像素的公式

formula to pick every pixel in a bitmap without repeating

sorting

random

algorithm

array-formulas

swift