Вы столкнулись с чрезмерно сложным решением, которое, тем не менее, просто работает для случая двух сегментов.Однако, как вы обнаружили, он не будет расширяться естественным образом до трех или более сегментов.
Вот более простое решение для случая с двумя корзинами, обобщенное и использующее List s вместо массивов:
// Find all 2-item combinations consisting of 1 item picked from
// each of 2 buckets
static <T> List<List<T>> pick1From2(List<List<T>> in)
{
List<List<T>> result = new ArrayList<>();
for (int i = 0; i < in.get(0).size(); ++i) {
for (int j = 0; j < in.get(1).size(); ++j) {
result.add(Arrays.asList(in.get(0).get(i), in.get(1).get(j)));
}
}
return result;
}
Внешний цикл работает над всеми элементами первого сегментаи для каждого элемента первого сегмента внутренний цикл проходит над элементами второго блока.
Для трех блоков вы можете просто добавить третий уровень вложенности цикла:
// Find all 3-item combinations consisting of 1 item picked from
// each of 3 buckets
static <T> List<List<T>> pick1From3(List<List<T>> in)
{
List<List<T>> result = new ArrayList<>();
for (int i = 0; i < in.get(0).size(); ++i) {
for (int j = 0; j < in.get(1).size(); ++j) {
for (int k = 0; k < in.get(2).size(); ++k)
result.add(Arrays.asList(in.get(0).get(i), in.get(1).get(j), in.get(2).get(k)));
}
}
return result;
}
Теперь у вас есть внешний цикл, проходящий через элементы первого контейнера, промежуточный цикл, проходящий через элементы второго контейнера, и внутренний цикл, проходящий через элементы третьего контейнера.
Но этот подход ограничен тем фактом, что необходимая глубина вложенности цикла напрямую связана с количеством сегментов, которые нужно обработать: Конечно, вы можете добавить четвертый, пятый и т. Д. Уровень циклагнездо для обработки четырех, пяти или более ведер.Тем не менее, основная проблема остается: вы должны продолжать модифицировать код, чтобы он соответствовал постоянно увеличивающемуся количеству сегментов.
Решение дилеммы - единый алгоритм, который учитывает любое число, N блоков, эффективно имитируя циклы for, вложенные в уровни N.Массив из индексов N заменит управляющие переменные цикла N из вложенных for операторов N:
// Find all `N`-item combinations consisting 1 item picked from
// each of an `N` buckets
static <T> List<List<T>> pick1fromN(List<List<T>> s)
{
List<List<T>> result = new ArrayList<>();
int[] idx = new int[s.size()];
while (idx[0] < s.get(0).size()) {
List<T> pick = new ArrayList(s.size());
for (int i = 0; i < idx.length; ++i) {
pick.add(s.get(i).get(idx[i]));
}
result.add(pick);
int i = idx.length - 1;
while (++idx[i] >= s.get(i).size() && i > 0) {
idx[i] = 0;
--i;
}
}
return result;
}
Все индексы начинаются с нуля, и каждый из них выводитсяпо достижении размера соответствующего ведра.Для перехода к следующей комбинации (внутренний цикл while) последний индексный индекс увеличивается;если он имеет maxxed out, он сбрасывается в ноль, и следующий более высокий индекс увеличивается.Если следующий более высокий индекс также достигает максимума, он сбрасывается и вызывает увеличение следующего индекса и так далее.idx[0] никогда не сбрасывается после увеличения, поэтому внешний while может определить, когда idx[0] достиг максимума.
Сбор k предметов из каждого ведра - это в основном тот же процесс, за исключением наборов k-комбинаций ведер, заменяющих исходные ведра:
// Find all `N * k`-item combinations formed by picking `k` items
// from each of `N` buckets
static <T> List<List<T>> pickKfromEach(List<List<T>> sets, int k)
{
List<List<List<T>>> kCombos = new ArrayList<>(sets.size());
for (List<T> ms : sets) {
kCombos.add(combinations(ms, k));
}
ArrayList<List<T>> result = new ArrayList<>();
int[] indices = new int[kCombos.size()];
while (indices[0] < kCombos.get(0).size()) {
List<T> pick = new ArrayList<>(kCombos.size());
for (int i = 0; i < indices.length; ++i) {
pick.addAll(kCombos.get(i).get(indices[i]));
}
result.add(pick);
int i = indices.length - 1;
while (++indices[i] >= kCombos.get(i).size() && i > 0) {
indices[i] = 0;
--i;
}
}
return result;
}
static <T> List<List<T>> combinations(List<T> s, int k) throws IllegalArgumentException
{
if (k < 0 || k > s.size()) {
throw new IllegalArgumentException("Can't pick " + k
+ " from set of size " + s.size());
}
List<List<T>> res = new LinkedList<>();
if (k > 0) {
int idx[] = new int[k];
for (int ix = 0; ix < idx.length; ++ix) {
idx[ix] = ix;
}
while (idx[0] <= s.size() - k) {
List<T> combo = new ArrayList<>(k);
for (int ix = 0; ix < idx.length; ++ix) {
combo.add(s.get(idx[ix]));
}
res.add(combo);
int ix = idx.length - 1;
while (ix > 0 && (idx[ix] == s.size() - k + ix))
--ix;
++idx[ix];
while (++ix < idx.length)
idx[ix] = idx[ix-1]+1;
}
}
return res;
}
Как и в процедуре выбора, метод combinations использует массив индексов для перечисления комбинаций.Но индексы управляются немного по-другому.Индексы начинаются с {0, 1, 2, ..., k -1_} и достигают максимума, когда достигают значений { n - k , n - k + 1, ..., n }.Чтобы перейти к следующей комбинации, последний индекс, который еще не достиг максимума, увеличивается, а затем каждый следующий индекс сбрасывается до значения, указанного выше, плюс один.