Best and most random way to get a set of unique random numbers-CodePudding

I need to pick 3 unique characters from a memorable word. This is the code from various places which works but it feels like there should be a more efficient way of doing it.

List<int> selections = new List<int>();
Random rand = new Random(); 
do {
    int index = rand.Next(memorableWord.Length);
    if (selections.Contains(index) != true) selections.Add(index);
} while (selections.Count <=2);

And is it better to generate a new Random object with this line, so it's using a new Random each loop or doesn't it matter either way?

int index = new Random().Next(memorableWord.Length);

CodePudding user response：

Try something like this:

private static readonly Random rng = new Random();

static string RandomChars( int n, string corpus )
{
  if (corpus.Length < 1) throw new ArgumentOutOfRangeException("corpus must contain at least on character.");
  if (n < 1 || n > corpus.Length) throw new ArgumentOutOfRangeException("n must be non-negative and less than or equal to the size of the corpus.");

  HashSet<char> set = new HashSet<char>();
  while (set.Count < n)
  {
    char ch = corpus[ rng.Next(corpus.Length) ];
    set.Add(ch);
  }
  
  return new string( set.ToArray() );
}

CodePudding user response：

It appears that you're trying to ensure unique selections of characters from a string.

What you're looking for is a shuffle, or a partial shuffle to get a subset of characters.

A Fisher-Yates shuffle would do the job efficiently from a computational point-of-view.

Here's the full implementation:

private Random _random = new Random();
public T[] FisherYates<T>(T[] source)
{
    T[] output = source.ToArray();
    for (var i = 0; i < output.Length; i  )
    {
        var j = _random.Next(i, output.Length);
        (output[i], output[j]) = (output[j], output[i]);
    }
    return output;
}

That will take an array of type T and return a fully shuffled array of the same size.

Note: Calling .ToArray() on an array calls Array.CopyTo under-the-hood, so it's efficient.

If you just want a subset of characters then this implementation allows you to specify the number of items you want:

public T[] FisherYates<T>(T[] source, int take)
{
    T[] output = source.ToArray();
    take = take < output.Length ? take : output.Length;
    for (var i = 0; i < take; i  )
    {
        var j = _random.Next(i, output.Length);
        (output[i], output[j]) = (output[j], output[i]);
    }
    return output.Take(take).ToArray();
}

This only iterates the Fisher-Yates loop the enough times to get the number of characters you need. So, if "best" means most efficient, then this is best.

So, let's try it:

string memorableWord = "Memorable";
for (int i = 0; i < 10; i  )
    Console.WriteLine(
        String.Concat(
            FisherYates(memorableWord.ToCharArray(), 4)));

That gave me:

Mleb
eoMe
Mber
lamM
eMlb
emlr
Mela
eebM
mrol
raeb

Now, if you just want "best" to be easiest to code, then this works:

char[] selection =
    memorableWord
        .OrderBy(x => _random.Next())
        .Take(4)
        .ToArray();

And, if you really just want unique indices, then this works too:

int[] selection =
    Enumerable
        .Range(0, memorableWord.Length)
        .OrderBy(x => _random.Next())
        .Take(4)
        .ToArray();

CodePudding user response：

List<int> selections = new List<int>();

do {
    int index = Random.Range(memorable.count);
    if (selections.Contains(memorable[index]) != true) selections.Add(memorable[index]);
} while (selections.Count <=2);

I hope to help you.