在 Solidity 中獲取不替換的隨機數

我正在嘗試使用Solidity對隨機數進行抽樣****而不進行替換，直到可能的數字池用完為止。在虛擬碼中，它應該是這樣的：

1. Initial pool of numbers: (1, 2, 3, 4)
2. Attempt 1: one of (1, 2, 3, 4) are possible, 3 is sampled
3. Attempt 2: one of (1, 2, 4) are possible, 4 is sampled
4. Attempt 3: one of (1, 2) are possible, 1 is sampled
5. Attempt 4: one of (2,) are possible, 2 is sampled
6. End

請注意，每個Attempt都是對合約的不同呼叫（由不同的使用者/發件人/錢包）。

到目前為止，下面的程式碼為我提供了一個 1 到 50 範圍內的隨機數：

uint256 public randomResult;

function fulfillRandomness(bytes32 requestId, uint256 randomness) internal override {
   randomResult = (randomness % 50) + 1;
}

我不知道如何使用 Solidity 將虛擬碼的邏輯放入智能合約中。最好避免需要迭代以檢查是否已看到數字的解決方案。任何幫助表示讚賞。謝謝。

假設您最初的“一副牌”是

$$ 0, 1, …, N-1 $$，以下應該大致工作。我基本上沒有嘗試編譯或檢查這個，但底層算法應該是合理的。 大致來說，方法是這樣的：

• 你從一個排序好的“一副牌”開始，$$ 0, …, N-1 $$. 這個套牌是隱含的。

• 要隨機選擇一張牌，您：

  • 在目前牌組中選擇一個隨機位置
  • 在該位置選擇卡片
  • 將卡組底部的卡移動到隨機位置

這樣，您可以將一個統一的隨機整數生成器轉換為一個隨機整數流而無需替換，並且每次呼叫在時間和空間上都是 O(1)，因此您不會遇到塊氣體限制的基本問題。

實現方式：

uint256 cardsRemaining;
mapping(uint256 => uint256) movedCards;

constructor(...) {
   [...]
   cardsRemaining = N;
}

// Return a random integer from 0 to k-1, inclusive.
// You might want to use, e.g, ChainLink, for random int generation.
function getRandom(uint256 k) private returns uint256 {
   [...]
}

function cardAt(uint256 i) private returns uint256 {
   if (movedCards[i]) {
       return movedCards[i];
   } else {
       return i;
   }
}

// Draw another "card" without replacement
function draw() public returns uint256 {
   require(cardsRemaining > 0, "All cards drawn");
   
   // Pick i
   uint256 i = getRandom(cardsRemaining);

   // Pick the ith card in the "deck"
   uint256 outCard = cardAt(i);

   // Move the last card in the deck into position i
   movedCards[i] = cardAt(cardsRemaining - 1);
   movedCards[cardsRemaining - 1] = 0;
   cardsRemaining -= 1;

   return outCard;
}

引用自：https://ethereum.stackexchange.com/questions/110848