查找所有具有重复元素但没有重复行的组合。

huangapple
go评论102阅读模式
英文:

Find all combinations with repetitions but without duplicate rows

问题

以下是翻译好的部分：

有一个数组1、2、3、4。需要生成所有可能的3个元素的组合，元素可以重复使用。行中元素的顺序不重要。例如：114 = 411 = 141。我找不到合适的算法。我找到了这个算法，但不能有元素的重复，比如111或113，只能是123、124等。

  1. public void doit(){
  2. String[] arr = {"1", "2", "3","4"};
  3. int count = fuctorial(arr.length);
  4. int max = arr.length - 1;
  5. System.out.println("Variations: " + count);
  6. int shift = max;
  7. String t;
  8. while (count > 0) {
  9.     t = arr[shift];
  10.     arr[shift] = arr[shift - 1];
  11.     arr[shift - 1] = t;
  12.     print(arr);
  13.     count--;
  14.     if (shift < 2) {
  15.         shift = max;
  16.     } else {
  17.         shift--;
  18.     }
  19. }
  20. }
  21. static void print(String[] arr) {
  22. System.out.println(Arrays.toString(arr));
  23. }
  25. static int fuctorial(int n) {
  26. return (n > 0) ? n * fuctorial(n - 1) : 1;
  27. }
英文:

There is an array of 1, 2, 3, 4. It is necessary to make all possible combinations of 3 size series, the elements can be repeated. The order of the elements in the row is not important. For instance:
114 = 411 = 141.
I can't find a suitable algorithm. I have found this algorithm, but there can be no repetitions of elements, like 111 or 113, only 123,124 etc.

  1. public void doit(){
  2. String[] arr = {&quot;1&quot;, &quot;2&quot;, &quot;3&quot;,&quot;4&quot;};
  3.             int count = fuctorial(arr.length);
  4.             int max = arr.length - 1;
  5.             System.out.println(&quot;Вариантов &quot; + count);
  6.             int shift = max;
  7.             String t;
  8.             while (count &gt; 0) {
  9.                 t = arr[shift];
  10.                 arr[shift] = arr[shift - 1];
  11.                 arr[shift - 1] = t;
  12.                 print(arr);
  13.                 count--;
  14.                 if (shift &lt; 2) {
  15.                     shift = max;
  16.                 } else {
  17.                     shift--;
  18.                 }
  19.             }
  20. }
  21.     static void print(String[] arr) {
  22.         System.out.println(Arrays.toString(arr));
  23.     }
  24.  
  25.     static int fuctorial(int n) {
  26.         return (n &gt; 0) ? n * fuctorial(n - 1) : 1;
  27.     }

答案1

得分: 2

请尝试这个代码：

  1. static void combination(int[] a, int n) {
  2.     int size = a.length;
  3.     int[] selected = new int[n];
  4.     new Object() {
  6.         void print() {
  7.             for (int i = 0; i < n; ++i)
  8.                 System.out.print(a[selected[i]] + " ");
  9.             System.out.println();
  10.         }
  12.         void combination(int index, int prev) {
  13.             if (index >= n)
  14.                 print();
  15.             else
  16.                 for (int i = prev; i < size; ++i)
  17.                     combination(index + 1, selected[index] = i);
  18.         }
  20.     }.combination(0, 0);
  21. }
  23. int[] a = {6, 7, 8, 9};
  24. combination(a, 3);

输出：

  1. 6 6 6 
  2. 6 6 7 
  3. 6 6 8 
  4. 6 6 9 
  5. 6 7 7 
  6. 6 7 8 
  7. 6 7 9 
  8. 6 8 8 
  9. 6 8 9 
  10. 6 9 9 
  11. 7 7 7 
  12. 7 7 8 
  13. 7 7 9 
  14. 7 8 8 
  15. 7 8 9 
  16. 7 9 9 
  17. 8 8 8 
  18. 8 8 9 
  19. 8 9 9 
  20. 9 9 9
英文:

Try this.

  1. static void combination(int[] a, int n) {
  2.     int size = a.length;
  3.     int[] selected = new int[n];
  4.     new Object() {
  6.         void print() {
  7.             for (int i = 0; i &lt; n; ++i)
  8.                 System.out.print(a[selected[i]] + &quot; &quot;);
  9.             System.out.println();
  10.         }
  12.         void combination(int index, int prev) {
  13.             if (index &gt;= n)
  14.                 print();
  15.             else
  16.                 for (int i = prev; i &lt; size; ++i)
  17.                     combination(index + 1, selected[index] = i);
  18.         }
  20.     }.combination(0, 0);
  21. }

and

  1. int[] a = {6, 7, 8, 9};
  2. combination(a, 3);

output:

  1. 6 6 6 
  2. 6 6 7 
  3. 6 6 8 
  4. 6 6 9 
  5. 6 7 7 
  6. 6 7 8 
  7. 6 7 9 
  8. 6 8 8 
  9. 6 8 9 
  10. 6 9 9 
  11. 7 7 7 
  12. 7 7 8 
  13. 7 7 9 
  14. 7 8 8 
  15. 7 8 9 
  16. 7 9 9 
  17. 8 8 8 
  18. 8 8 9 
  19. 8 9 9 
  20. 9 9 9

答案2

得分: 1

  1. public void func() {
  2.     boolean[] check = new boolean[49];
  3.     for(int i=1; i <= 4; i++ ) {
  4.         for(int j=1; j <= 4; j++) {
  5.             for(int k=1; k <= 4; k++) {
  6.                 int sum = i*i + j*j + k*k;
  7.                 if(!check[sum]) {
  8.                     check[sum] = true;
  9.                     System.out.println(i + "," + j + "," + k);
  10.                 }
  11.             }
  12.         }
  13.     }
  14. }
  16. 思路是：我们取一个三元组，计算平方和，然后检查是否已经有一个具有相同平方和的三元组。相同的三元组将具有相同的平方和。
  17. 平方和总是在3-48的范围内。此外，平方和对于每组数字组合都是唯一的，正如您所要求的那样。
  19. 复杂度为O(N^3)，其中N是数组的大小。因为我们需要3个元素的组合，我认为无法降低复杂度。
  21. **更新：** 为了更通用，可以使用一个HashSet<Integer>来存储平方和，而不是使用布尔数组，并在输入数组上进行三重嵌套循环。计算平方和并与HashSet进行比较。
  23. 性能优化：预先计算数组中每个元素的平方，这样就不必一遍又一遍地计算它们。
英文: 
  1. public void func() {
  2.     boolean[] check = new boolean[49];
  3.     for(int i=1; i &lt;=4; i++ ) {
  4.         for(int j=1; j &lt;=4; j++) {
  5.             for(int k=1; k&lt;=4; k++) {
  6.                 int sum = i*i + j*j + k*k;
  7.                 if(!check[sum]) {
  8.                     check[sum] = true;
  9.                     System.out.println(i + &quot;,&quot; + j + &quot;,&quot; + k);
  10.                 }
  11.             }
  12.         }
  13.     }
  14. }

idea is: we take a triplet, calculate the sum of squares, and check if we already had a triplet with that sum. identical triplets will have the same sum of squares.
the sum of squares will always be in the range 3-48. also, the sum is unique to each combination of numbers just like you require.

Complexity is O(N^3) where N is the size of the array. since we need combinations of 3 elements, i don't think you can go below that.

UPDATE: to make is more general, use a HashSet<Integer> for the sums instead of the boolean array, and iterate 3 nested loops over the input array. calculate the sum of squares and check against the HashSet.

Performance Optimization: calculate the squares of each element in the array in advance so you dont have to calculate them over and over again.

huangapple
  • 本文由 发表于 2020年8月6日 18:47:47
  • 转载请务必保留本文链接：https://go.coder-hub.com/63281968.html
  • algorithm
  • java
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定