Как быстро выбрать все сочетания из массива (комбинаторика)? День добрый! Стандартная задача. Есть массив [1,2,3], есть n = 2. Нужно выбрать все сочетания из массива по n. То есть должны получить: [[1,2], [1,3], [2, 3]].
Можно, конечно, пройтись циклом в цикле, но при увеличении размера массива и n вычисления будут выполняться слишком долго ввиду большого количества (> 66%) отсева ненужных сочетаний.
Таки вопрос, как грамотно это реализовать?
Как быстро выбрать все сочетания из массива (комбинаторика)? День добрый! Стандартная задача. Есть массив [1,2,3], есть n = 2. Нужно выбрать все сочетания из массива по n. То есть должны получить: [[1,2], [1,3], [2, 3]].
Можно, конечно, пройтись циклом в цикле, но при увеличении размера массива и n вычисления будут выполняться слишком долго ввиду большого количества (> 66%) отсева ненужных сочетаний.
Таки вопрос, как грамотно это реализовать?
Можно, конечно, пройтись циклом в цикле, но при увеличении размера массива и n вычисления будут выполняться слишком долго ввиду большого количества (> 66%) отсева ненужных сочетаний.
Таки вопрос, как грамотно это реализовать?
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Есть несколько способов решения данной задачи более эффективным способом, не используя перебор всех возможных комбинаций.
Один из способов - использовать рекурсивный подход. Можно рассматривать каждый элемент массива как "включенный" или "не включенный" в текущую комбинацию. Таким образом, можно генерировать все возможные сочетания за линейное время.
Вот пример кода на Python:
def combine(nums, n):def backtrack(start, curr):
if len(curr) == n:
result.append(curr[:])
return
for i in range(start, len(nums)):
curr.append(nums[i])
backtrack(i + 1, curr)
curr.pop()
result = []
backtrack(0, [])
return result
nums = [1, 2, 3]
n = 2
print(combine(nums, n))
Этот код будет генерировать все сочетания из массива по n за линейное время.