Как сгруппировать массив char/string с UNION?

Question

У меня есть двумерный массив гольца, названный Letters [] []

Letters[0][0] = A 
     [0][1] = B 

Letters[1][0] = C 
     [1][1] = D 

Letters[2][0] = B 
     [2][1] = A 
     [2][2] = F 

Letters[3][0] = I 
     [3][1] = F 
     [3][2] = J 

Мне нужно сгруппировать его, так что это будет что-то вроде этого:

group[0] [0] = A 
group[0] [1] = B 
group[0] [2] = F 
group[0] [3] = I 
group[0] [4] = J 

group[1] [0] = C 
group[1] [1] = D 

Моя логика до сих пор для моя проблема заключается в проверке всех элементов с другими элементами. Если оба элемента являются одной и той же буквой, они группируются вместе со всеми другими элементами массива без двойных/дублированных элементов. Но я не уверен в использовании C# Linq Union или, возможно, только для стандартного доступа к массиву.

Как мне сделать, чтобы сгруппировать его наилучшим образом? Или есть другие решения для этого?

Answer 1

Я думаю, что чистое решение LINQ будет чрезмерно сложным. Это не так (если я правильно понимаю вашу спецификацию) - простая операция объединения. Вы хотите объединение на основе непустых пересечений. Это означало бы сначала переупорядочить данные, чтобы LINQ мог выполнить соединение, чтобы найти данные, которые соответствуют, и поскольку LINQ будет только присоединяться к равенству, выполнение этого при сохранении исходной информации группировки приведет к синтаксису, который будет больше проблема, чем это стоит, ИМХО.

Вот подход, не LINQ, который работает для примера вы дали:

static void Main(string[] args) 
{ 
    char[][] letters = 
    { 
     new [] { 'A', 'B' }, 
     new [] { 'C', 'D' }, 
     new [] { 'B', 'A', 'F' }, 
     new [] { 'I', 'F', 'J' }, 
    }; 

    List<HashSet<char>> sets = new List<HashSet<char>>(); 

    foreach (char[] row in letters) 
    { 
     List<int> setIndexes = Enumerable.Range(0, sets.Count) 
     .Where(i => row.Any(ch => sets[i].Contains(ch))).ToList(); 

     CoalesceSets(sets, row, setIndexes); 
    } 

    foreach (HashSet<char> set in sets) 
    { 
     Console.WriteLine("{ " + string.Join(", ", set) + " }"); 
    } 
} 

private static void CoalesceSets(List<HashSet<char>> sets, char[] row, List<int> setIndexes) 
{ 
    if (setIndexes.Count == 0) 
    { 
     sets.Add(new HashSet<char>(row)); 
    } 
    else 
    { 
     HashSet<char> targetSet = sets[setIndexes[0]]; 

     targetSet.UnionWith(row); 

     for (int i = setIndexes.Count - 1; i >= 1; i--) 
     { 
      targetSet.UnionWith(sets[setIndexes[i]]); 
      sets.RemoveAt(setIndexes[i]); 
     } 
    } 
} 

Это создает наборы входных данных путем сканирования ранее идентифицированных наборов, чтобы найти те, которые текущая строка данные пересекаются с, а затем объединяют эти множества в один набор, содержащий все члены (ваша спецификация, похоже, налагает транзитивное членство и hellip, т.е. если одна буква соединяет множества A и B, а другая буква объединяет множество B и C, вы хотите, чтобы A , B и C все объединены в один набор).

Это не оптимальное решение, но оно читаемо. Вы могли бы избежать поиска O (N^2), поддерживая Dictionary<char, int>, чтобы отобразить каждый символ в набор, который содержит его. Затем вместо сканирования всех наборов это простой поиск каждого символа в текущей строке, чтобы создать список установленных индексов. Но есть гораздо больше «домашнего» кода, который подходит к этому подходу; Я бы не стал ее реализовывать таким образом, если вы не найдете доказанной проблемы с производительностью, сделав ее более простым способом.

К слову: у меня есть смутное воспоминание. Я видел этот тип вопроса до переполнения стека, т. Е. Такого рода транзитивное объединение множеств. Я искал вопрос, но не мог его найти. Возможно, вам повезет больше, и вы найдете дополнительную полезную информацию с этим вопросом и его ответами.