Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Algorithm to get all the combinations of size n from an array (Java)? [closed]

Right now I'm trying to write a function that takes an array and an integer n, and gives a list of each size n combination (so a list of int arrays). I am able to write it using n nested loops, but this only works for a specific size of subset. I can't figure out how to generalize it to work for any size of combination. I think I need to use recursion?

This is the code for all combinations of 3 elements, and I need an algorithm for any number of elements.

import java.util.List; import java.util.ArrayList;  public class combinatorics{     public static void main(String[] args) {          List<int[]> list = new ArrayList<int[]>();         int[] arr = {1,2,3,4,5};         combinations3(arr,list);         listToString(list);     }      static void combinations3(int[] arr, List<int[]> list){         for(int i = 0; i<arr.length-2; i++)             for(int j = i+1; j<arr.length-1; j++)                 for(int k = j+1; k<arr.length; k++)                     list.add(new int[]{arr[i],arr[j],arr[k]});     }      private static void listToString(List<int[]> list){         for(int i = 0; i<list.size(); i++){ //iterate through list             for(int j : list.get(i)){ //iterate through array                 System.out.printf("%d ",j);             }         System.out.print("\n");         }     } } 
like image 436
pyjamas Avatar asked Apr 28 '15 04:04

pyjamas


People also ask

How do you generate all possible combinations of a set of numbers in Java?

We use the size() method to get the number of elements in the list. We set a constant value 2 to r, i.e., the number of items being chosen at a time. After that, we use the combination formula, i.e., fact(n) / (fact(r) * fact(n-r)) and store the result into the result variable.

How do you find the sum of all combinations of an array?

Follow the below steps to implement the idea: Sort the array arr[] and remove all the duplicates from the arr[] then create a temporary vector r. to store every combination and a vector of vector res. Recursively follow: If at any time sub-problem sum == 0 then add that array to the res (vector of vectors).

How do you find the combinations of 4 numbers in Java?

You can do it like: str+=String. valueOf(w) + String. valueOf(x) + String. valueOf(y)+ String.

How do you find all possible combinations?

Remember, the formula to calculate combinations is nCr = n! / r! * (n - r)!, where n represents the number of items, and r represents the number of items being chosen at a time. Let's look at an example of how to calculate a combination.


2 Answers

This is a well-studied problem of generating all k-subsets, or k-combinations, which can be easily done without recursion.

The idea is to have array of size k keeping sequence of indices of elements from the input array (which are numbers from 0 to n - 1) in increasing order. (Subset then can be created by taking items by these indices from the initial array.) So we need to generate all such index sequences.

First index sequence will be [0, 1, 2, ... , k - 1], on the second step it switches to [0, 1, 2,..., k], then to [0, 1, 2, ... k + 1] and so on. The last possible sequence will be [n - k, n - k + 1, ..., n - 1].

On each step, algorithm looks for the closest to the end item which can be incremented, increments it and fills up items right to that item.

To illustrate, consider n = 7 and k = 3. First index sequence is [0, 1, 2], then [0, 1, 3] and so on... At some point we have [0, 5, 6]:

[0, 5, 6] <-- scan from the end: "6" cannot be incremented, "5" also, but "0" can be [1, ?, ?] <-- "0" -> "1" [1, 2, 3] <-- fill up remaining elements  next iteration:  [1, 2, 3] <-- "3" can be incremented [1, 2, 4] <-- "3" -> "4" 

Thus, [0, 5, 6] is followed by [1, 2, 3], then goes [1, 2, 4] etc.

Code:

int[] input = {10, 20, 30, 40, 50};    // input array int k = 3;                             // sequence length     List<int[]> subsets = new ArrayList<>();  int[] s = new int[k];                  // here we'll keep indices                                         // pointing to elements in input array  if (k <= input.length) {     // first index sequence: 0, 1, 2, ...     for (int i = 0; (s[i] = i) < k - 1; i++);       subsets.add(getSubset(input, s));     for(;;) {         int i;         // find position of item that can be incremented         for (i = k - 1; i >= 0 && s[i] == input.length - k + i; i--);          if (i < 0) {             break;         }         s[i]++;                    // increment this item         for (++i; i < k; i++) {    // fill up remaining items             s[i] = s[i - 1] + 1;          }         subsets.add(getSubset(input, s));     } }  // generate actual subset by index sequence int[] getSubset(int[] input, int[] subset) {     int[] result = new int[subset.length];      for (int i = 0; i < subset.length; i++)          result[i] = input[subset[i]];     return result; } 
like image 128
Alex Salauyou Avatar answered Sep 21 '22 13:09

Alex Salauyou


If I understood your problem correctly, this article seems to point to what you're trying to do.

To quote from the article:

Method 1 (Fix Elements and Recur)

We create a temporary array ‘data[]’ which stores all outputs one by one. The idea is to start from first index (index = 0) in data[], one by one fix elements at this index and recur for remaining indexes. Let the input array be {1, 2, 3, 4, 5} and r be 3. We first fix 1 at index 0 in data[], then recur for remaining indexes, then we fix 2 at index 0 and recur. Finally, we fix 3 and recur for remaining indexes. When number of elements in data[] becomes equal to r (size of a combination), we print data[].

Method 2 (Include and Exclude every element)

Like the above method, We create a temporary array data[]. The idea here is similar to Subset Sum Problem. We one by one consider every element of input array, and recur for two cases:

  1. The element is included in current combination (We put the element in data[] and increment next available index in data[])
  2. The element is excluded in current combination (We do not put the element and do not change index)

When number of elements in data[] become equal to r (size of a combination), we print it.

like image 29
Roney Michael Avatar answered Sep 21 '22 13:09

Roney Michael