Используя последовательность: 1, 2, 3, 4, 5.
Я искал комбинации из:
- Один
- Два
- Три
- Четыре
Объяснение и пример
В следующем примере приведены комбинации:
- Один
- Два
- Три
- Четыре
Комбинации расположены по столбцам. Каждый столбец представляет собой комбинацию количества чисел, которые он содержит.
Прочитайте образец сверху вниз.
Образец:
1
1 2
1 2 3
1 2 3 4
1 2 3 5
1 2 4
1 2 4 5
1 2 5
1 3
1 3 4
1 3 4 5
1 3 5
1 4
1 4 5
1 5
2
2 3
2 3 4
2 3 4 5
2 3 5
2 4
2 4 5
2 5
3
3 4
3 4 5
3 5
4
4 5
5
Задание
Возьмите каждое число и объедините его с каждым последующим. Затем возьмите следующее число и сделайте то же самое.
Последний элемент в комбинациях из одного числа игнорируйте.
Например, для входной последовательности A:
A[1] A[2], A[1] A[3], to A[1] A[A.length]
A[2] A[3], A[2] A[A.length]
Повторяя действия до конца.
COMBINATIONS-OF-TWO(A)
combinations = [];
count = 1;
for i=1 to A.length - 1
for j=i+1 to A.length
combinations[count] = [i, j];
count++;
return combinations;
Выводы и реализация
Используя математическую индукцию, мы пришли к следующему выводу:
Один
Комбинации из одного элемента берут каждый элемент из массива.
Два
Комбинации из двух берут каждую комбинацию из одного.
Затем добавляем каждый последующий элемент к каждому.
Игнорируя последний элемент в комбинации один.
Три
Комбинации из трех берут каждую комбинацию из двух.
Затем добавьте каждый последующий элемент к каждому.
Игнорируя последние 2 элемента в комбинации один.
Игнорирование последнего 1 элемента в комбинации два.
Четыре
Комбинация из четырех берется каждая комбинация из трех.
Затем добавьте каждый последующий элемент к каждому.
Игнорирование последних 3 элементов в комбинации один.
Игнорирование последних 2 элементов в комбинации два.
Игнорирование последних 1 элементов в комбинации три.
Реализация
COMBINATIONS-OF-FOUR(A)
combinations = [];
// use counter because loops
// don't track amount combinations
count = 1;
// combinations of one
for i to A.length - 3
// combinations of two
for j=i+1 to A.length - 2
// combinations of three
for z=j+1 to A.length - 1
// each subsequent element
// on top of combination of three
// gives combination of four
for k=z+1 to A.length
combinations[count] = [i, j, z, k];
count++;
return combinations;
В качестве бонуса, вот реализация с помощью JavaScript. Copy-Paste runnable.
function combinationsOfFour(A) {
let combinations = [];
let count = 0;
let i, j, z, k;
const len = A.length;
for (i = 0; i < len - 3; i++) {
for (j = i + 1; j < len - 2;j++) {
for (z = j + 1; z < len - 1; z++) {
for (k = z + 1; k < len; k++) {
combinations[count] = [i, j, z, k];
count++;
}
}
}
}
return combinations;
}
const numbers = [0, 1, 2, 3, 4];
console.log(combinationsOfFour(numbers));
Поиск действительных сумм из 4
Теперь я модифицирую алгоритм. Мне нужно вернуть четверки с индексами, значения которых совпадают с суммой.
// find sums of 4 that match sum
SUMS-OF-FOUR(A, sum)
sums = [];
// use sum counter because loops
// don't track amount of sums we have
count = 1;
// combinations of one
for i to A.length - 3
for j=i+1 to A.length - 2
for z=j+1 to A.length - 1
for k=z+1 to A.length
// if combination of four
// is the sum we need
if A[i] + A[j] + A[z] + A[k] == sum
// save the indices representing sum
sums[count] =[i, j, z, k];
count++;
return sums;
Сколько циклов мне нужно?
Я выяснил, сколько циклов мне нужно. Я сделал это, наблюдая за поведением, которое я использовал.
Используя последовательность 1, 2, 3, 4, 5 получаем комбинации по одной.
1
2
3
4
5
Это было линейно. Теперь сделайте это для комбинаций из двух.
Используя последовательность 1, 2, 3, 4, 5, получите комбинации из двух чисел.
Первое число:
1
append 2 => 1, 2
append 3 => 1, 3
append 4 => 1, 4
append 5 => 1, 5
Второе число:
2
append 3 => 2, 3
append 4 => 2, 4
append 5 => 2, 5
Заметили поведение цикла? Я делал это постоянно. Прошло несколько часов, пока я понял, сколько итераций делает мой ум.
Используя математическую индукцию, мы пришли к следующему выводу
- Мы можем повторить шаги для комбинации из n.
- Комбинации из одного числа используют один цикл и являются линейными.
- Комбинации из двух используют два цикла и являются квадратичными.
- Комбинации из трех используют три цикла и являются кубическими.
Реализация комбинаций для любого допустимого r
Используя последовательность 1, 2, 3, 4, 5.
Даны преобразования до уровня 3, или r=3.
1
1 2
1 2 3
1 2 4
1 2 5
1 3
1 3 4
1 3 5
1 4
1 4 5
1 5
2
2 3
2 3 4
2 3 5
2 4
2 4 5
2 5
3
3 4
3 4 5
3 5
4
4 5
5
Мы можем рассматривать столбцы как уровни или комбинации r. Каждая комбинация является преобразованием предыдущей. Чтобы добраться до комбинации 2, мы преобразуем каждую комбинацию 1. Для каждой предыдущей комбинации мы берем последнее значение (индекс). Затем добавляем каждый последующий индекс к этой комбинации. Это дает нам новую комбинацию. При последующих итерациях создается одинаковое количество комбинаций. Исключение составляют начальные комбинации, они пусты. Мы должны их заполнить. Мы продолжаем преобразовывать комбинации, пока не исчерпаем количество значений на уровне. Нам нужен один уровень для каждого преобразования.
Реализация
COMBINATIONS(array, r, combinations = [])
if combinations.length == 0
// populate combinations of 1
for i=1 to array.length
combinations[i] = [i]
if r > 1
// next combinations
next = []
count = 1
// transform each combination
// to next one
for i=1 to combinations.length
// take current combination
c = combinations[i]
// take last index
last = c[c.length]
// append next indexes to
// current combination
for j=last+1 to array.length
// copy current combination
next[count] = c
// append index to current comb.
// which creates new one
next[count][c.length + 1] = j
count++
COMBINATIONS(array, r-1, next)
else
return combinations
Ограничения, которые необходимо учитывать
- массив должен быть массивом чисел
- 1 <= r <= ar
- информация: из 5 чисел нельзя составить неповторяющуюся комбинацию 6
- информация: комбинации из 0 не имеют смысла?
- Комбинации должны быть либо
- пустой массив (из-за начального значения)
- массив чисел