@mikhle19

Как перебрать все комбинации по m элементов из n объектов, без повторения?

Добрый день. Задача по постановке простая. Есть массив из n элементов([1...9]), m - число элементов в одной комбинации. Основное ограничение : нельзя, чтобы в разных комбинациях повторялись более чем один элемент.
К примеру:
Для массива 1 2 3 5 4 6 7 8 9
Надо получить следующие комбинации
1 2 3
4 5 6
7 8 9
1 4 7
1 5 8
1 6 9
2 4 8
2 5 9
2 6 7
3 4 9
3 5 7
3 6 8

Весь перебор с проверкой не подойдет. А если идти обычным циклом, то приведет к такому решению:
1 2 3
1 4 5
1 6 7
1 8 9
2 4 6
2 5 7
2 8
2 9
3 4 7
3 5 8
3 9
и т.д.
Подскажите, пожалуйста, либо какие-то наводки в интернете, либо какие алгоритмы могут помочь. Спасибо
  • Вопрос задан
  • 13291 просмотр
Пригласить эксперта
Ответы на вопрос 2
sgjurano
@sgjurano
Разработчик
Задача называется "генерация сочетаний", так и гуглится.
www.e-maxx-ru.1gb.ru/algo/generating_combinations
Ответ написан
Комментировать
Я когда-то на Хабре в статье предложил один подход (правда, в комментах мне потом сказали, что это "поиск перестановок через факториальную систему счисления и код Лехмера").
Глянь, там немонго, может станет понятнее.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы