Print all subsequence arrays where no elements are adjacents

Question

In the following i can able to print all the sub sequence arrays but can someone please help to print all the subsequence where no elements adjacent.

`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);
    }
}`

output :- [[1], [1, 2], [2], [1, 3], [1, 2, 3], [2, 3], [3]]

expected output : - [[1], [2], [1, 3],[3]]

Answer 1

Generate Combinations:

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;
    }

Driver Code:

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());
        }
    }

Output:

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

Algorithm:

• Generating combinations avoiding adjacent elements actually follows a fibonacci sequence.

Let's take array as as {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 |
+-------------------------------------------------------------------------+---+---+---+---+---+---+

• In other words, this means that I would iterate all combinations from the start and stop at the point where it will be total combinations I could generate - 1(where -1 is excluding for itself).

• Let's go through the combinations for better clarity. Assume, the first 2 combinations are already there.

[1]

[2]

• So, for 3 we would go from the start like,

[1,3]

[3] (this we would add ourselves)

• For 4, we would have all combinations in front of us as:

[1]

[2]

[1,3]

[3]

• Now, we would only go till [2] and then stop, making combinations as:

[1,4]

[2,4]

[4] (adding this ourselves).

• and so on so forth for upcoming elements. Hope this helps.

Answer 2

I decided to split the solution into two methods, one simple method that would create a List from the array for a given start position and step size and a main method that called the first one for all possible combinations.

static List<Integer> oneLoop(int[] arr, boolean isOdd, int step) {
    int start = isOdd ? 1 : 0;
    List<Integer> result = new ArrayList<>();
    for (int i = start; i < arr.length; i += step) {
        result.add(arr[i]);    
    }
    return result;
}

static List<List<Integer>> combinations(int[] arr) {
    List<List<Integer>> allCombinations = new ArrayList<>();

    //Add each single element as separate list
    for (int i = 0; i < arr.length; i++) {
        List<Integer> list = new ArrayList<>();
        list.add(arr[i]);
        allCombinations.add(list);
    }
    //Loop over an increasing larger step size until size is to large
    int step = 2;
    while (step < arr.length) {                        
        allCombinations.add(oneLoop(arr, false, step));
        if ( (step +1) < arr.length) {
            allCombinations.add(oneLoop(arr, true, step));
        }
        step += 1;
    }

    return allCombinations;
}

And this is my test method

public static void main(String[] args) {
    int[] array = new int[args.length];
    for (int i = 0; i < args.length; i++) {
        array[i] = Integer.valueOf(args[i]);
    } 
    List<List<Integer>> list = combinations(array);
    System.out.println(list);
}