6
\$\begingroup\$

The task is to create two random teams from a list of players.

Given an example of players = ["John", "Mike", "Alice", "Bob"]

One example random team would be:

team1 = ["Mike", "Alice"];
team2 = ["John", "Bob"];

This is my solution but I'm not sure how efficient it is because random can create same number for a number of times.

The question to separate equally and randomly without repeating the same player.

using System;
using System.Collections.Generic;

public class Program
{

    public static void Main(string[] args)
    {
        Random rnd = new Random();
        var numbers = new List<int>();

        var ilkListe = new List<int>();

        var ikinciListe = new List<int>();

        numbers.Add(1);
        numbers.Add(2);
        numbers.Add(3);
        numbers.Add(4);
        numbers.Add(5);
        numbers.Add(6);
        numbers.Add(7);
        numbers.Add(8);
        numbers.Add(9);
        numbers.Add(10);
        Console.WriteLine("LIST 1: " + numbers.Count);

        do {
            int sayi = numbers[rnd.Next(numbers.Count)];
            if (!(ilkListe.Contains(sayi))) {
                Console.WriteLine(sayi);
                ilkListe.Add(sayi);
            }
        }

        while (ilkListe.Count < numbers.Count / 2);

        Console.WriteLine("Ikinci liste");

        do {
            int sayi = numbers[rnd.Next(numbers.Count)];
            if (!(ilkListe.Contains(sayi)) && !(ikinciListe.Contains(sayi))) {
                Console.WriteLine(sayi);
                ikinciListe.Add(sayi);
            }
        }

        while (ikinciListe.Count < numbers.Count / 2);
    }
}
\$\endgroup\$
  • 4
    \$\begingroup\$ Thanks for updating. I've looked through your code and it does seem like it does what it is supposed to do but in an inefficient way, so you've come to the right place. \$\endgroup\$ – Simon Forsberg Jul 31 at 19:31
  • \$\begingroup\$ @dfhwze it does not matter actually. The idea is same. I was just trying to simulate the task in an online editor. \$\endgroup\$ – esilik Jul 31 at 19:43
  • 7
    \$\begingroup\$ I don't have time today to write an answer, but you should consider shuffling the array, then dividing into the two teams. That completes in deterministic time, whereas there's no guarantee that the presented algorithm will terminate. \$\endgroup\$ – Toby Speight Jul 31 at 21:46
  • \$\begingroup\$ @Toby Speight thank you. "shuffling the array" do too much. \$\endgroup\$ – esilik Jul 31 at 22:26
  • \$\begingroup\$ Actually: better than shuffling is simply to iterate through the elements, and assign each to a team (with 50% probability) until one of the teams is fully populated (effectively, a partial shuffle). \$\endgroup\$ – Toby Speight Aug 1 at 3:06
5
\$\begingroup\$

While your new solution does look somewhat better than the original, I would suggest that constantly removing elements from the list can be quite expensive. I would suggest shuffling or randomly sorting the list then simply divvying up the players to the teams.

Also you're still putting the implementation in Main, instead of calling a method.

Instead of hardcoding everything for 2 teams I would be in favor of allowing any number of teams as long as it's an exact divisor of the number of players.

Instead of multidimensional lists, I would use a Dictionary where the Key is the name of the team and the players names are in a list.

It could look something like this:

public static Dictionary<int,List<T>> MakeTeams<T>(this List<T> playerList, int numTeams)
{

    int count = playerList.Count();
    if(count % numTeams != 0)
    {
        throw new ArgumentException("The number of players must be a multiple of numTeams to get even distribution of players");
    }
    var randomList = playerList.OrderBy(x => Guid.NewGuid()).ToList();
    var teams = (from int i in Enumerable.Range(0, count)
                 let item = randomList[i]
                 group item by (i % numTeams) into team
                 select team).ToDictionary(team => team.Key, team => team.ToList());

    return teams;
}

This simply uses a number for the team name. If you wanted to get fancier with it you could add a string array of team names to use instead:

public static Dictionary<string, List<T>> MakeTeams<T>(this List<T> playerList, int numTeams, string[] teamNames)
{
    if(teamNames.Length < numTeams)
    {
        throw new ArgumentException("The number of team names must be equal to or greater than numTeams");
    }
    int count = playerList.Count();
    if (count % numTeams != 0)
    {
        throw new ArgumentException("The number of players must be a multiple of numTeams to get even distribution of players");
    }
    var randomList = playerList.OrderBy(x => Guid.NewGuid()).ToList();
    var teams = (from int i in Enumerable.Range(0, count)
                 let item = randomList[i]
                 group item by (i % numTeams) into team
                 select team).ToDictionary(team => teamNames[team.Key], team => team.ToList());

    return teams;
}
\$\endgroup\$
  • 6
    \$\begingroup\$ Couple of things: Make the dictionary keys a generic type as well. Don't ask how many teams there are, just count how many keys you were given. Don't use random-guid-sort to shuffle (lengthy discussion in comments). \$\endgroup\$ – ShapeOfMatter Aug 1 at 0:44
  • \$\begingroup\$ I've seen OrderBy(x => Guid.NewGuid()) repeatedly and it's an awful solution to shuffle a list. Not only is it non-intuitive, it's also slow, not guaranteed to work at all (there's no guarantee what type of GUID is created, the GUID only has to be unique) and worst of all it's subtly broken. A fisher yates shuffle is trivial to implement so don't skimp to save a few lines of code. (Using a proper PRNG for your random shuffle property is also wrong, so no just stick with fisher yates) \$\endgroup\$ – Voo Aug 2 at 14:22
18
\$\begingroup\$

Review

  • Don't use the main entry point to implement an algorithm. Create a method instead.
  • Think about how to allow this method to be usable for all kinds of types, not just integers. You have implemented the algorithm for integers, yet you show an example with strings.
  • When creating an algorithm, surely you have made some unit tests, at least for the happy paths. Feel free to include them in the question.
  • Use clear variable names, and stick to one written language.
  • Don't mix algorithm logic with Console output.

A possible method signature could be:

public static IEnumerable<IEnumerable<T>> SplitRandom<T>(
    this IEnumerable<T> source, int targetCount)
{
    // .. algorithm implementation
}

Called as..

var names = new [] { "John", "Mike", "Alice", "Bob" };
var teams = names.SplitRandom(2);

Or as..

var numbers = Enumrable.Range(1, 10);
var numberGroups = numbers.SplitRandom(2);
\$\endgroup\$
  • \$\begingroup\$ I don't think IEnumerable is the correct signature. You need the length of the data and also to shuffle the data, too. So what you need is actually IReadOnlyCollection<T>. And the result is IReadOnlyList<IReadOnlyList<T>> (I'm not sure about the output type). \$\endgroup\$ – Akangka Aug 1 at 22:21
5
\$\begingroup\$

All of dfhwze's points are spot-on, and the only thing I can think of to add to his type-signature is that if you're unfamiliar with all of the syntax he's using that's ok.
(If you want to learn the stuff in question, search for "inheritance" (or "interface"), "generics", "extension methods", and possibly "generators" or "yield".)

Regarding your actual algorithm:

The big red flag that your current algorithm isn't good is that you have two nearly-identical loops. That they happen to be while loops is a small red flag, which you noticed indirectly when you noted that rnd.Next() can yield duplicates.

The algorithm you probably want is to first shuffle your source list, and then take sequential runs from it as needed. Stack Exchange gives us usable implementations of both those steps. Only copy-paste them if you understand how they work and you want those exact methods lying around your code-base; most of the time it's better to re-write these things so that you're making the "details" decisions for yourself.

There are some details that probably matter, like whether or not the original order of the elements needs to be preserved, or what should happen if the source list isn't evenly divisible into the number of buckets in question.

And once you've resolved all of that, since you asked about efficiency, we can return to dfhwze's function signature. Specifically, this IEnumerable<T> source is taken as an enumerable collection; the Fisher–Yates shuffle shuffles a list in place. It's very tempting to change the argument to this IList<T> source, so that if the calling context already has a list, we're can just use that one instead of calling source.ToList(). If you do it that way you'll have written a function that returns a computed value and modifies the contents of its argument; strongly consider not doing that.

\$\endgroup\$
  • \$\begingroup\$ If you are looking for an efficient implementation I would probably just loop through the list once and randomly assign each player to one team, until one team is full, then all remaining players go to the other team. No shuffling and no reallocations. \$\endgroup\$ – Falco Aug 1 at 12:54
  • 3
    \$\begingroup\$ @Falco: Your suggestion might work for the OP and it might not. Consider this... There are 100 players listed alphabetically. Using your suggestion, Xavier and Zak will almost always be on the same team, a violation of the OP's "random teams" condition. \$\endgroup\$ – James Aug 1 at 14:11
  • \$\begingroup\$ You are right, most simpler solutions have unwanted correlations between some players landing in the same team depending on position in the list. An inplace-shuffle and then taking two sub-lists is probably the best way. \$\endgroup\$ – Falco Aug 1 at 16:03
0
\$\begingroup\$
using System;
using System.Collections.Generic;

public class Program
{

    public static void Main(string[] args)
    {
        List<string> players = new List<string>(new string[]{ "John", "Mike", "Kate", "Michael" });

        List<string> randomPlayers = ShuffleList<string>(players);

        List<string> team1 = randomPlayers.GetRange(0, (randomPlayers.Count - 1) / 2);
        List<string> team2 = randomPlayers.GetRange((randomPlayers.Count - 1) / 2, (randomPlayers.Count - 1));
    }

    public static List<E> ShuffleList<E>(List<E> inputList)
    {
     List<E> randomList = new List<E>();

     Random r = new Random();
     int randomIndex = 0;
     while (inputList.Count > 0)
     {
          randomIndex = r.Next(0, inputList.Count); //Choose a random object in the list
          randomList.Add(inputList[randomIndex]); //add it to the new, random list
          inputList.RemoveAt(randomIndex); //remove to avoid duplicates
     }

     return randomList; //return the new random list
    }
}

After a little search of "array shuffle keyword", rewrite the code.

\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to Code Review! Just a friendly reminder that self-answers should still be in the form of a review - you're expected to explain what's wrong with the original code, rather than simply posting a replacement. You'll find more guidance in the help center (sorry, I don't have time to look it up for you right now - I'm in the middle of a very busy spell). \$\endgroup\$ – Toby Speight Aug 1 at 3:10
  • \$\begingroup\$ A quick and easy way I sometimes use to shuffle a list, is to simply order it by NewGuid. So you could do randomPlayers = players.OrderBy(x => Guid.NewGuid()); \$\endgroup\$ – dbso Aug 1 at 5:43
  • \$\begingroup\$ @dbso; I won't argue that order-by-guid isn't quick and easy to write, but it's too hacky to inline without comment, and if you're going to have a designated method for the task then you should do it correctly. The comments on this answer discuss your suggestion, and the other answers there show better ways of shuffling in place. \$\endgroup\$ – ShapeOfMatter Aug 1 at 14:47
  • \$\begingroup\$ That's an unnecessarily O(n^2) implementation of a linear problem. The splitting up afterwards is also incorrect. \$\endgroup\$ – Voo Aug 3 at 8:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.