-3

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

Glyn
  • 316
  • 2
  • 20
  • 1
    What idoes the documentation say when you research these questions? – Ňɏssa Pøngjǣrdenlarp Sep 07 '22 at 22:56
  • 1
    The title is asking for a set of unique random numbers, but the description is asking for unique characters. If `memorableWord` has more than one instance of the same character, are you allowed to return different indexes that point to the same character? – StriplingWarrior Sep 07 '22 at 23:02
  • 1
    Your concerns about efficiency are almost certainly a premature optimization. It will probably take orders of magnitude more time for one person to read your question than your program will spend executing this code, for the entire lifetime of the application you're writing. – StriplingWarrior Sep 07 '22 at 23:05
  • 3
    As for your second side question (please ask one question at a time), no, do not create `Random` in a loop: https://stackoverflow.com/questions/3053807/random-number-in-a-loop – Ry- Sep 07 '22 at 23:05
  • 2
    Since you’re asking for “most random”, what kind of application is it? Is it cryptography/password-related, where it’s important that there’s no bias and that the randomness is impossible to predict? Is it simulation-related, where predictability isn’t an issue but bias could skew the results? Or is it casual (game, flash cards, …), where small biases are okay? – Ry- Sep 07 '22 at 23:12
  • 2
    Since you are only picking 3 characters, your approach is probably the best. The other way to go is to use a _shuffle_ algorithm (to shuffle the letters in the word) and then pick the first three letters. By the way, if the word is something like **letter**, do you still care about uniqueness (the word is 6 characters long, but only has 4 unique letters) – Flydog57 Sep 07 '22 at 23:29

3 Answers3

1

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() );
}
Nicholas Carey
  • 71,308
  • 16
  • 93
  • 135
1

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();
Enigmativity
  • 113,464
  • 11
  • 89
  • 172
  • Note that _Memorable_ has two letter E-s (and two Ms (though one is capitalized)). As a result `eebM` is one of the results this solution generates. Does this meet the original spec? – Flydog57 Sep 08 '22 at 16:11
  • @Flydog57 - Yes, I chose the word for that purpose. The original code was selecting unique indices, and not characters, so I continued that approach. – Enigmativity Sep 08 '22 at 22:04
-3
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.

BlackDragon94
  • 41
  • 6