0

I want to write a Christmas lottery algorithm. I want the people I enter in my hand to be matched with other people who are not themselves and printed on the screen. I wrote a code like the one below. But because it removes an element from the list every time, my program matches fewer people than the number of people entered.

How can I find a solution to this problem?

List<string> person = new List<string>() { "Joe","John","Chris","Henry","Tom","Patrick"};
        List<string> personCopy = new List<string>(person);

        for (int i = 0; i < person.Count; i++)
        {
            string person1 = person[i];
            Random rnd = new Random();
            var index = rnd.Next(personCopy.Count);
            while (i == index) {
                index = rnd.Next(personCopy.Count);
            }

            string person2 = personCopy[index];
            person.RemoveAt(i);
            personCopy.RemoveAt(index);
            Console.WriteLine("{0}  > {1}",person1,person2);
            
        }
İlyas Aruca
  • 1
  • 1
  • @JohnG First of all, thank you for your warning. I will think. But when I organize it this way, it gives only 3 matches instead of 6 different matches. – İlyas Aruca Dec 22 '20 at 23:54
  • Iterate backwards – Caius Jard Dec 23 '20 at 00:15
  • 2
    As an alternative... Shuffle your list (look for "shuffle random C#", or https://stackoverflow.com/questions/4412405/is-there-a-performance-difference-between-these-two-algorithms-for-shuffling-an). Then just associate the first person with the second, and so on until the last one (who you associate with the first). It's random and there's no chance that you associate one person with him/herself – Flydog57 Dec 23 '20 at 00:53
  • @Flydog57 that works and makes a good solution but doesn't make all solutions possible. Considering the problem as constructing a directed graph with people as nodes, we need to make each node have one incoming and outgoing edge. This ends up looking like a graph that has any number of disconnected simple cycles. that solution only creates the graphs that are a single cycle containing all the nodes. That being said, I think it's an excellent, simple solution and generally it's likely that someone doing this is fine with that caveat. It's how I would do it if I didn't _require_ other solutions. – moreON Dec 23 '20 at 01:08
  • 1
    The spec is *"I want the people I enter in my hand to be matched with other people who are not themselves and printed on the screen"*. This fits the spec (from what I can understand of it). The idea is not to consider every possible solution, it's to find one. This is effectively equivalent to dealing out two hands of cards from a shuffled deck and doing the matching based on the cards dealt. Using a shuffle is often the simplest solution to a _Random_ problem – Flydog57 Dec 23 '20 at 01:14
  • Taken literally, your question is too broad for Stack Overflow. However, a "Chrismas lottery" is fundamentally "drawing names from a hat", which in code is fundamentally "shuffling an array". Copy the list, shuffle the copy, then match each person from the original list with a person from the shuffled list (you'll want to skip an element if the current shuffled-list element is the person from the original list). ... – Peter Duniho Dec 23 '20 at 02:08
  • ... Alternatively, you can just match each person from the shuffled list with the next person in the shuffled list, matching the last person with the first person, if you require a "directed graph" solution where there is always only a single cycle. Either way, see duplicate for how to properly shuffle an array (or list). Use [this answer](https://stackoverflow.com/a/110570); the accepted answer is ridiculous. – Peter Duniho Dec 23 '20 at 02:08
  • @Flydog57 I don't think that I suggested that the idea presented doesn't fit the spec, just that it excludes some categories of solution that also fit the spec, and anyone using it should at least be aware of that. – moreON Dec 23 '20 at 02:29

2 Answers2

1

Shuffling would work well apart from the exclusivity issue (someone picking their own name).

Taking that into consideration, there are many ways to achieve this. This approach is "relatively" O(n) (linear) time complexity, though it's probably not the most efficient as it has to do an IndexOf when the pool gets to the length of 2. You don't want someone being their own secret Santa. Additionally, because that fact it wouldn't be the most even probability distribution ¯\_(ツ)_/¯

In short, don't use this in life or death Secret Santa situations.

Given

private static IEnumerable<(T, T)> FunkyLotto<T>(IEnumerable<T> source)
{
    var pool = source.ToList();
    var iteration = pool.ToList();
    foreach (var item in iteration)
    {
        int choice;
        if (pool.Count == 2 && pool.IndexOf(item) >= 0) 
            // special case when there is only 2 left, and there is a case for a duplicate
            choice = (pool.IndexOf(item) + 1) % pool.Count;
        else
            choice = _r.Next(0, pool.Count);
        choice = Equals(item, pool[choice]) ? (choice + 1) % pool.Count : choice;
        yield return (item, pool[choice]);
        pool.RemoveAt(choice);
    }
}

Usage

var list = new[] {"Joe", "John", "Chris", "Henry", "Tom", "Patrick"};

foreach (var result in FunkyLotto(list))
    Console.WriteLine(result);

Output

(Joe, Patrick)
(John, Chris)
(Chris, Joe)
(Henry, Tom)
(Tom, John)
(Patrick, Henry)

Full Demo Here

Or a more efficient variation which omits the memory copy of Remove, and does a reference check on the second last and last item in the pool.

[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static void Swap<T>(T[] array, int indexA, int indexB)
{
   var tmp = array[indexA];
   array[indexA] = array[indexB];
   array[indexB] = tmp;
}


private static IEnumerable<(T, T)> FunkyLotto2<T>(IEnumerable<T> source)
{
   var pool = source.ToArray();
   var iteration = pool.ToArray();
   var poolLength = pool.Length;

   foreach (var item in iteration)
   {
      int choice;
      if (poolLength == 2)
         choice = Equals(item, pool[0]) ? 1 : 0;
      else
      {
         choice = _r.Next(0, poolLength);
         choice = Equals(item, pool[choice]) ? (choice + 1) % poolLength : choice;
      }

      yield return (item, pool[choice]);
      Swap(pool, choice, poolLength - 1);
      poolLength--;
   }

}

And a slightly more efficient variation that uses an array parameter/result, and a pointer based stack allocated index array.

[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static unsafe void Swap(int* array, int indexA, int indexB)
{
   var tmp = array[indexA];
   array[indexA] = array[indexB];
   array[indexB] = tmp;
}

public static unsafe (T, T)[] FunkyLotto3<T>(T[] source)
{
   var pool = stackalloc int[source.Length];

   for (var i = 0; i < source.Length; i++)
      pool[i] = i;

   var result = new (T, T)[source.Length];

   var poolLength = source.Length;

   for (var index = 0; index < source.Length; index++)
   {
      int choice;
      if (poolLength == 2)
         choice = index == pool[0] ? 1 : 0;
      else
      {
         choice = _r.Next(0, poolLength);
         choice = index == pool[choice] ? (choice + 1) % poolLength : choice;
      }

      result[index] = (source[index], source[pool[choice]]);
      Swap(pool, choice, poolLength - 1);
      poolLength--;
   }

   return result;
}

And just because I can, Here some benchmarks

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.18363.1256 (1909/November2018Update/19H2)
AMD Ryzen 9 3900X, 1 CPU, 24 logical and 12 physical cores
.NET Core SDK=5.0.101
  [Host]        : .NET Core 5.0.1 (CoreCLR 5.0.120.57516, CoreFX 5.0.120.57516), X64 RyuJIT
  .NET Core 5.0 : .NET Core 5.0.1 (CoreCLR 5.0.120.57516, CoreFX 5.0.120.57516), X64 RyuJIT

Job=.NET Core 5.0  Runtime=.NET Core 5.0
Method N Mean Error StdDev Gen 0 Gen 1 Gen 2 Allocated
Original 100 6.209 us 0.0478 us 0.0448 us 0.7019 - - 5896 B
Modified 100 3.575 us 0.0301 us 0.0282 us 0.6943 - - 5824 B
Modified2 100 1.312 us 0.0041 us 0.0036 us 0.0267 - - 224 B
Original 1000 67.507 us 0.2349 us 0.2197 us 6.4697 0.1221 - 54640 B
Modified 1000 29.546 us 0.4567 us 0.4272 us 6.5002 0.1221 - 54568 B
Modified2 1000 13.413 us 0.0230 us 0.0215 us 0.2289 - - 2024 B
Original 10000 1,005.864 us 2.7138 us 2.5385 us 64.4531 7.8125 - 553608 B
Modified 10000 289.806 us 1.7409 us 1.5432 us 65.9180 10.2539 - 553536 B
Modified2 10000 130.208 us 0.4183 us 0.3493 us 2.1973 - - 20024 B

Full test code here

[SimpleJob(RuntimeMoniker.NetCoreApp50)]
[MemoryDiagnoser]

public class Test
{
   private byte[] data;

   [Params(100, 1000, 10000)] public int N;

   [GlobalSetup]
   public void Setup()
   {
      data = new byte[N];
      new Random(42).NextBytes(data);
   }

   private static readonly Random _r = new Random();

   private static IEnumerable<(T, T)> FunkyLotto<T>(IEnumerable<T> source)
   {
      var pool = source.ToList();
      var iteration = pool.ToList();
      foreach (var item in iteration)
      {
         int choice;
         if (pool.Count == 2 && pool.IndexOf(item) >= 0) // special case when there is only 2 left, and there is a case for a duplicate
            choice = (pool.IndexOf(item) + 1) % pool.Count;
         else
            choice = _r.Next(0, pool.Count);
         choice = Equals(item, pool[choice]) ? (choice + 1) % pool.Count : choice;
         yield return (item, pool[choice]);
         pool.RemoveAt(choice);
      }
   }


   [MethodImpl(MethodImplOptions.AggressiveInlining)]
   private static void Swap<T>(T[] array, int indexA, int indexB)
   {
      var tmp = array[indexA];
      array[indexA] = array[indexB];
      array[indexB] = tmp;
   }


   private static IEnumerable<(T, T)> FunkyLotto2<T>(IEnumerable<T> source)
   {
      var pool = source.ToArray();
      var iteration = pool.ToArray();
      var poolLength = pool.Length;

      foreach (var item in iteration)
      {
         int choice;
         if (poolLength == 2)
            choice = Equals(item, pool[0]) ? 1 : 0;
         else
         {
            choice = _r.Next(0, poolLength);
            choice = Equals(item, pool[choice]) ? (choice + 1) % poolLength : choice;
         }

         yield return (item, pool[choice]);
         Swap(pool, choice, poolLength - 1);
         poolLength--;
      }

   }


   [MethodImpl(MethodImplOptions.AggressiveInlining)]
   private static unsafe void Swap(int* array, int indexA, int indexB)
   {
      var tmp = array[indexA];
      array[indexA] = array[indexB];
      array[indexB] = tmp;
   }

   public static unsafe (T, T)[] FunkyLotto3<T>(T[] source)
   {
      var pool = stackalloc int[source.Length];

      for (var i = 0; i < source.Length; i++)
         pool[i] = i;

      var result = new (T, T)[source.Length];

      var poolLength = source.Length;

      for (var index = 0; index < source.Length; index++)
      {
         int choice;
         if (poolLength == 2)
            choice = index == pool[0] ? 1 : 0;
         else
         {
            choice = _r.Next(0, poolLength);
            choice = index == pool[choice] ? (choice + 1) % poolLength : choice;
         }

         result[index] = (source[index], source[pool[choice]]);
         Swap(pool, choice, poolLength - 1);
         poolLength--;
      }

      return result;
   }

   [Benchmark]
   public (byte, byte)[] Original() => FunkyLotto(data).ToArray();

   [Benchmark]
   public (byte, byte)[] Modified() => FunkyLotto2(data).ToArray();

   [Benchmark]
   public (byte, byte)[] Modified2() => FunkyLotto3(data);
}
halfer
  • 19,824
  • 17
  • 99
  • 186
TheGeneral
  • 79,002
  • 9
  • 103
  • 141
0

This occurs because you are removing an element from person while iterating up over its index.

In the first iteration where i=0 you remove the element at 0 which shifts everything down (i.e. old element at 1 is now at 0, element from 2 is at 1, etc).

After this, you increment i so that its value is now 1. Now in the next iteration you'll take element 1 (which was previously at 2). This has skipped the element originally at position 1. This continues happening, with each iteration skipping another element.

The solution to this is fairly straightforward, but it's probably more helpful to you if you figure it out yourself based on this knowledge. If you really need the ways to do this spelled out clearly, I can do that - but I would still strongly encourage working out how yourself first. Programming things will involve running into small problems like this and learning to solve them on your own is important.

The next problem that you'll probably run in to is that you're removing different elements from person and personCopy so the indexes of the same element won't actually match up. Because of this the test that elements are "different" isn't testing that at all, and when you get to the final element, I expect that solution will cause the loop selecting a random element to never terminate after you fix your current problem. There's a different approach that I think makes more sense than your current approach, but you'll probably learn more if you fix what you currently have first rather than blindly copying something that I say will work better.

moreON
  • 1,977
  • 17
  • 19