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

Question

我正在寻找一种算法，我现在正在快速编程，但伪代码或任何相当相似的“C 系列”语法都可以。

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

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

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

编辑:我使用了改组数组的方法。我会在应用程序加载时随机播放一次，反正不会花那么长时间。这是我的“Dealer”类的代码。

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。每次您需要一张“卡片”时，您都会调用 Deal。当“甲板”完成时，它循环到开头。

Answer 1

如果你有足够的内存空间来存储所有的像素位置，你可以打乱它们:

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]);
 }

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