Существует ли какая-либо функция c # для создания множества, замкнутого относительно объединения / пересечения - PullRequest
Новая
       29

Существует ли какая-либо функция c # для создания множества, замкнутого относительно объединения / пересечения

0 голосов
/ 01 апреля 2019

Я работаю над созданием списка строковых массивов, закрытых объединением, что означает, что объединение любых двух массивов должно присутствовать в полном списке.

Для этого я написал свой собственный код, который выполняет итерациюсписок строковых массивов и добавление новых строковых массивов, которые являются объединением двух существующих строковых массивов списка, только когда новый массив еще не существует в списке. 

public static List<string[]> UnionClosed(List<string[]> kstructure)
{        
    for (int i = 1; i < kstructure.Count; i++)
    {
        for (int j = i + 1; j < kstructure.Count; j++)
        {
            string[] kstate1 = kstructure[i];
            string[] kstate2 = kstructure[j];
            string[] unionStatesResult = kstate1.Union(kstate2).ToArray();
            int flag = 0;
            for (int k = 1; k < kstructure.Count; k++)
            {
                if (kstructure[k].Length == unionStatesResult.Length && kstructure[k].Intersect(unionStatesResult).Count()==kstructure[k].Length)
                {
                    flag = flag + 1;
                    break;
                }

            }
            if (flag==0)
            {
                kstructure.Add(unionStatesResult);
            }
        }
    }

    return (kstructure);
}

Ожидаемый результатчтобы получить список строковых массивов, которые закрыты при объединении.

Например, если я передам ввод: {{}, {"i1"}, {"i2"}, {"i3"}, {"i4"}, {"i1", "i2"}, {"i1", "i3"}, {"i1", "i4"}, {"i1", "i5"}, {"i2","i3"}, {"i2", "i4"}, {"i2", "i5"}, {"i1", "i2", "i3"}, {"i1", "i2", "i4"}, {" i1 "," i2 "," i5 "}, {" i1 "," i3 "," i4 "}, {" i1 "," i3 "," i5 "}, {" i2 ","i3", "i4"}, {"i2", "i3", "i5"}, {"i1", "i2", "i3", "i4"}, {"i1", "i2","i3", "i5"}, {"i1", "i3", "i4", "i5"}, {"i1", "i2", "i3", "i4", "i5"}}.

Тогда ожидаемый результат должен быть: {{}, {"i1"}, {"i2"}, {"i3"}, {"i4"}, {"i1", "i2"}, {"i1", "i3"}, {"i1", "i4"}, {"i1", "i5"}, {"i2", "i3"}, {"i2", "i4"}, {"i2", "i5"}, {"i3", "i4"}, {"i1", "i2", "i3"}, {"i1", "i2", "i4"}, {"i1", "i2", "i5"}, {"i1", "i3", "i4"}, {"i1", "i3", "i5"}, {"i1", "i4","i5"}, {"i2", "i3", "i4"}, {"i2", "i3", "i5"}, {"i2", "i4", "i5"}, {"i1"," i2 "," i3 "," i4 "}, {" i1 "," i2 "," i3 "," i5 "}, {" i1 "," i2 "," i4 "," i5 "}, {"i1", "i3", "i4", "i5"}, {"i2", "i3", "i4", "i5"}, {"i1", "i2", "i3","i4", "i5"}}.

Я получаю вывод, но проблема в том, что он очень медленный и не дает результата для большого числа строковых массивов.Я хотел, чтобы список размером 500 был закрыт при объединении, но этот код не дал мне результата. Я хочу знать, есть ли какая-либо функция c # для того же.В пакете R sets предусмотрены те же функции, что и в методе binary_closure ().Я хочу то же самое в C #.

1 Ответ

0 голосов
/ 01 апреля 2019

Вы можете сделать это немного более эффективным, используя HashSets для сравнения наборов, а не зацикливаясь.

Сначала вводится один из ваших комментариев: 

var input = new string[][]
{
    new string[0],
    new[] {"i1"},
    new[] {"i2"},
    new[] {"i3"},
    new[] {"i4"},
    new[] {"i1", "i2"},
    new[] {"i1", "i3"},
    new[] {"i1", "i4"},
    new[] {"i1", "i5"},
    new[] {"i2", "i3"},
    new[] {"i2", "i4"},
    new[] {"i2", "i5"},
    new[] {"i1", "i2", "i3"},
    new[] {"i1", "i2", "i4"},
    new[] {"i1", "i2", "i5"},
    new[] {"i1", "i3", "i4"},
    new[] {"i1", "i3", "i5"},
    new[] {"i2", "i3", "i4"},
    new[] {"i2", "i3", "i5"},
    new[] {"i1", "i2", "i3", "i4"},
    new[] {"i1", "i2", "i3", "i5"},
    new[] {"i1", "i3", "i4", "i5"},
    new[] {"i1", "i2", "i3", "i4", "i5"},
};

Нам понадобится такой помощник, который позволит нам сравнить HashSets на равенство: 

public class HashSetEqualityComparer<T> : IEqualityComparer<HashSet<T>>
{
    public static readonly HashSetEqualityComparer<T> Instance = new HashSetEqualityComparer<T>();

    public bool Equals(HashSet<T> x, HashSet<T> y)
    {
        if (ReferenceEquals(x, y))
            return true;
        if (ReferenceEquals(x, null) || ReferenceEquals(y, null))
            return false;

        return x.SetEquals(y);
    }

    public int GetHashCode(HashSet<T> obj)
    {
        // See http://stackoverflow.com/a/670068/1086121

        if (obj == null)
            throw new ArgumentNullException(nameof(obj));

        var comparer = obj.Comparer;
        int hash = 0;
        foreach (T element in obj)
        {
            hash = unchecked(hash + comparer.GetHashCode(element));
        }
        return hash;
    }
}

Затем код: 

var output = new HashSet<HashSet<string>>(HashSetEqualityComparer<string>.Instance);

for (int i = 0; i < input.Length; i++)
{
    // We need to make sure that every input item is in the output
    output.Add(new HashSet<string>(input[i]));

    for (int j = i + 1; j < input.Length; j++)
    {
        // It annoys me that we have to create a HashSet<string>(input[i]))twice
        var hashSet = new HashSet<string>(input[i]);
        hashSet.UnionWith(input[j]);
        output.Add(hashSet);
    }
}

Для каждой комбинации первой и второй строки мы создаем новый HashSet. Затем мы пытаемся добавить это HashSet<string> к нашему выводу HashSet, который является HashSet<HashSet<string>>. Наш пользовательский IEqualityComparer позаботится о том, чтобы он был добавлен, только если он еще не существует.

Мы также разделили коллекцию ввода и вывода, поэтому мы не начинаем обрабатывать вывод, как если бы он был вводом (что добавляет много ненужной работы).

...