How to get a collection of combinations of an Integer arrayList in Java

Question

My goal is to find all possible combinations of items in an ArrayList with a fixed predefined length. For example, if my ArrayList is called arr and contains <1, 2, 3> then the desired output for the predefined size r = 2 will be:

<1,2>
<1,3>
<2,3>

Here is code I found which prints the desired output. My problem is that I need to define a return value type ArrayList which holds the outputs from the method. Besides, my input type is also an ArrayList<Integer>, instead of an Array, which has made it more complicated for me because then I first will need to convert the values to the primitive type int.

import java.io.*;

class Permutation {

    /* arr[] ---> Input Array
    data[] ---> Temporary array to store current combination
    start & end ---> Staring and Ending indexes in arr[]
    index ---> Current index in data[]
    r ---> Size of a combination to be printed */
    static void combinationUtil(int arr[], int data[], int start,
                                int end, int index, int r)
    {
        // Current combination is ready to be printed, print it
        if (index == r)
        {
            for (int j=0; j<r; j++)
                System.out.print(data[j]+" ");
            System.out.println("");
            return;
        }

        // replace index with all possible elements. The condition
        // "end-i+1 >= r-index" makes sure that including one element
        // at index will make a combination with remaining elements
        // at remaining positions
        for (int i=start; i<=end && end-i+1 >= r-index; i++)
        {
            data[index] = arr[i];
            combinationUtil(arr, data, i+1, end, index+1, r);
        }
    }

    // The main function that prints all combinations of size r
    // in arr[] of size n. This function mainly uses combinationUtil()
    static void printCombination(int arr[], int n, int r)
    {
        // A temporary array to store all combination one by one
        int data[]=new int[r];

        // Print all combination using temprary array 'data[]'
        combinationUtil(arr, data, 0, n-1, 0, r);
    }

    /*Driver function to check for above function*/
    public static void main (String[] args) {
        int arr[] = {1, 2, 3, 4, 5};
        int r = 3;
        int n = arr.length;
        printCombination(arr, n, r);
    }
}

/* This code is contributed by Devesh Agrawal */

StaticBeagle · Accepted Answer · 2018-06-24 02:55:33Z

ArrayList is backed up by an array internally so translating the current array based implementation to ArrayList should be reasonable. In arrays you use the [] operator to index an element in the array, and the parallel operations using ArrayList are get and set. Also you might want to read on Autoboxing and Unboxing. A possible implementation using Lists:

static void combinationUtil(List<Integer> list, List<Integer> data, int start, int end, int index, int r) {
    // Current combination is ready to be printed, print it
    if (index == r) {
        for (int j = 0; j < r; j++)
            System.out.print(data.get(j) + " ");
        System.out.println("");
        return;
    }

    // replace index with all possible elements. The condition
    // "end-i+1 >= r-index" makes sure that including one element
    // at index will make a combination with remaining elements
    // at remaining positions
    for (int i = start; i <= end && end - i + 1 >= r - index; i++) {
        data.set(index, list.get(i));
        combinationUtil(list, data, i + 1, end, index + 1, r);
    }
}

// The main function that prints all combinations of size r
// in list of size n. This function mainly uses combinationUtil()
static void printCombination(List<Integer> list, int n, int r) {
    // A temporary array to store all combination one by one
    List<Integer> data = new ArrayList<>(Collections.nCopies(r, 0));

    // Print all combination using temporary array 'data'
    combinationUtil(list, data, 0, n - 1, 0, r);
}

public static void main(String[] args) {
    List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
    int r = 3;
    int n = list.size();
    printCombination(list, n, r);
}

Collectives™ on Stack Overflow

How to get a collection of combinations of an Integer arrayList in Java

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related