Как получить коллекцию комбинаций Integer arrayList в Java? - PullRequest
Новая
       16

Как получить коллекцию комбинаций Integer arrayList в Java?

0 голосов
/ 24 июня 2018

Моя цель - найти все возможные комбинации элементов в ArrayList с фиксированной предварительно определенной длиной.Например, если мой ArrayList называется arr и содержит <1, 2, 3>, то желаемый вывод для предопределенного размера r = 2 будет: 

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

Вот код, который я нашел, который печатает желаемый вывод.Моя проблема заключается в том, что мне нужно определить тип возвращаемого значения ArrayList, который содержит выходные данные метода.Кроме того, мой тип ввода также ArrayList<Integer> вместо массива, что усложнило для меня, потому что тогда мне сначала нужно будет преобразовать значения в примитивный тип 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 */

1 Ответ

0 голосов
/ 24 июня 2018

ArrayList поддерживается внутренним массивом, поэтому целесообразно перевести текущую реализацию на основе array в ArrayList. В arrays вы используете оператор [] для индексации элемента в array, а параллельные операции, использующие ArrayList: get и set. Также вы можете прочитать на Autoboxing and Unboxing. Возможная реализация с использованием 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);
}
...