在 C# 中将对象列表排序为组

Question

我有一个 'tickets' 的列表，每个 'ticket' 包含三个数字。我会将所有门票分类，以便每组包含至少共享一个号码的门票。我如何将这些数据整理成最终的分组门票列表？

简而言之，这是最初的门票列表：

ticketA = { 1, 2, 3 }
ticketB = { 3, 4, 1 }
ticketC = { 5, 6, 7 }
ticketD = { 7, 8, 5 }
ticketE = { 9, 10, 11 }
ticketF = { 11, 1, 9 }

结果输出将是（为了便于视觉阅读而分成单独的行：

GroupedTickets = {
    <List>( ticketA, ticketB, ticketF ticketE )
    <List>( ticketC, ticketD )
}

下面是我一直用来找出解决方案的代码片段...

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace CrowdTool
{
    class Ticket
    {
        public string Name { get; set; }
        public List<int> Numbers { get; set; }
    }

    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
            Sort();
        }

        public void Sort()
        {
            List<Ticket> allTickets = new List<Ticket>();
            Ticket ticketA = new Ticket();
            ticketA.Numbers = new List<int> { 1, 2, 3 };
            allTickets.Add(ticketA);
            Ticket ticketB = new Ticket();
            ticketB.Numbers = new List<int> { 3, 4, 1 };
            allTickets.Add(ticketB);
            Ticket ticketC = new Ticket();
            ticketC.Numbers = new List<int> { 5, 6, 7 };
            allTickets.Add(ticketC);
            Ticket ticketD = new Ticket();
            ticketD.Numbers = new List<int> { 7, 8, 5 };
            allTickets.Add(ticketD);
            Ticket ticketE = new Ticket();
            ticketE.Numbers = new List<int> { 9, 10, 11 };
            allTickets.Add(ticketE);
            Ticket ticketF = new Ticket();
            ticketF.Numbers = new List<int> { 11, 1, 9 };
            allTickets.Add(ticketF);

            // variable to store groups of tickets
            List <List<Ticket>> GroupedTickets = new List<List<Ticket>>();
            foreach (var ticket in allTickets)
            {
                Console.WriteLine(ticket);
            }

        }
    }
}

Answer 1

因此，我采用了为所有票号制作所有组的方法。然后可以查询最终结果以获得您想要的结果。

我不得不将数据更改为适合处理的形式。我从这个开始：

var tickets = new Dictionary<string, int[]>()
{
    { "TicketA", new [] { 1, 2, 3 } },
    { "TicketB", new [] { 3, 4, 1 } },
    { "TicketC", new [] { 5, 6, 7 } },
    { "TicketD", new [] { 7, 8, 5 } },
    { "TicketE", new [] { 9, 10, 11 } },
    { "TicketF", new [] { 11, 1, 9 } },
};

现在我可以做这个查询了：

var groupedTickets =
    tickets
        .SelectMany(t => t.Value, (t, n) => new { t, n })
        .ToLookup(x => x.n, x => x.t)
        .OrderBy(x => x.Key)
        .Select(x => new
        {
            number = x.Key,
            tickets = x.Select(y => new
            {
                ticket = y.Key,
                numbers = y.Value
            }).ToList()
        })
        .ToList();

现在我得到了这样的结果：

但是要看清整个事情并不是一件容易的事，所以我重新格式化成这样：

1: TicketA = {1, 2, 3}, TicketB = {3, 4, 1}, TicketF = {11, 1, 9} 
2: TicketA = {1, 2, 3} 
3: TicketA = {1, 2, 3}, TicketB = {3, 4, 1} 
4: TicketB = {3, 4, 1} 
5: TicketC = {5, 6, 7}, TicketD = {7, 8, 5} 
6: TicketC = {5, 6, 7} 
7: TicketC = {5, 6, 7}, TicketD = {7, 8, 5} 
8: TicketD = {7, 8, 5} 
9: TicketE = {9, 10, 11}, TicketF = {11, 1, 9} 
10: TicketE = {9, 10, 11} 
11: TicketE = {9, 10, 11}, TicketF = {11, 1, 9}

您应该能够针对 groupedTickets 进行查询以准确获得您想要的内容。

例如，您可以这样做：

var output =
    groupedTickets
        .Where(x => x.tickets.Skip(1).Any())
        .Select(x => String.Join(", ", x.tickets.Select(y => y.ticket)))
        .OrderBy(x => x)
        .Distinct();

这会给你这个输出：

TicketA, TicketB 
TicketA, TicketB, TicketF 
TicketC, TicketD 
TicketE, TicketF

这与请求的输出非常相似，但为了显示目的而格式化。

根据问题编辑和下面的评论，这里是更新的解决方案。

var lookup =
    tickets
        .SelectMany(t => t.Value, (t, n) => new { t, n })
        .ToLookup(x => x.n, x => x.t.Value);

var groupedTickets =
    tickets
        .SelectMany(t => t.Value, (t, n) => new { t, n })
        .OrderBy(x => x.n)
        .ToLookup(x => x.n, x => x.t)
        .SelectMany(
            x => x.SelectMany(y => y.Value),
            (x, y) => new []
            {
                Tuple.Create(x.Key, y), 
                Tuple.Create(y, x.Key)
            })
        .SelectMany(t => t)
        .Where(t => t.Item1 != t.Item2)
        .Distinct();

Func<
    IEnumerable<Tuple<int, int>>,
    IEnumerable<Tuple<int, int>>,
    int,
    IEnumerable<Tuple<int, int>>> fold = null;
fold = (ts0, ts1, n) =>
    n == 0
        ? ts0
        : ts0
            .Concat(fold(
                ts0.Join(
                    ts1,
                    t0 => t0.Item2,
                    t1 => t1.Item1,
                    (t0, t1) => Tuple.Create(t0.Item1, t1.Item2)),
                ts1,
                n - 1))
            .Distinct()
            .ToArray();

var pairs = tickets.SelectMany(t => t.Value).Distinct().Count();

var final =
    fold(groupedTickets, groupedTickets, pairs)
        .OrderBy(x => x.Item1)
        .ThenBy(x => x.Item2)
        .GroupBy(x => x.Item1, x => x.Item2)
        .GroupBy(x => String.Join(",", x), x => x.Key)
        .Select(x => x.SelectMany(y => lookup[y]).Distinct());

这会产生两个不同的集合：

{ { 1, 2, 3 }, { 3, 4, 1 }, { 11, 1, 9 }, { 9, 10, 11 } }

{ { 5, 6, 7 }, { 7, 8, 5 } }

Answer 2

不是很优化，但这将完成工作，您可以改进它以提高效率（最明显的是使用 .Clear() 和 .AddRange()）。

var tickets = new Dictionary<string, List<int>>()
{
    { "TicketA", new List<int> { 1, 2, 3 } },
    { "TicketB", new List<int> { 3, 4, 1 } },
    { "TicketC", new List<int> { 5, 6, 7 } },
    { "TicketD", new List<int> { 7, 8, 5 } },
    { "TicketE", new List<int> { 9, 10, 11 } },
    { "TicketF", new List<int> { 11, 1, 9 } },
};

var newDict = new Dictionary<string, List<int>>(tickets);
foreach(var ticket in newDict)
{
    bool madeChange = true;
    while(madeChange)
    {
        var groupTickets = newDict.Where(t => t.Key != ticket.Key && t.Value.Intersect(ticket.Value).Any() && t.Value.Except(ticket.Value).Any()).ToList();
        madeChange = false;
        if (groupTickets.Any())
        {
            var newSet = groupTickets.SelectMany (t => t.Value).Union(ticket.Value).Distinct().ToList();                
            ticket.Value.Clear();
            ticket.Value.AddRange(newSet);
            foreach(var groupTicket in groupTickets)
            {
                groupTicket.Value.Clear();
                groupTicket.Value.AddRange(newSet);
            }
            madeChange = true;
        }
    }
}

newDict.GroupBy (t => String.Join(",", t.Value)).Dump();

本质上，它会查找所有具有匹配号码的门票。然后它会将号码插入 all 匹配的票中。重复此操作，直到找不到新数字。

在 C# 中将对象列表排序为组

Sort a list of objects into groups in C#

c#

list

nested-lists