Помощь в выборе алгоритма поиска по массиву или списку

Question

всем привет Вопрос-задача из реальной жизни: у меня есть сочетания чисел и описания к ним. в сочетании может быть от 2 до 5 чисел. Дается массив из 9 чисел от 1 до 50. Как лучше всего орuанизовать перебор массива, чтобы проверить все сочетания и как хранить сочетания вместе с их описаниями? (С#)

За любые подсказки буду благодарен

пример: даются числа [1, 2, 3, 4, 5, 6, 7, 8, 8] есть сочетания чисел: 1-2-4, 1-8, 8-8, 4-8-8 и программа должна проходить по списку и смотреть: (для первой комбинации) - есть ли в массиве число 1, число 2 и число 4? (для третьей) - есть ли в массиве две 8-ки? и т.д. и если есть - должен выводиться определённый текст (как вот эти сочетания/комбинации хранить - тоже вопрос)

я сделал решение, которое использует вложенные циклы, но сами понимаете, что там время - O(N^5) Заранее спасибо

Answer 1

Сочетания хранить несложно - как пары значение:количество. Можно как словарь, можно просто как массив пар.

Набор чисел нужно обработать, приведя к подобному виду. Опять же - можно использовать словарь, можно массив пар, а то и просто массив длиной 51, содержащий количество чисел, соответствующих индексу.

Answer 2

Вот пример, который по идее проверяет наличие вашего паттерна в данных за линейное время

public bool Check(int[] data, int[] pattern)
{
    int dataInd = 0;
    int patInd = 0;
    
    while(dataInd < data.Length)
    {
        if (patInd >= pattern.Length) return true;
        if (pattern[patInd] == data[dataInd]) patInd++;
        dataInd++;
    }
    
    return patInd >= pattern.Length;    
}

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

Проверка (тут я уже сортированные массивы использую)

    Console.WriteLine(Check(new[] {1, 2, 3, 4, 5, 6, 7, 8, 8 }, new[] {1, 2, 4}));
    Console.WriteLine(Check(new[] {1, 2, 3, 4, 5, 6, 7, 8, 8 }, new[] {1, 8}));
    Console.WriteLine(Check(new[] {1, 2, 3, 4, 5, 6, 7, 8, 8 }, new[] {8, 8}));
    Console.WriteLine(Check(new[] {1, 2, 3, 4, 5, 6, 7, 8, 8 }, new[] {4, 8, 8}));
    Console.WriteLine(Check(new[] {1, 2, 3, 4, 5, 6, 7, 8, 8 }, new[] {3, 4, 4}));

Вывод

True
True
True
True
False

Как хранить массивы и паттерны - тут зависит от того, сколько их у вас. Можно просто в таком виде и хранить - как массивы. Если это проблема, то опишите конрктно что за проблема с хранением. Перевести массивы в пары ключ-значение не сложно, но это максимум в 5 раз сократит занимаемое место (максиммум, в среднем скорее всего разница будет не особо большая)

БЛОГ НА HUSL

Помощь в выборе алгоритма поиска по массиву или списку

Ответы (2 шт):