public class NonRepeatingListFactory
{
    public static INonRepeatingList GetNonRepeatingList(int min, int max, int count)
    {
        long length = max - min + 1;
        if (length / 8 > count * 2 * sizeof(int))
        {
            //if the amount of bytes occupied by the array is greater then the dictionary
            return new NonRepeatingListWithSet();
        }
        return new NonRepeatingListWithArray(min, max);
    }
}

public interface INonRepeatingList : IEnumerable<int>
{
    bool Add(int value);
}

internal class NonRepeatingListWithArray : List<int>, INonRepeatingList
{
    private readonly BitArray inList;
    private readonly int min;
    private readonly int max;

    public NonRepeatingListWithArray(int min, int max)
    {
        this.inList = new BitArray(max-min+1);
        this.min = min;
        this.max = max;
    }

    bool INonRepeatingList.Add(int value)
    {
        if (!this.inList[value - this.min])
        {
            this.Add(value);
            this.inList[value - this.min] = true;
            return true;
        }
        return false;
    }
}

internal class NonRepeatingListWithSet : List<int>, INonRepeatingList
{
    private readonly HashSet<int> mapValue = new HashSet<int>();
    private int currentIndex = 0;

    bool INonRepeatingList.Add(int value)
    {
        if (mapValue.Add(value))
        {
            base.Add(value);
            return true;
        }
        return false;
    }
}

public static class MathUtils
{
    public static double Factorial(this int n)
    {
        if (n < 2)
        {
            return 1;
        }
        return n*Factorial(n - 1);
    }

    public static double Factorial(this int n, int min)
    {
        double acc = 1;
        while (n >= min)
        {
            acc *= n;
            --n;
        }
        return acc;
    }
}

public static class CollectionUtils
{
    private static readonly Random random = new Random();

    public static IList<T> Shuffle<T>(this IEnumerable<T> col)
    {
        var list = col as IList<T> ?? col.ToList();
        for (int i = 0; i < list.Count; ++i)
        {
            //get a chance of staying in same place
            list.Swap(i, random.Next(i, list.Count));
        }
        return list;
    }

    public static void Swap<T>(this IEnumerable<T> col, int idxSrc, int idxDest)
    {
        var list = col as IList<T> ?? col.ToList();
        T aux = list[idxSrc];
        list[idxSrc] = list[idxDest];
        list[idxDest] = aux;
    }
}

[TestFixture]
public class TestNonRepeatingGenerator
{
    [Test]
    public void TestLastCountElementsAreNotInIndex0()
    {
        for (int i = 0; i < 1000000; ++i)
        {
            var list = Sequence.BobFloydNonRepeatingSequence(0, 15, 4).ToList();
            Assert.IsFalse(new[] { 12, 13, 14, 15 }.Contains(list[0]));
            Assert.AreEqual(4, list.Count);
        }
    }

    [Test]
    public void TestBobFloydBecomesLinear()
    {
        var list = Sequence.BobFloydNonRepeatingSequence(0, 15, 16).ToList();
        for (int i = 0; i < list.Count; ++i)
        {
            Assert.AreEqual(i, list[i]);
        }
    }

    [Test]
    public void TestBobFloydRandomness()
    {
        TestRandomness(() => Sequence.BobFloydNonRepeatingSequence(0, 15, 4).ToList(), 16, 4);
    }


    [Test]
    public void TestBobFloydWithShuffleRandomness()
    {
        TestRandomness(() => Sequence.NonRepeatingRandomSequence(0, 31, 4).ToList(), 32, 4);
    }

    [Test]
    public void TestShuffleRandomness()
    {
        TestRandomness(() => Enumerable.Range(0, 15).ToList().Shuffle().Take(4).ToList(), 16, 4);
    }


    public void TestRandomness(Func<List<int>> getRandomList, int rangeLength, int count)
    {
        long combinations = (long)(rangeLength.Factorial(rangeLength - count + 1) * ((double)(count - 1) / count));
        long iterations = combinations * 100;
        var partitioner = Partitioner.Create(0, iterations, iterations / 4);
        ConcurrentDictionary<long, int> ocurrences = new ConcurrentDictionary<long, int>(Environment.ProcessorCount, (int)combinations);

        Parallel.ForEach(partitioner, new ParallelOptions() {MaxDegreeOfParallelism = Environment.ProcessorCount},
            range =>
            {
                //hopefully having a private dictionary will help concurrency
                Dictionary<long, int> privateOcurrences = new Dictionary<long, int>();
                for (long i = range.Item1; i < range.Item2; ++i)
                {
                    var list = getRandomList();
                    long acc = 0;
                    //this will only work when numbers are between 0 and 88
                    foreach (var value in list)
                    {
                        acc = (value + 11) + acc*100;
                    }
                    privateOcurrences.AddOrUpdate(acc, 1, v => v + 1);
                }
                foreach (var privateOcurrence in privateOcurrences)
                {
                    ocurrences.AddOrUpdate(privateOcurrence.Key,
                        privateOcurrence.Value,
                        (k, v) => v + privateOcurrence.Value);
                }
            });

        double averageOcurrences = iterations / combinations;
        double currentAverage = ocurrences.Values.Average();
        Debug.WriteLine("The average ocurrences of this implementation is {0} comparing to {1} in the 'perfect' scenario", currentAverage, averageOcurrences);
        Assert.Less(currentAverage, averageOcurrences * 1.05);
        Assert.Greater(currentAverage, averageOcurrences * 0.95);
    }
}