フレームワークのRandom
クラスを使用して、次の遅延実装を思いつき、カードのデッキをシャッフルしました。
次のコードの最悪の場合の複雑さを O(N + NlogN) と見積もっています。私は正しいですか?
データ構造
enum SuitType
{
Diamond,
Heart,
Spade,
Club
}
class Card
{
public SuitType suitType;
public int value;
public int randomOrder;
}
- 各カードに変数 randomOrder を追加しました。
- 次に、各カードの乱数を取得するために Randome.Next() を使用しています。
- この乱数に基づいてデッキを並べ替えます。
class Program
{
static void Main(string[] args)
{
Program p = new Program();
List<Card> deck = new List<Card>(52);
p.InitializeDeck(deck);
List<Card> shuffledDeck = p.ShuffleDeck(deck).ToList();
}
Random r = new Random();
readonly int RMIN = 1, RMAX = 100;
//O(N + NlogN)
private IEnumerable<Card> ShuffleDeck(List<Card> deck)
{
//O(N)
foreach (var d in deck)
{
d.randomOrder = r.Next(RMIN, RMAX);
}
//O(NlogN)
return deck.OrderBy(d => d.randomOrder);
}
private void InitializeDeck(List<Card> deck)
{
int suitCounter = 0;
for (int i = 1; i <= 52; i++)
{
deck.Add(new Card
{
suitType = (SuitType)suitCounter,
value = i,
randomOrder = r.Next(RMIN, RMAX)
});
if (i % 13 == 0)
{
suitCounter++;
}
}
}
}