java打印没有元素邻接的所有子序列数组

Question

在下文中，我可以打印所有子序列数组，但请有人帮助打印没有相邻元素的所有子序列

`package test;

import java.util.ArrayList;
import java.util.List;

public class Test1 {
    public static List<List<Integer>> combinations(int[] arr) {
        List<List<Integer>> combinations = new ArrayList<List<Integer>>();
        List<Integer> total;
        for (int i = 0; i < arr.length; i++) {
            int k = combinations.size();
            for (int j = 0; j < k; j++) {
                // if ((i + 1 < arr.length)) {

                total = new ArrayList<Integer>(combinations.get(j));
                total.add(new Integer(arr[i]));

                combinations.add(total);
                // }
            }
            total = new ArrayList<Integer>();
            total.add(new Integer(arr[i]));
            combinations.add(total);
        }
        System.out.println(combinations);
        return combinations;
    }

    public static void main(String args[]) {
        int arr[] = { 1, 2, 3 };
        combinations(arr);
    }
}`

输出：-[[1]、[1,2]、[2]、[1,3]、[1,2,3]、[2,3]、[3]]

预期产出：-[1]，[2]，[1,3]，[3]]

Answer 1

生成组合：

private static List<List<Integer>> generateCombinations(int[] arr){
        List<List<Integer>> combs = new ArrayList<List<Integer>>();
        int prev2 = 1,prev1 = 1;
        
        for(int i=0;i<arr.length;++i){
             //individual
            List<Integer> l = new ArrayList<>();
            l.add(arr[i]);
            combs.add(l);   
            
            if(i < 2){ // since these are base cases for our fibonacci sequence
                continue;
            }
            
            int size = prev1 + prev2 - 1; 
            
            for(int j=0;j<size;++j){
                List<Integer> new_list = new ArrayList<>(combs.get(j));
                new_list.add(arr[i]);
                combs.add(new_list);
            }           
            
            prev1 = prev1 + prev2;
            prev2 = prev1 - prev2;
        }        
        
        return combs;
    }

驱动程序代码：

public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};
        List<List<Integer>> result = generateCombinations(arr);
        int size = result.size();
        for(int i=0;i<size;++i){
            System.out.println(result.get(i).toString());
        }
    }

输出：

[1]
[2]
[3]
[1, 3]
[4]
[1, 4]
[2, 4]
[5]
[1, 5]
[2, 5]
[3, 5]
[1, 3, 5]

算法：

• 生成避免相邻元素的组合实际上遵循斐波那契序列

让我们把数组看作{1,2,3,4,5,6}

+                                    -+ -+ -+ -+ -+ -+ -+
|                                                                         |   |   |   |   |   |   |
+                                    -+ -+ -+ -+ -+ -+ -+
| Individual element's generated combinations excluding adjacent elements | 1 | 1 | 2 | 3 | 5 | 8 |
+                                    -+ -+ -+ -+ -+ -+ -+
| Elements of the array                                                   | 1 | 2 | 3 | 4 | 5 | 6 |
+                                    -+ -+ -+ -+ -+ -+ -+

• 换句话说，这意味着我将从开始迭代所有组合，并在我可以生成的总组合-1处停止（其中-1本身不包括）

• 为了更清晰，让我们看一下这些组合。假设前两种组合已经存在

[1]

[2]

• 所以，对于3我们从一开始就想

[1,3]

[3] (this we would add ourselves)

• 对于4，我们将有所有组合摆在我们面前：

[1]

[2]

[1,3]

[3]

• 现在，我们只需要走到[2]然后停下来，组合如下：

[1,4]

[2,4]

[4] (adding this ourselves).

• 等等，接下来的元素。希望这有帮助