Алгоритм получения всех комбинаций размера n из массива (Java)?
57603 просмотра
3 ответа
Прямо сейчас я пытаюсь написать функцию, которая принимает массив и целое число n, и дает список каждой комбинации размера n (так что список массивов int). Я могу написать это, используя n вложенных циклов, но это работает только для определенного размера подмножества. Я не могу понять, как обобщить это, чтобы работать для любого размера комбинации. Я думаю, что мне нужно использовать рекурсию?
Это код для всех комбинаций из 3 элементов, и мне нужен алгоритм для любого количества элементов.
import java.util.List;
import java.util.ArrayList;
public class combinatorics{
public static void main(String[] args) {
List<int[]> list = new ArrayList<int[]>();
int[] arr = {1,2,3,4,5};
combinations3(arr,list);
listToString(list);
}
static void combinations3(int[] arr, List<int[]> list){
for(int i = 0; i<arr.length-2; i++)
for(int j = i+1; j<arr.length-1; j++)
for(int k = j+1; k<arr.length; k++)
list.add(new int[]{arr[i],arr[j],arr[k]});
}
private static void listToString(List<int[]> list){
for(int i = 0; i<list.size(); i++){ //iterate through list
for(int j : list.get(i)){ //iterate through array
System.out.printf("%d ",j);
}
System.out.print("\n");
}
}
}
Автор: Esostack
Источник
Размещён: 12.11.2019 09:40
Ответы (3)
48 плюса
Это хорошо изученная проблема генерации всех k-подмножеств или k-комбинаций , что может быть легко выполнено без рекурсии.
Идея состоит в том, чтобы иметь массив размеров, k
сохраняющий последовательность индексов элементов из входного массива (которые являются числами от 0
до n - 1
) в порядке возрастания. ( Затем можно создать подмножество , взяв элементы по этим индексам из исходного массива.) Поэтому нам нужно сгенерировать все такие последовательности индексов.
Первая последовательность индексов будет [0, 1, 2, ... , k - 1]
, на втором шаге она переключится на [0, 1, 2,..., k]
, затем на [0, 1, 2, ... k + 1]
и так далее. Последняя возможная последовательность будет [n - k, n - k + 1, ..., n - 1]
.
На каждом шаге алгоритм ищет ближайший к конечному элементу, который может быть увеличен, увеличивает его и заполняет элементы прямо к этому элементу.
Для иллюстрации рассмотрим n = 7
и k = 3
. Первая последовательность индексов [0, 1, 2]
, затем [0, 1, 3]
и так далее ... В какой-то момент мы имеем [0, 5, 6]
:
[0, 5, 6] <-- scan from the end: "6" cannot be incremented, "5" also, but "0" can be
[1, ?, ?] <-- "0" -> "1"
[1, 2, 3] <-- fill up remaining elements
next iteration:
[1, 2, 3] <-- "3" can be incremented
[1, 2, 4] <-- "3" -> "4"
Таким образом, [0, 5, 6]
следует [1, 2, 3]
, затем идет [1, 2, 4]
и т. Д.
Код:
int[] input = {10, 20, 30, 40, 50}; // input array
int k = 3; // sequence length
List<int[]> subsets = new ArrayList<>();
int[] s = new int[k]; // here we'll keep indices
// pointing to elements in input array
if (k <= input.length) {
// first index sequence: 0, 1, 2, ...
for (int i = 0; (s[i] = i) < k - 1; i++);
subsets.add(getSubset(input, s));
for(;;) {
int i;
// find position of item that can be incremented
for (i = k - 1; i >= 0 && s[i] == input.length - k + i; i--);
if (i < 0) {
break;
}
s[i]++; // increment this item
for (++i; i < k; i++) { // fill up remaining items
s[i] = s[i - 1] + 1;
}
subsets.add(getSubset(input, s));
}
}
// generate actual subset by index sequence
int[] getSubset(int[] input, int[] subset) {
int[] result = new int[subset.length];
for (int i = 0; i < subset.length; i++)
result[i] = input[subset[i]];
return result;
}
Автор: Alex Salauyou
Размещён: 28.04.2015 09:02
5 плюса
Если я правильно понял вашу проблему, эта статья, кажется, указывает на то, что вы пытаетесь сделать.
Цитировать из статьи:
Автор: Roney Michael Размещён: 28.04.2015 05:31Способ 1 (исправить элементы и повторить)
Мы создаем временный массив «data []», который хранит все выходные данные один за другим. Идея состоит в том, чтобы начать с первого индекса (index = 0) в data [], один за другим исправить элементы в этом индексе и повторить оставшиеся индексы. Пусть входной массив равен {1, 2, 3, 4, 5} и r равен 3. Сначала мы фиксируем 1 в индексе 0 в data [], затем возвращаемся к оставшимся индексам, затем фиксируем 2 в индексе 0 и повторяем. Наконец, мы исправляем 3 и возвращаемся к остальным индексам. Когда число элементов в data [] становится равным r (размер комбинации), мы печатаем data [].
Способ 2 (включить и исключить каждый элемент)
Как и в предыдущем методе, мы создаем временный массив данных []. Идея здесь аналогична проблеме суммы подмножеств. Мы по очереди рассматриваем каждый элемент входного массива и повторяем для двух случаев:
- Элемент включен в текущую комбинацию (мы помещаем элемент в data [] и увеличиваем следующий доступный индекс в data [])
- Элемент исключен в текущей комбинации (мы не ставим элемент и не меняем индекс)
Когда число элементов в data [] становится равным r (размер комбинации), мы печатаем его.
2 плюса
Вы можете сделать это определенно с итерацией.
Вот одно решение, которое вычисляет, сколько массивов мы должны создать, а затем строит их, используя математические вычисления, чтобы вычислить, какой элемент из исходного массива должен находиться в каком месте:
public static void combinations(int n, int[] arr, List<int[]> list) {
// Calculate the number of arrays we should create
int numArrays = (int)Math.pow(arr.length, n);
// Create each array
for(int i = 0; i < numArrays; i++) {
int[] current = new int[n];
// Calculate the correct item for each position in the array
for(int j = 0; j < n; j++) {
// This is the period with which this position changes, i.e.
// a period of 5 means the value changes every 5th array
int period = (int) Math.pow(arr.length, n - j - 1);
// Get the correct item and set it
int index = i / period % arr.length;
current[j] = arr[index];
}
list.add(current);
}
}
Обновить:
Вот оптимизированная версия, которая значительно сокращает количество обращений к Math.pow
public static void combinations(int n, int[] arr, List<int[]> list) {
// Calculate the number of arrays we should create
int numArrays = (int)Math.pow(arr.length, n);
// Create each array
for(int i = 0; i < numArrays; i++) {
list.add(new int[n]);
}
// Fill up the arrays
for(int j = 0; j < n; j++) {
// This is the period with which this position changes, i.e.
// a period of 5 means the value changes every 5th array
int period = (int) Math.pow(arr.length, n - j - 1);
for(int i = 0; i < numArrays; i++) {
int[] current = list.get(i);
// Get the correct item and set it
int index = i / period % arr.length;
current[j] = arr[index];
}
}
}
Автор: Raniz
Размещён: 28.04.2015 05:11
Вопросы из категории :
- java В чем разница между int и Integer в Java и C #?
- java Как я могу определить IP моего маршрутизатора / шлюза в Java?
- java Каков наилучший способ проверки XML-файла по сравнению с XSD-файлом?
- java Как округлить результат целочисленного деления?
- java Преобразование списка <Integer> в список <String>
- java Почему я не могу объявить статические методы в интерфейсе?
- combinations Алгоритм возврата всех комбинаций k элементов из n
- combinations Как получить все возможные комбинации элементов списка?
- combinations Все комбинации списка списков
- combinations Как создать комбинации нескольких векторов без циклов жесткого кодирования в C ++?
- combinations Генерация неповторяющихся пар комбинаций в R
- combinations Генерация всех двоичных строк длины n с установленным k битами
- combinatorics Как генерировать перестановки списка без "обратных дубликатов" в Python с использованием генераторов
- combinatorics Проблема назначения, функция NumPy?
- combinatorics Быстрая перестановка -> число -> алгоритмы отображения перестановок
- combinatorics Комбинаторный «N выбирает R» в Java-математике?
- combinatorics Как распечатать все возможные комбинации букв, которые может представлять данный номер телефона?
- combinatorics Как сгенерировать все варианты с повторениями строки?