Комбинация списка списков, так что каждая комбинация имеет уникальные элементы - PullRequest
Новая
       19

Комбинация списка списков, так что каждая комбинация имеет уникальные элементы

0 голосов
/ 01 июня 2018

Хорошо, у меня есть список списков, как и в заголовке, и я хочу создать комбинации из k списков, в которых каждый список имеет элементы, отличные от остальных.

Пример :

У меня есть следующий список списков: 

{ {1,2,3} , {1,11} , {2,3,6} , {6,5,7} , {4,8,9} }

Допустимая 3-размерная комбинация этих списков может быть: 

{ {1,11}, {4,8,9} ,{6,5,7} }

Это только ОДИН издействительные комбинации, которые я хочу вернуть, это список всех допустимых комбинаций списков K.

Недопустимая комбинация будет: 

{ {1,11} ,{2, 3, 6}, {6, 5, 7} }

, поскольку элемент 6 присутствует ввторой и третий список.

У меня уже есть код, который делает это, но он просто находит все возможные комбинации и проверяет, являются ли они действительными, прежде чем добавить его в список окончательных результатов.Поскольку этот список списков довольно велик (153 списка), когда K становится больше, время, потраченное на него, тоже смехотворно велико (при K = 5 это занимает у меня около 10 минут.)

Я хочу посмотреть, есть лиэффективный способ сделать это.Ниже приведен мой текущий код (списки, которые я хочу объединить, являются атрибутом класса Item): 

public void recursiveComb(List<Item> arr, int len,  int startPosition, Item[] result)
{
    if (len == 0)
    {            
        if (valid(result.ToList()))
        {                
          //Here I add the result to final list

          //valid is just a function that checks if any list has repeated elements in other  
        }            
        return;
    }

    for (int i = startPosition; i <= arr.Count - len; i++)
    {       
        result[result.Length - len] = arr[i];
        recursiveComb(arr, len - 1,  i + 1, result);
    }
}

Ответы [ 3 ]

0 голосов
/ 01 июня 2018

Если я правильно понял ваш код, то вы передаете каждую list<int> из своего ввода в recursiveComb() функцию.который выглядит следующим образом 

for(int i = 0; i < inputnestedList.Count; i++)
{
    recursiveComb();
   // Inside of recursiveComb() you are using one more for loop with recursion.
   // This I observed from your first parameter i.e. List<int>
}

Поправьте меня, если я ошибаюсь

Это приводит к сложности времени больше, чем O (n ^ 2)

Вот мое простейшее решение с двумя forloops без рекурсии. 

List<List<int>> x = new List<List<int>>{ new List<int>(){1,2,3} , new List<int>(){1,11} , new List<int>(){2,3,6} , new List<int>(){6,5,7} , new List<int>(){4,8,9} };
List<List<int>> result = new List<List<int>>();
var watch = Stopwatch.StartNew();

for (int i = 0; i < x.Count;i++)
{
    int temp = 0;
    for (int j = 0; j < x.Count; j++)
    {
        if (i != j && x[i].Intersect(x[j]).Any())
            temp++;
    }

    // This condition decides, that elements of  ith list are available in other lists
    if (temp <= 1)
        result.Add(x[i]);
}
watch.Stop();
var elapsedMs = watch.Elapsed.TotalMilliseconds;

Console.WriteLine(elapsedMs);

Теперь, когда я печатаю время выполнения, вывод будет 

Execution Time: 11.4628

Проверить выполнениевремя вашего кода.Если время выполнения вашего кода выше моего, то вы можете считать его эффективным кодом

Подтверждение кода: DotNetFiddler

Счастливое кодирование

0 голосов
/ 01 июня 2018

Если я правильно понял вашу проблему, то это будет работать: 

 /// <summary>
        /// Get Unique List sets
        /// </summary>
        /// <param name="sets"></param>
        /// <returns></returns>
        public List<List<T>> GetUniqueSets<T>(List<List<T>> sets )
        {
            List<List<T>> cache = new List<List<T>>();

            for (int i = 0; i < sets.Count; i++)
            {
                // add to cache if it's empty
                if (cache.Count == 0)
                {
                    cache.Add(sets[i]);
                    continue;
                }
                else
                {
                    //check whether current item is in the cache and also whether current item intersects with any of the items in cache
                    var cacheItems = from item in cache where (item != sets[i] && item.Intersect(sets[i]).Count() == 0) select item;

                    //if not add to cache
                    if (cacheItems.Count() == cache.Count)
                    {
                        cache.Add(sets[i]);
                    }

                }
            }


            return cache;

        }

Протестировано, это быстро и потребовалось 00: 00: 00.0186033 для поиска наборов.

0 голосов
/ 01 июня 2018

Используйте HashSet https://msdn.microsoft.com/en-us/library/bb359438(v=vs.110).aspx для отслеживания различных элементов при построении вывода из кандидатов во входном списке списков / кортежей

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

Объект hashset эффективно поддерживает реестр отдельных элементов в вашем принятом списке кортежей.

...