What is Cartesian Product with Repetition
比如说有两个集合：
({1, 2, 3})
({A, B, C})
想把他们组合成所有可能组合，比如，
1AAA
1AAB
1AAC
...
这种组合可以称为"有重复的笛卡尔积"或"带重复的笛卡尔乘积"(Cartesian Product with Repetition)。
带重复的笛卡尔乘积(Cartesian Product with Repetition)具有以下特征:
-
涉及两个或多个集合：它是针对两个或更多个集合进行操作。在您的示例中,涉及两个集合{1, 2, 3}和{A, B, C}。
-
元素可以重复出现：与传统的笛卡尔积不同,在带重复的笛卡尔乘积中,同一个集合中的元素可以在生成的组合中多次出现。在您的示例中,第二个集合{A, B, C}中的元素可以在组合中重复出现,比如AAA、ABB等。
-
生成的组合长度固定：生成的组合的长度是事先确定的,等于参与集合的数量。在您的示例中,生成的组合长度为2,因为涉及两个集合。
-
组合的排列顺序不同视为不同组合：生成的组合中,元素的排列顺序不同就被视为不同的组合。例如,AB和BA是两个不同的组合。
-
组合数量呈指数级增长：随着参与集合的元素数量增加,生成的组合数量会呈指数级增长。如果有n个集合,每个集合有m个元素,那么生成的组合数量将是m^n。
总的来说,带重复的笛卡尔乘积是一种特殊的组合形式,它允许元素重复出现。
Code Demo
import java.util.ArrayList; import java.util.List; public class Combination { public static void main(String[] args) { List<String> list1 = new ArrayList<>(); list1.add("1"); list1.add("2"); list1.add("3"); List<String> list2 = new ArrayList<>(); list2.add("A"); list2.add("B"); list2.add("C"); // 用于存储所有可能的组合 List<String> combinations = new ArrayList<>(); // 遍历第一个列表中的每个元素 // 遍历list1中的每个元素,对于每个元素: // 调用generateCombinations方法,将list2和list2的长度作为参数传递进去,并将生成的组合添加到combinations列表中。 for (String item1 : list1) { // 对于每个元素,生成第二个列表中元素的所有可能组合,并添加到 combinations 列表中 combinations.addAll(generateCombinations(list2, list2.size(), item1)); } // 打印所有可能的组合 System.out.println("所有可能的组合:"); for (String combination : combinations) { System.out.println(combination); } } /** * 生成第二个列表中元素的所有可能组合 * * @param list 第二个列表 * @param length 要生成的组合长度 * @param prefix 已经选择的元素前缀 * @return 所有可能的组合 */ private static List<String> generateCombinations(List<String> list, int length, String prefix) { // 所有可能的组合 存储 List<String> combinations = new ArrayList<>(); // 如果要生成的组合长度为 0,说明已经生成了所有元素的组合 if (length == 0) { // 将前缀添加到结果列表中并返回 combinations.add(prefix); return combinations; } // 遍历第二个列表中的每个元素 for (int i = 0; i < list.size(); i++) { // 将当前元素追加到前缀中 String newPrefix = prefix + list.get(i); // 递归调用 generateCombinations 方法,将 length 减 1,并将新的前缀作为参数传递进去 combinations.addAll(generateCombinations(list, length - 1, newPrefix)); } return combinations; } } out:
所有可能的组合: 1AAA 1AAB 1AAC 1ABA 1ABB 1ABC 1ACA 1ACB 1ACC 1BAA 1BAB 1BAC 1BBA 1BBB 1BBC 1BCA 1BCB 1BCC 1CAA 1CAB 1CAC 1CBA 1CBB 1CBC 1CCA 1CCB 1CCC 2AAA 2AAB 2AAC 2ABA 2ABB 2ABC 2ACA 2ACB 2ACC 2BAA 2BAB 2BAC 2BBA 2BBB 2BBC 2BCA 2BCB 2BCC 2CAA 2CAB 2CAC 2CBA 2CBB 2CBC 2CCA 2CCB 2CCC 3AAA 3AAB 3AAC 3ABA 3ABB 3ABC 3ACA 3ACB 3ACC 3BAA 3BAB 3BAC 3BBA 3BBB 3BBC 3BCA 3BCB 3BCC 3CAA 3CAB 3CAC 3CBA 3CBB 3CBC 3CCA 3CCB 3CCC 
