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

Question

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

Например, если у меня есть следующие объекты: a, b, c,d, e, f

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

a, b, c, d

b, c, d, e

a, д, е, е

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

Answer 1

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

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

Проверьте эту страницу: http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

Answer 2

Вот рекурсивный подход, написанный на 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);
}

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

Answer 3

Если вам нужно выбрать 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
    }
}

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

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