查看: 153|回复: 0

[Java学习] Java基于递归和循环两种方式实现未知维度集合的笛卡尔积算法示例

发表于 4 天前

本文实例讲述了Java基于递归和循环两种方式实现未知维度集合的笛卡尔积。分享给大家供大家参考,具体如下:

什么是笛卡尔积?

在数学中,两个集合X和Y的笛卡儿积(Cartesian product),又称直积,表示为X × Y,第一个对象是X的成员而第二个对象是Y的所有可能有序对的其中一个成员。

假设集合A={a,b},集合B={0,1,2},则两个集合的笛卡尔积为{(a,0),(a,1),(a,2),(b,0),(b,1), (b,2)}。

如何用程序算法实现笛卡尔积?

如果编程前已知集合的数量,通过程序的多次循环即可得出笛卡尔积。但是如果编程前不知道集合的数量,如何得到笛卡尔积哪?比如集合表示List < List> list;这个list在编程前list的数量是未知的。下面的代码使用递归和循环两种方法实现未知维度集合的笛卡尔积:

  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.List;
  4. /**
  5. * 循环和递归两种方式实现未知维度集合的笛卡尔积
  6. * Created on 2015-05-22
  7. * @author luweijie
  8. */
  9. public class Descartes {
  10. /**
  11. * 递归实现dimValue中的笛卡尔积,结果放在result中
  12. * @param dimValue 原始数据
  13. * @param result 结果数据
  14. * @param layer dimValue的层数
  15. * @param curList 每次笛卡尔积的结果
  16. */
  17. private static void recursive (List<List<String>> dimValue, List<List<String>> result, int layer, List<String> curList) {
  18. if (layer < dimValue.size() - 1) {
  19. if (dimValue.get(layer).size() == 0) {
  20. recursive(dimValue, result, layer + 1, curList);
  21. } else {
  22. for (int i = 0; i < dimValue.get(layer).size(); i++) {
  23. List<String> list = new ArrayList<String>(curList);
  24. list.add(dimValue.get(layer).get(i));
  25. recursive(dimValue, result, layer + 1, list);
  26. }
  27. }
  28. } else if (layer == dimValue.size() - 1) {
  29. if (dimValue.get(layer).size() == 0) {
  30. result.add(curList);
  31. } else {
  32. for (int i = 0; i < dimValue.get(layer).size(); i++) {
  33. List<String> list = new ArrayList<String>(curList);
  34. list.add(dimValue.get(layer).get(i));
  35. result.add(list);
  36. }
  37. }
  38. }
  39. }
  40. /**
  41. * 循环实现dimValue中的笛卡尔积,结果放在result中
  42. * @param dimValue 原始数据
  43. * @param result 结果数据
  44. */
  45. private static void circulate (List<List<String>> dimValue, List<List<String>> result) {
  46. int total = 1;
  47. for (List<String> list : dimValue) {
  48. total *= list.size();
  49. }
  50. String[] myResult = new String[total];
  51. int itemLoopNum = 1;
  52. int loopPerItem = 1;
  53. int now = 1;
  54. for (List<String> list : dimValue) {
  55. now *= list.size();
  56. int index = 0;
  57. int currentSize = list.size();
  58. itemLoopNum = total / now;
  59. loopPerItem = total / (itemLoopNum * currentSize);
  60. int myIndex = 0;
  61. for (String string : list) {
  62. for (int i = 0; i < loopPerItem; i++) {
  63. if (myIndex == list.size()) {
  64. myIndex = 0;
  65. }
  66. for (int j = 0; j < itemLoopNum; j++) {
  67. myResult[index] = (myResult[index] == null? "" : myResult[index] + ",") + list.get(myIndex);
  68. index++;
  69. }
  70. myIndex++;
  71. }
  72. }
  73. }
  74. List<String> stringResult = Arrays.asList(myResult);
  75. for (String string : stringResult) {
  76. String[] stringArray = string.split(",");
  77. result.add(Arrays.asList(stringArray));
  78. }
  79. }
  80. /**
  81. * 程序入口
  82. * @param args
  83. */
  84. public static void main (String[] args) {
  85. List<String> list1 = new ArrayList<String>();
  86. list1.add("1");
  87. list1.add("2");
  88. List<String> list2 = new ArrayList<String>();
  89. list2.add("a");
  90. list2.add("b");
  91. List<String> list3 = new ArrayList<String>();
  92. list3.add("3");
  93. list3.add("4");
  94. list3.add("5");
  95. List<String> list4 = new ArrayList<String>();
  96. list4.add("c");
  97. list4.add("d");
  98. list4.add("e");
  99. List<List<String>> dimValue = new ArrayList<List<String>>();
  100. dimValue.add(list1);
  101. dimValue.add(list2);
  102. dimValue.add(list3);
  103. dimValue.add(list4);
  104. List<List<String>> recursiveResult = new ArrayList<List<String>>();
  105. // 递归实现笛卡尔积
  106. recursive(dimValue, recursiveResult, 0, new ArrayList<String>());
  107. System.out.println("递归实现笛卡尔乘积: 共 " + recursiveResult.size() + " 个结果");
  108. for (List<String> list : recursiveResult) {
  109. for (String string : list) {
  110. System.out.print(string + " ");
  111. }
  112. System.out.println();
  113. }
  114. List<List<String>> circulateResult = new ArrayList<List<String>>();
  115. circulate(dimValue, circulateResult);
  116. System.out.println("循环实现笛卡尔乘积: 共 " + circulateResult.size() + " 个结果");
  117. for (List<String> list : circulateResult) {
  118. for (String string : list) {
  119. System.out.print(string + " ");
  120. }
  121. System.out.println();
  122. }
  123. }
  124. }
复制代码

输出结果是:

  1. 递归实现笛卡尔乘积: 共 36 个结果
  2. 1 a 3 c
  3. 1 a 3 d
  4. 1 a 3 e
  5. 1 a 4 c
  6. 1 a 4 d
  7. 1 a 4 e
  8. 1 a 5 c
  9. 1 a 5 d
  10. 1 a 5 e
  11. 1 b 3 c
  12. 1 b 3 d
  13. 1 b 3 e
  14. 1 b 4 c
  15. 1 b 4 d
  16. 1 b 4 e
  17. 1 b 5 c
  18. 1 b 5 d
  19. 1 b 5 e
  20. 2 a 3 c
  21. 2 a 3 d
  22. 2 a 3 e
  23. 2 a 4 c
  24. 2 a 4 d
  25. 2 a 4 e
  26. 2 a 5 c
  27. 2 a 5 d
  28. 2 a 5 e
  29. 2 b 3 c
  30. 2 b 3 d
  31. 2 b 3 e
  32. 2 b 4 c
  33. 2 b 4 d
  34. 2 b 4 e
  35. 2 b 5 c
  36. 2 b 5 d
  37. 2 b 5 e
  38. 循环实现笛卡尔乘积: 共 36 个结果
  39. 1 a 3 c
  40. 1 a 3 d
  41. 1 a 3 e
  42. 1 a 4 c
  43. 1 a 4 d
  44. 1 a 4 e
  45. 1 a 5 c
  46. 1 a 5 d
  47. 1 a 5 e
  48. 1 b 3 c
  49. 1 b 3 d
  50. 1 b 3 e
  51. 1 b 4 c
  52. 1 b 4 d
  53. 1 b 4 e
  54. 1 b 5 c
  55. 1 b 5 d
  56. 1 b 5 e
  57. 2 a 3 c
  58. 2 a 3 d
  59. 2 a 3 e
  60. 2 a 4 c
  61. 2 a 4 d
  62. 2 a 4 e
  63. 2 a 5 c
  64. 2 a 5 d
  65. 2 a 5 e
  66. 2 b 3 c
  67. 2 b 3 d
  68. 2 b 3 e
  69. 2 b 4 c
  70. 2 b 4 d
  71. 2 b 4 e
  72. 2 b 5 c
  73. 2 b 5 d
  74. 2 b 5 e
复制代码

更多关于java算法相关内容感兴趣的读者可查看本站专题:《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。



回复

使用道具 举报