Pick Random string from List with exclusions and non-repetitive pick

Question

im trying to write a program that would let a user:

1. Load a set of string.
2. Loop through the set, and pick another string from the same set.
3. Avoid a picked string from being picked again.
4. Have specific strings not be able to pick specified strings.

Example is table below:

And below table is a sample scenario:

How am i supposed to do this the easy way?

i have below code, but it is taking like forever to generate a valid set since it restarts everything if there are nothing left to pick, while not eliminating the possibility.

private List<Participant> _participants;

AllOverAgain:

var pickedParticipants = new List<Participant>();
var participantPicks = new List<ParticipantPick>();

foreach(var participant in _participants)
{
    var pickedParticipantNames = from rp in participantPicks select rp.PickedParticipant;

    var picks = (from p in _participants where p.Name != participant.Name & !Utilities.IsInList(p.Name, pickedParticipantNames) select p).ToList();

    var pick = picks[new Random().Next(0, picks.Count())];

    if(pick == null)
    {
        UpdateStatus($"No Available Picks left for {participant.Name}, Restarting...");
        goto AllOverAgain;
    }

    var exclusions = participant.Exclusions.Split(',').Select(p => p.Trim()).ToList();

    if(exclusions.Contains(pick.Name))
    {
        UpdateStatus($"No Available Picks left for {participant.Name}, Restarting...");

        goto AllOverAgain;
    }

    participantPicks.Add(new ParticipantPick(participant.Name, pick.Name, participant.Number));
}

return participantPicks; // Returns the final output result

The Participant Class consists of these Properties:

public string Name { get; set; }
public string Number { get; set; }
public string Exclusions { get; set; }

The ParticipantPick Class consists of these Properties:

public string Participant { get; set; }
public string PickedParticipant { get; set; }
public string Number { get; set; }

Answer 1

One way you can solve this is by using a dictionary, using a composite key of a tuple and the matching value of a datatype bool.

Dictionary<Tuple<string, string>, bool>

The composite key Tuple<sring,string> will contain every permutation of participants and match them to their appropriate bool value.

For example, the dictionary filled with values such as:

Dictionary<Tuple<"Judith","James">, true>

...would be indicating that Judith picking James is valid.

So lets create a dictionary with every single possible combination of participants, and set the value of them to true for them being valid at the start of the program.

This can be accomplished by a cartesian join using an array with itself.

Dictionary<Tuple<string, string>, bool> dictionary = participants.SelectMany(left => participants, (left, right) => new Tuple<string, string>(left, right)).ToDictionary(item=> item, item=>true);

After getting every permutation of possible picks and setting them to true, we can go through the "not allowed to pick" lists and change the dictionary value for that composite key to false.

dictionary[new Tuple<string, string>(personNotAllowing, notAllowedPerson)] = false;

You can remove a participant from picking itself by using a loop in the following way:

for(int abc=0;abc<participants.Length;abc++)
{
    //remove clone set
    Tuple<string, string> clonePair = Tuple.Create(participants[abc], participants[abc]);
    dictionary.Remove(clonePair);
}

Or by simply changing the value of the clone pair to false.

for(int abc=0;abc<participants.Length;abc++)
{
    dictionary[Tuple.Create(participants[abc],participants[abc])] = false;
}

In this example program, I create a string[] of participants, and a string[] for the respective list of people they do not allow. I then perform a cartesian join, the participants array with itself. This leads to every permutation, with an initial true boolean value.

I change the dictionary where the participants are not allowed to false, and display the example dictionary.

Afterward, I create 10 instances of random participants who are picking other random participants and test if it would be valid.

Every time a participant picks another participant, I check that composite key to see if it has a value of true.

If it does result in a valid pick, then every combination of the resulting participant who was picked gets set to false.

 for(int j=0; j<participants.Length;j++)
 {
     //Make the partner never be able to be picked again
     Tuple<string, string> currentPair2 = Tuple.Create(partner, participants[j]);
     try
     {
         dictionary[currentPair2] = false;
     }
     catch
     {
     }
}

This concept is better illustrated with running the code.

The demo:

static void Main(string[] args)
{
    //Create participants set
    string[] participants = {"James","John","Tyrone","Rebecca","Tiffany","Judith"};

    //Create not allowed lists
    string[] jamesNotAllowedList = {"Tiffany", "Tyrone"};
    string[] johnNotAllowedList = {};
    string[] tyroneNotAllowedList = {};
    string[] rebeccaNotAllowedList ={"James", "Tiffany"};
    string[] judithNotAllowedList = {};
    //Create list of not allowed lists
    string[][] notAllowedLists = { jamesNotAllowedList, johnNotAllowedList, tyroneNotAllowedList, rebeccaNotAllowedList, judithNotAllowedList};

    //Create dictionary<Tuple<string,string>, bool> from participants array by using cartesian join on itself
    Dictionary<Tuple<string, string>, bool> dictionary = participants.SelectMany(left => participants, (left, right) => new Tuple<string, string>(left, right)).ToDictionary(item=> item, item=>true);

    //Loop through each person who owns a notAllowedList 
    for (int list = 0; list < notAllowedLists.Length; list++)
    {
        //Loop through each name on the not allowed list
        for (int person = 0; person<notAllowedLists[list].Length; person++)
        {
            string personNotAllowing = participants[list];
            string notAllowedPerson = notAllowedLists[list][person];
            //Change the boolean value matched to the composite key
            dictionary[new Tuple<string, string>(personNotAllowing, notAllowedPerson)] = false;
            Console.WriteLine(personNotAllowing + " did not allow " + notAllowedPerson);
        }
    }                

    //Then since a participant cant pick itself
    for(int abc=0;abc<participants.Length;abc++)
    {
        //remove clone set
        Tuple<string, string> clonePair = Tuple.Create(participants[abc], participants[abc]);
        dictionary.Remove(clonePair);
    }

    //Display whats going on with this Dictionary<Tuple<string,string>, bool>
    Console.WriteLine("--------Allowed?--Dictionary------------\n");
    Console.WriteLine(string.Join("  \n", dictionary));
    Console.WriteLine("----------------------------------------\n\n");

    //Create Random Object
    Random rand = new Random();

    //Now that the data is organized in a dictionary..
      //..Let's have random participants pick random participants

    //For this demonstration lets try it 10 times
    for (int i=0;i<20;i++)
    {
        //Create a new random participant
        int rNum = rand.Next(participants.Length);
        string randomParticipant = participants[rNum];
        //Random participant picks a random participant
        string partner = participants[rand.Next(participants.Length)];

        //Create composite key for the current pair
        Tuple<string, string> currentPair = Tuple.Create(partner,randomParticipant);

        //Check if it's a valid choice
        try
        {
            if (dictionary[currentPair])
            {
                Console.WriteLine(randomParticipant + " tries to pick " + partner);
                Console.WriteLine("Valid.\n");
                //add to dictionary
                for(int j=0; j<participants.Length;j++)
                {
                    //Make the partner never be able to be picked again
                    Tuple<string, string> currentPair2 = Tuple.Create(partner, participants[j]);
                    try
                    {
                        dictionary[currentPair2] = false;
                    }
                    catch
                    {

                    }
                }

            }
            else
            {
                Console.WriteLine(randomParticipant + " tries to pick " + partner);
                Console.WriteLine(">>>>>>>>Invalid.\n");
            }
        }
        catch
        {
            //otherwise exception happens because the random participant
              //And its partner participant are the same person

            //You can also handle the random participant picking itself differently
              //In this catch block

            //Make sure the loop continues as many times as necessary
            //by acting like this instance never existed
            i = i - 1;
        }


    }


    Console.ReadLine();

}

Answer 2

This code will always give you output that adheres to your criteria:

public static class Program
{

    public static void Main(string[] args)
    {
        var gathering = new Gathering();
        gathering.MakeSelections();

        foreach (var item in gathering.participants)
        {
            Console.WriteLine(item.name + ":" + item.selectedParticipant);
        }
    }

    public class Participant
    {
        public string name;
        public List<string> exclusions;
        public string selectedParticipant;
    }

    public class Gathering
    {
        public List<Participant> participants;
        public List<string> availableParticipants;
        public List<string> usedNames;
        public Dictionary<string, string> result;

        public Gathering()
        {
            //initialize participants
            participants = new List<Participant>();

            participants.Add(new Participant
            {
                name = "James",
                exclusions = new List<string> { "Tiffany", "Tyrone" }
            });

            participants.Add(new Participant
            {
                name = "John",
                exclusions = new List<string> { }
            });

            participants.Add(new Participant
            {
                name = "Judith",
                exclusions = new List<string> { }
            });

            participants.Add(new Participant
            {
                name = "Rebecca",
                exclusions = new List<string> { "James", "Tiffany" }
            });

            participants.Add(new Participant
            {
                name = "Tiffany",
                exclusions = new List<string> { }
            });

            participants.Add(new Participant
            {
                name = "Tyrone",
                exclusions = new List<string> { }
            });

            //prevent participants from selecting themselves
            foreach (Participant p in participants)
            {
                p.exclusions.Add(p.name);
            }

            //create list of all the names (all available participants at the beginning)
            availableParticipants = participants.Select(x => x.name).ToList();

        }

        public void MakeSelections()
        {
            Participant currentParticipant;
            Random randy = new Random();


            //Sort Participants by the length of their exclusion lists, in descending order.
            participants.Sort((p1, p2) => p2.exclusions.Count.CompareTo(p1.exclusions.Count));

            //Get the first participant in the list which hasn't selected someone yet
            currentParticipant = participants.FirstOrDefault(p => p.selectedParticipant == null);

            while (currentParticipant != null)
            {
                //of the available participants, create a list to choose from for the current participant
                List<string> listToChooseFrom = availableParticipants.Where(x => !currentParticipant.exclusions.Contains(x)).ToList();

                //select a random participant from the list of eligible ones to be matched with the current participant
                string assignee = listToChooseFrom[randy.Next(listToChooseFrom.Count)];
                currentParticipant.selectedParticipant = assignee;

                //remove the selected participant from the list of available participants
                availableParticipants.RemoveAt(availableParticipants.IndexOf(assignee));

                //remove the selected participant from everyone's exclusion lists
                foreach (Participant p in participants)
                    if (p.exclusions.Contains(assignee))
                        p.exclusions.RemoveAt(p.exclusions.IndexOf(assignee));

                //Resort Participants by the length of their exclusion lists, in descending order.
                participants.Sort((p1, p2) => p2.exclusions.Count.CompareTo(p1.exclusions.Count));

                //Get the first participant in the list which hasn't selected someone yet
                currentParticipant = participants.FirstOrDefault(p => p.selectedParticipant == null);
            }

            //finally, sort by alphabetical order
            participants.Sort((p1, p2) => p1.name.CompareTo(p2.name));

        }
    }
}

Answer 3

In the simpler version, the items can just be shuffled:

string[] source = { "A", "B", "C", "D", "E", "F" };
string[] picked = source.ToArray(); // copy
var rand = new Random();

for (int i = source.Length - 1, r; i > 0; --i)
{
    var pick = picked[r = rand.Next(i)];    // pick random item less than the current one 
    picked[r] = picked[i];                  // and swap with the current one
    picked[i] = pick;

    Console.WriteLine(i + " swapped with " + r);
}

Console.WriteLine("\nsource: " + string.Join(", ", source) + 
                  "\npicked: " + string.Join(", ", picked));

sample result:

5 swapped with 4
4 swapped with 2
3 swapped with 0
2 swapped with 1
1 swapped with 0

source: A, B, C, D, E, F
picked: F, D, B, A, C, E

or, the source can be optionally shuffled, and each person can pick the person that is next in the list.