Какой алгоритм мне нужен?

Question

Я пытаюсь выяснить все различные способы создания групп из 4 объектов с помощью объектива-c.

Например, если я имел следующие объекты: а, б, в, г, д, е

Тогда я мог бы создать такие группы, как

а, б, в, г

б, в, г, д

а, г, д, е

и так далее. Заказ не имеет значения. Если бы я хотел выяснить все разные возможности, какой алгоритм мне нужен? Сначала я думал о перестановках, но я не думаю, что все. Я думаю, что может быть что-то более быстрое или более подходящее, но я забыл, что это называется.

Answer 1

Если вам нужно выбрать 4 разных объекта всеми возможными способами, это означает, что вам нужно удалить («не выбирать») два других объекта всеми возможными способами. Только две петли:

for (int i = 0; i < 6; ++i) { 
    for (int j = i + 1; j < 6; ++j) { 
     // here we select all elements except i and j 
    } 
} 

Не очень расширяемый, если количество объектов растет, но достаточно прост.

(я предполагаю, что порядок не имеет значения: это так кажется из ваших примеров)

Answer 2

Перестановка является правильным местом для начала. Метод грубой силы должен был найти все шесть перестановок строк и просто захватить первые четыре и добавить их в набор. Ужасно неэффективно.

Базовый алгоритм перестановки может быть изменен, чтобы генерировать только группы из четырех.

Заканчивать эту страницу: http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

Answer 3

Вот рекурсивный подход, написанный на Java, подходит для общего случая:

public static void comb(int[] arr, int m) { 
    comb(arr, m, 0, new ArrayList<Integer>()); 
} 

public static void comb(int[] arr, int m, int ind, ArrayList<Integer> s) { 
    int left = m - s.size(); 
    if (left == 0) { 
     System.out.println(s); 
     return; 
    } 

    if (left > arr.length - ind) 
     return; 
    comb(arr, m, ind + 1, s); 
    s.add(arr[ind]); 
    comb(arr, m, ind + 1, s); 
    s.remove(s.size()-1); 
} 

Разветвляется каждый раз, когда он находит элемент и должен решить, следует ли включить это или нет. Существует также оптимизация обрезки для предотвращения тупиков.