комбинации из списка предметов
У меня есть список коллекций:
{A B}
{C D E}
{F G}
Количество строк может быть произвольным, а также количество элементов в строке может быть произвольным.
Мне нужно получить это:
{ACF ACG ADF ADG AEF AEG BCF BCG BDF BDG BEF BEG}
Может кто-то указать на какой-то алгоритм, который может сделать это или, по крайней мере, на название проблемы — если таковой имеется.
Решение
Вы можете создать рекурсивную функцию, которая принимает исходную коллекцию списков и текущий индекс списка в коллекции. Затем он будет перебирать элементы в списке и при каждом вызове самого элемента с увеличенным индексом.
Другие решения
В своем примере вы сказали, что вам нужно только это:
{ACF ACG ADF ADG AEF AEG BCF BCG BDF BDG BEF BEG}
Если вам также нужны все другие комбинации, то вы можете использовать класс, который я написал, для обработки общих функций для работы с биномиальным коэффициентом, к которому относится ваша проблема. Он выполняет следующие задачи:
-
Выводит все K-индексы в хорошем формате для любого N, выбирают K в файл. K-индексы могут быть заменены более описательными строками или буквами. Этот метод делает решение этого типа проблемы довольно тривиальным.
-
Преобразует K-индексы в соответствующий индекс записи в отсортированной таблице биномиальных коэффициентов. Этот метод намного быстрее, чем старые опубликованные методы, основанные на итерации. Это делается с помощью математического свойства, присущего треугольнику Паскаля. Моя газета говорит об этом. Я считаю, что я первый, кто открыл и опубликовал эту технику, но я могу ошибаться.
-
Преобразует индекс в отсортированной таблице биномиальных коэффициентов в соответствующие K-индексы.
-
Пользы Марк Доминус метод для вычисления биномиального коэффициента, который с гораздо меньшей вероятностью переполнится и работает с большими числами.
-
Класс написан на .NET C # и предоставляет способ управления объектами, связанными с проблемой (если таковые имеются), используя общий список. Конструктор этого класса принимает значение bool, называемое InitTable, которое при значении true создаст общий список для хранения управляемых объектов. Если это значение равно false, таблица не будет создана. Таблицу не нужно создавать для выполнения 4 вышеуказанных методов. Методы доступа предоставляются для доступа к таблице.
-
Существует связанный тестовый класс, который показывает, как использовать класс и его методы. Он был тщательно протестирован с 2 случаями, и никаких известных ошибок нет.
Чтобы прочитать об этом классе и скачать код, см. Таблицы биномиальных коэффициентов.
Не должно быть трудно преобразовать этот класс на язык по вашему выбору.
На самом деле это легко:
Вот решение в C ++, если первый набор — A, второй — B, а третий — C;
cout << "{ ";
for( int i=0; i<a_size; ++i ) {
for( int j=0; j<b_size; ++j ) {
for( int k=0; k<c_size; ++k ) {
cout << A[ i ] << B[ j ] << C[ k ] << " ";
}
}
}
cout << " }\n";