The following program implements a random bag. Random bag iterations provide the items in random order. All N! permutations are equally likely. Items are kept in an array and their order is randomized for each iterator.

Supported operations:

  • Add(Item)
using System;
using System.Collections;

namespace ConsoleTest
{
    class Program
    {
        static void Main(string[] args)
        {
            RandomBag rb = new RandomBag(5);

            rb.Add("A");
            rb.Add("B");
            rb.Add("C");
            rb.Add("D");
            rb.Add("E");

            for (int i = 1; i <= 20; ++i)
            {
                foreach (string s in rb)
                    Console.Write(s + " ");
                Console.WriteLine();
            }

            Console.ReadKey();
        }

        class RandomBag where T : class
        {
            private T[] a; // bag entries
            private int N; // bag size

            private Random rnd = new Random();

            public bool IsEmpty { get { return N == 0; } }
            public int Size { get { return N; } }

            public RandomBag(int capacity)
            {
                a = new T[capacity];
            }

            public void Add(T item)
            {
                // Check if the array is too small and if there is no room, double its size.
                if (N == a.Length)
                    Resize(2 * a.Length);

                // Add the item to the top of the bag.
                a[N++] = item; // set a[N]=item and then increment N
            }

            // We need an iterator as there is no other method to access the bag elements.
            public IEnumerator GetEnumerator()
            {
                // Randomize the order of the items for this iterator.
                Shuffle();

                for (int i=0; i< N; ++i)
                {
                    yield return a[i];
                }
            }

            // Move a bag of size N <= newSize to a new array of the newSize.
            private void Resize(int newSize)
            {
                T[] tmp = new T[newSize];
                for (int i = 0; i < N; ++i)
                    tmp[i] = a[i];
                a = tmp;
            }

            // Randomly shuffle the N first elements in the bag's array.
            private void Shuffle()
            {
                for (int i = 0; i < N; ++i)
                {
                    // Exchange a[i] with a random element in a[i..N-1]
                    // All N! permutations are equally likely.
                    // This code is based on Ex.1.1.36-37
                    int r = rnd.Next(i, N);
                    T tmp = a[i];
                    a[i] = a[r];
                    a[r] = tmp;
                }
            }
        }
    }
}

Output:

D B C E A
B D E C A
B D C E A
B C D E A
B A C D E
E A B C D
C B D A E
C B E D A
D C A E B
A E B C D
A E C D B
D E C A B
D C B E A
E B A D C
E D A C B
A D C B E
A C B E D
E D C B A
E A B C D
A C B D E