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

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

1 голос
/ 18 марта 2012

У меня есть несколько списков LInked, где количество связанных списков теоретически случайное, поскольку у меня может быть неопределенное количество.Количество элементов внутри каждого списка также может быть любым.По сути, я могу иметь произвольное количество списков со случайным количеством элементов, таких как:

Список 1

  • 1
  • 34
  • 91

Список 2

  • 6
  • 5
  • 94
  • 43
  • 245
  • 467

Список 3

  • 98
  • 39

Список 4

  • 11

И так далее ...

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

Например, элемент 1 в List 1 + элемент 5 в List 2 + элемент 2 в List 3 + элемент 1 в List 4 = определенное значение.Что я хочу, так это все комбинации списков, которые следуют за предыдущим, то есть это должен быть список 1 + список 2 + .... список n по порядку.

Кто-нибудь может подсказать, как этого можно достичь?

Ответы [ 2 ]

0 голосов
/ 18 марта 2012

Попробуйте это: 

const int SearchedValue = 296;
static List<LinkedList<int>> lists;
static Stack<int> indexes = new Stack<int>();

private static void Check(int sum, int listIndex)
{
    if (listIndex == lists.Count)
    {
        if (sum == SearchedValue)
        {
            Console.WriteLine("Found: " + String.Join(", ",
                indexes.Reverse().Select(i => i + 1).ToArray()));
        }
    }
    else
    {
        int i = 0;
        foreach (var value in lists[listIndex])
        {
            indexes.Push(i++);
            Check(sum + value, listIndex + 1);
            indexes.Pop();
        }
    }
}

public static void Main()
{
    var list1 = new LinkedList<int>();
    list1.AddLast(1);
    list1.AddLast(34);
    list1.AddLast(91);

    var list2 = new LinkedList<int>();
    list2.AddLast(6);
    list2.AddLast(5);
    list2.AddLast(94);
    list2.AddLast(43);
    list2.AddLast(245);
    list2.AddLast(467);

    var list3 = new LinkedList<int>();
    list3.AddLast(98);
    list3.AddLast(39);

    var list4 = new LinkedList<int>();
    list4.AddLast(11);

    lists = new List<LinkedList<int>>() { list1, list2, list3, list4 };

    Check(0, 0);
}
0 голосов
/ 18 марта 2012

Если вы говорите так: возьмите по одному int из каждого списка и посмотрите, равна ли их сумма чему-либо, тогда 

List<List<int>> lists = new List<List<int>>();
lists.Add(new List<int>() { 1, 34, 91});
lists.Add(new List<int>() { 6, 5, 94, 43, 245, 467 });
lists.Add(new List<int>() { 98, 39 });
lists.Add(new List<int>() { 11 });

var cp = CartesianProduct(lists);
int searchFor = 115;
foreach (var list in cp)
{
    if (list.Sum() == searchFor)
    {
        foreach (var i in list) Console.Write(i + " ");
    }
}

public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(IEnumerable<IEnumerable<T>> sequences)
{
    IEnumerable<IEnumerable<T>> emptyProduct = new IEnumerable<T>[] { Enumerable.Empty<T>() };
    return sequences.Aggregate(
        emptyProduct,
        (accumulator, sequence) =>
        {
            return accumulator.SelectMany(
                (accseq => sequence),
                (accseq, item) => accseq.Concat(new T[] { item })
            );
        }
    );
}
...