如何从列表中获取不同的分组组合 [英] 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屋!