如何从列表中获取不同的分组组合 [英] How to get different grouping combinations from a list

问题描述

我正在解决一个问题，我想按两个列表对列表进行分组并获得所有可能的组合。例如
：对于列表[A，B，C，D];
我正在尝试创建一种方法，该方法可以ff：

I'm working on a problem where I want to group a list by two's and get all possible combinations. for example: for the list [A,B,C,D]; I'm trying to create a method that will give me the ff:

   A and BCD
    B and ACD
    C and ABD
    D and ABC
    AB and CD
    AC and BD
    AD and BC

etc...

我知道递归是答案，但我不知道从哪里开始。有人可以指出我正确的方向吗？

I know that recursion is the answer but I don't know where to start. Can someone point me to the right direction?

到目前为止我的尝试：

List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");

    for (int x = 1; x < list.size() - 1; x++) {  //how many elements in one group
        for (int i = 0; i < list.size(); i++) {   //get first group..
            List<Integer> chosenIndices = new ArrayList<>();   //?..
            chosenIndices.add(i); // good for one element grouping only.. 
            List<String> firstGroup = getFirstGroup(list, chosenIndices); //method to pick chosenindices
            List<String> secondGroup = getRestofList(list, chosenIndices);  //method to exclude chosenIndices
            System.out.println(firstGroup + ": " + secondGroup);
        }

    }

第一组包含一个元素，但是我不知道如何获得下一个迭代，并为第一组列出两个元素的列表。
我希望这是有道理的。

this takes care of the combination where the first group contains one element but I can't figure out how to get the next iteration and come up with a list of two elements for the first group. I hope this makes sense.

推荐答案

我的第一个答案也许很有用，但效果不好。抱歉。

My first answer maybe was useful, but it worked bad. Sorry.

这里是另一个示例。它基于组合规则：

Here is another example. It is based on the rules of combinatorics:

(n, k) = (n - 1, k - 1) + (n - 1, k)

其中n-是元素总数，k是元素总数元素的组是组

where n - is the number of elements total, and k is the number of elements is group

@Test
    public void test() throws Exception {
        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");
        list.add("D");

        List<String> result = new ArrayList<>();

        for (int i = 1; i < list.size() + 1; i++) {
            combine(list, result, i);
        }

        System.out.println(result);
    }

    public static void combine(List<String> list, List<String> result, int k) {
        if (k > list.size())
            return;

        // calculate and print the possible combinations
        // e.g. c(4,2)
        int ncr = fact(list.size()) / fact(list.size() - k) / fact(k);
        System.out.println(String.format("C(%s, %s). Combinations nbr = %s", list.size(), k, ncr));

        // get the combine by index
        // e.g. 01 --> AB , 23 --> CD
        int combination[] = new int[k];

        // position of current index
        int r = 0;
        int index = 0;

        while (r >= 0) {
            // for r = 0 ==> index < (4+ (0 - 2)) = 2
            if (index <= (list.size() + (r - k))) {
                combination[r] = index;

                // if we are at the last position print and increase the index
                if (r == k - 1) {
                    //do something with the combine e.g. add to list or print
                    add(combination, list, result);
                    index++;
                } else {
                    // select index for next position
                    index = combination[r] + 1;
                    r++;
                }
            } else {
                r--;
                if (r > 0)
                    index = combination[r] + 1;
                else
                    index = combination[0] + 1;
            }
        }
    }

    private static int fact(int n) {
        if (n == 0)
            return 1;
        else
            return n * fact(n - 1);
    }

    private static void add(int[] combination, List<String> elements, List<String> result) {
        String output = "";
        for (int i = 0; i < combination.length; i++) {
            output += elements.get(combination[i]);
        }

        result.add(output);
    }

输出为：

C(4, 1). Combinations nbr = 4
C(4, 2). Combinations nbr = 6
C(4, 3). Combinations nbr = 4
C(4, 4). Combinations nbr = 1
[A, B, C, D, AB, AC, AD, BC, BD, CD, ABC, ABD, ACD, BCD, ABCD]

这篇关于如何从列表中获取不同的分组组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！