Most efficient way to distribute non unique elements across multiple lists

user_984349 0
Viewed 120

Suppose that I have a list of integer or whatever

List<int> motherlist = { 1, 1, 2, 5, 7, 2, 2, 2, 6, 1 }

Console.WriteLine(children.Count); // 10

I would like to find all duplicates and not remove them from the list but to distribute them across other lists so the final count of all childrens should be the same as motherlist:

List<List<int>> children = { { 1, 2, 5, 7, 6 }, { 1, 2 }, { 1, 2 }, { 2 }}

Console.WriteLine(children.Sum(l => l.Count())); // 10 same as mother

I tried so far a brute force approach by looping through all elements of mother, comparing the elements with all other elements and to check for duplicates, If duplicate found I add it to a list of buckets (List of Lists) and so forth until the last elements. But the brute force approach takes 7 CPU seconds for only a mother list of 300 items. I imagine that if I had 1000 items this would take forever.

Is there a faster way to do this in C# .NET ?

optimization c#
4 Answers

I suggest grouping duplicates and then loop taking into account size of the groups:

public static IEnumerable<List<T>> MyDo<T>(IEnumerable<T> source, 
                                           IEqualityComparer<T> comparer = null) {
  if (null == source)
    throw new ArgumentNullException(nameof(source));

  var groups = new Dictionary<T, List<T>>(comparer ?? EqualityComparer<T>.Default);

  int maxLength = 0;

  foreach (T item in source) {
    if (!groups.TryGetValue(item, out var list)) 
      groups.Add(item, list = new List<T>());
    
    list.Add(item);
    maxLength = Math.Max(maxLength, list.Count);
  }
  
  for (int i = 0; i < maxLength; ++i) {
    List<T> result = new List<T>();

    foreach (var value in groups.Values)
      if (i < value.Count)
        result.Add(value[i]);

    yield return result;
  }
}

Demo:

  int[] source = new int[] { 1, 1, 2, 5, 7, 2, 2, 2, 6, 1 };

  var result = MyDo(source).ToList();

  string report = string.Join(Environment.NewLine, result
    .Select(line => $"[{string.Join(", ", line)}]"));

  Console.Write(report);

Outcome:

[1, 2, 5, 7, 6]
[1, 2]
[1, 2]
[2]

Stress Demo:

  Random random = new Random(1234); // seed, the results to be reproducible

  // We don't want 1000 items be forever; let's try 1_000_000 items
  int[] source = Enumerable
    .Range(1, 1_000_000)
    .Select(x => random.Next(1, 1000))
    .ToArray();

  Stopwatch sw = new Stopwatch();

  sw.Start();

  var result = MyDo(source).ToList();

  sw.Stop();

  Console.WriteLine($"Time: {sw.ElapsedMilliseconds} ms");

Outcome: (may vary from workstation to workstation)

  Time: 50 ms
user_23194070

I would GroupBy the elements of the list, and then use the count of elements to know the number of sublists an element has to be added in

List<int> motherlist = new List<int> { 1, 1, 2, 5, 7, 2, 2, 2, 6, 1 };
var childrens = motherlist.GroupBy(x => x).OrderByDescending(x => x.Count());
var result = new List<List<int>>();

foreach (var children in childrens)
{
    for (var i = 0; i < children.Count(); i++)
    {
        if (result.Count() <= i) result.Add(new List<int>());

        result[i].Add(children.Key);
    }
}
Console.WriteLine("{");
foreach (var res in result)
{
    Console.WriteLine($"\t{{ { string.Join(", ", res) } }}");
}
Console.WriteLine("}");

This outputs :

{
    { 2, 1, 5, 7, 6 }
    { 2, 1 }
    { 2, 1 }
    { 2 }
}
user_83985490

Just a quick shot, but it seems to work quite well...

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp2
{
    class Program
    {
        static void Main(string[] args)
        {
            List<int> motherlist = new List<int> { 1, 1, 2, 5, 7, 2, 2, 2, 6, 1 };

            var rnd = new Random(1);

            for (int i = 0; i < 1000; i++)
            {
                motherlist.Add(rnd.Next(1, 200));
            }

            var resultLists = new List<IEnumerable<int>>();

            while (motherlist.Any())
            {
                var subList = motherlist.Distinct().OrderBy(x => x).ToList();
                subList.ForEach(x => motherlist.Remove(x));
                resultLists.Add(subList);
            }
        }
    }
}
user_36912680

You can use a Dictionary<int, int> to keep track of the number of occurrences of each element and build the child lists in a single iteration with O(n) time complexity(most of the time) and without any LINQ:

var motherlist = new List<int>() { 1, 1, 2, 5, 7, 2, 2, 2, 6, 1 };
var counts = new Dictionary<int, int>();
var children = new List<List<int>>();
foreach(var element in motherlist)
{
    counts.TryGetValue(element, out int count);
    counts[element] = ++count;
    if (children.Count < count)
    {
        children.Add(new List<int>() { element });
    }
    else
    {
        children[count - 1].Add(element);
    }
}

OUTPUT

{ 1, 2, 5, 7, 6 }
{ 1, 2 }
{ 2, 1 }
{ 2 }
user_114551050
Related