生成无重复的随机数

#1 楼

    do number = random.Next();
    while (randomNumbers.Contains(number));

    do
    {
        number = random.Next();
    } while (randomNumbers.Contains(number));

List<int> randomNumbers = new List<int>(count);

using System;
using System.Collections.Generic;

public class Test
{
    static Random random = new Random();

    public static List<int> GenerateRandom(int count)
    {
        // generate count random values.
        HashSet<int> candidates = new HashSet<int>();
        while (candidates.Count < count)
        {
            // May strike a duplicate.
            candidates.Add(random.Next());
        }

        // load them in to a list.
        List<int> result = new List<int>();
        result.AddRange(candidates);

        // shuffle the results:
        int i = result.Count;  
        while (i > 1)
        {  
            i--;  
            int k = random.Next(i + 1);  
            int value = result[k];  
            result[k] = result[i];  
            result[i] = value;  
        }  
        return result;
    }
    public static void Main()
    {
        List<int> vals = GenerateRandom(10);
        Console.WriteLine("Result: " + vals.Count);
        vals.ForEach(Console.WriteLine);
    }
}

initialize set S to empty
for J := N-M + 1 to N do
    T := RandInt(1, J)
    if T is not in S then
        insert T in S
    else
        insert J in S

#2 楼

Enumerable.Range(0,100).OrderBy(x => Guid.NewGuid()).Take(20);

Enumerable.Range(0,100).OrderBy(x => random.Next()).Take(20);

void Main()
{
    var random = new Random();
    var times = new TimeSpan[512];
    var values = new bool[512];
    var sw = new Stopwatch();

    for(int i = 0; i < times.Length; i++) 
    {   
        sw.Restart();
        while(true) {
            int rand = random.Next();

            if(rand > 7894500 && rand < 7894512) 
            {
                int index = rand - 7894500;
                if(!values[index])
                {
                    values[index] = true;
                    break;
                }
            }
        }
        sw.Stop();
        times[i] = sw.Elapsed;
        Console.WriteLine ("Elapsed time: " + sw.Elapsed);
    }

    var orderedTime = times.OrderBy(x => x);
    for(int i = 0; i < 512; i++)
    {
        Console.WriteLine (orderedTime.ElementAt(i));
    }
}

#3 楼

public static List<int> GetRandomNumbers(int count)
{
    List<int> randomNumbers = new List<int>(); 

    for (int i=0; i<count; i++) 
    {    
        int number;

        do number = random.Next();
        while (randomNumbers.Contains(number));

        randomNumbers.Add(number);
    }

    return randomNumbers;
}

#4 楼

class RandomSequence {

  int actual;
  static final int M = (1<<31) -1;

  public RandomSequence(int seed) {
    this.actual = seed
  }

  public int next() {
    return this.actual = (16807 * this.actual) % RandomSequence.M
  }

}

#5 楼

do
{
    bar();
}
while (foo);

#6 楼

#7 楼

static IEnumerable<int> NonRepeatingRandomSequence(int min, int max, int count, int? seed = null)

public void TestRandomness(Func<List<int>> getRandomList, int rangeLength, int count)
{
    long combinations = (long)(rangeLength.Factorial(rangeLength - count + 1));
    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);
}

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

public static IEnumerable<int> BobFloydNonRepeatingSequence(int min, int max, int count, int? seed = null)
{
    Random random;
    if (seed != null)
    {
        random = new Random(seed.Value);
    }
    else
    {
        random = new Random();
    }
    long length = max - min + 1;
    INonRepeatingList values = NonRepeatingListFactory.GetNonRepeatingList(min, max, count);
    for (int i = (int)(length - count); i < length; ++i)
    {
        if (!values.Add(random.Next(min, i+min+1)))
        {
            values.Add(i+min);
        }
    }
    return values;
}

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

public static IEnumerable<int> NonRepeatingRandomSequence(int min, int max, int count, int? seed = null)
{
    Random random;
    if (seed != null)
    {
        random = new Random(seed.Value);
    }
    else
    {
        random = new Random();
    }
    long length = max - min + 1;
    INonRepeatingList values = NonRepeatingListFactory.GetNonRepeatingList(min, max, count);
    for (int i = (int)(length - count); i < length; ++i)
    {
        if (!values.Add(random.Next(min, i+min+1)))
        {
            values.Add(i+min);
        }
    }
    values.Shuffle();
    return values;
}

#8 楼

#9 楼

#10 楼

#11 楼

#12 楼

#13 楼

public static int[] GetRandomNumbers(int count, int minValue, int maxValue)
{
    int[] randomNumbers = new int[count]; 

    for (int i=0; i < count; ++i) 
    {      
        //Given (min - max) is the range, there can only be (range - i) unique number left
        int number = random.Next(minValue, maxValue - i);

        //if the number is greater than or equal to, then increase the number
        for (int j=0; j < i; ++j)
            if(number >= randomNumbers[j])
                ++number; 

        randomNumbers.Add(number);
    }

    return randomNumbers;
}

#14 楼

static void PrintRandom(int limit)
{

        List<int> original = Enumerable.Range(1, limit).ToList();
        Random rand = new Random ();

        //shuffle the list

        List <int> sorted = original.OrderBy(item => rand.Next()).ToList ();
        foreach (int i in sorted)
        {
            Console.WriteLine(i);   
        }
        Console.ReadKey();
}

#15 楼

    public static IEnumerable<int> GetRandomNumbers(int count, int minValue, int maxValue)
    {
        if (count < 1)
        {
            throw new ArgumentException("Count must be greater then 0", "count");
        }

        if (count > Math.Abs(maxValue - minValue))
        {
            throw new ArgumentException("MaxValue must be greater than count", "maxValue");
        }

        var segmentSize = (maxValue - minValue) / count;
        var random = new Random();
        var steps = Enumerable.Range(0, count).ToList();

        while (steps.Count != 0)
        {
            var currentIndex = random.Next(0, steps.Count);
            var index = steps[currentIndex];
            steps.RemoveAt(currentIndex);

            yield return random.Next((index * segmentSize) + minValue, ((index + 1) * segmentSize) + minValue);
        }
    }

    public static IEnumerable<int> GetRandomNumbers(int count)
    {
        return GetRandomNumbers(count, 0, int.MaxValue);
    }

#16 楼

private static Random rand = new Random();
public static IEnumerable<int> GetRandomNumbers(int count)
{
    HashSet<int> randomNumbers = new HashSet<int>();
    while(randomNumbers.Count < count)
    {
        int r = rand.Next();
        if (randomNumbers.Add(r))
            yield return r;
    }
}