Combinations program in java

Combinations program in java

Learn Latest Tutorials

Preparation

Trending Technologies

B.Tech / MCA

Javatpoint Services

JavaTpoint offers too many high quality services. Mail us on h[email protected], to get more information about given services.

• Website Designing
• Website Development
• Java Development
• PHP Development
• WordPress
• Graphic Designing
• Logo
• Digital Marketing
• On Page and Off Page SEO
• PPC
• Content Development
• Corporate Training
• Classroom and Online Training
• Data Entry

Training For College Campus

JavaTpoint offers college campus training on Core Java, Advance Java, .Net, Android, Hadoop, PHP, Web Technology and Python. Please mail your requirement at [email protected].
Duration: 1 week to 2 week

Like/Subscribe us for latest updates or newsletter

Источник

Generate All Possible Combinations in Java

1. Use Recurrence to Generate All Possible Combinations in Java
2. Use Include-Exclude to Generate All Possible Combinations in Java

This tutorial demonstrates how to generate all possible combinations of the elements of an array in Java.

Use Recurrence to Generate All Possible Combinations in Java

First, we create an empty array that will store the outputs. The idea is to fix elements one by one and then use recurrence.

Finally, when the number of elements in the initial array becomes equal to the size of combinations, then we print the initial array. Let’s try to implement it in Java.

package delftstack;  import java.io.*;  public class Possible_Combinations    static void CombinationPossible(int Input_Array[], int Empty_Array[], int Start_Element, int End_Element, int Array_Index, int r)   // Current combination is ready to be printed, print it  if (Array_Index == r)   for (int x=0; xr; x++)   System.out.print(Empty_Array[x]+" ");  >  System.out.println("");  return;  >   for (int y=Start_Element; yEnd_Element && End_Element-y+1 >= r-Array_Index; y++)   Empty_Array[Array_Index] = Input_Array[y];  CombinationPossible(Input_Array, Empty_Array, y+1, End_Element, Array_Index+1, r);  >  >   static void Print_Combination(int Input_Arrary[], int n, int r)   int Empty_Array[]=new int[r];  CombinationPossible(Input_Arrary, Empty_Array, 0, n-1, 0, r);  >   public static void main (String[] args)   int Input_Array[] = 10,30, 50, 70, 90, 100>;  int r = 3;  int n = Input_Array.length;  Print_Combination(Input_Array, n, r);  > > 

The code above will generate all the possible combinations of the given array in the form of three numbers. See output:

10 30 50 10 30 70 10 30 90 10 30 100 10 50 70 10 50 90 10 50 100 10 70 90 10 70 100 10 90 100 30 50 70 30 50 90 30 50 100 30 70 90 30 70 100 30 90 100 50 70 90 50 70 100 50 90 100 70 90 100 

Use Include-Exclude to Generate All Possible Combinations in Java

Similarly, we create an empty array and use the Pascal identity problem to generate all the possible combinations of an array.

In this method, we consider the elements of the given array and recure using the two cases. The first case is the element included in the current combination.

The second case is that element is excluded in the current combination. Let’s try to implement this method in Java.

package delftstack;  import java.io.*;  public class Possible_Combinations    static void PossibleCombinations(int Input_Array[], int n, int Length, int Array_Index,  int Empty_Array[], int x)   if (Array_Index == Length)   for (int y=0; yLength; y++)  System.out.print(Empty_Array[y]+" ");  System.out.println("");  return;  >   if (x >= n)  return;   Empty_Array[Array_Index] = Input_Array[x];  PossibleCombinations(Input_Array, n, Length, Array_Index+1, Empty_Array, x+1);   PossibleCombinations(Input_Array, n, Length, Array_Index, Empty_Array, x+1);  >   static void Print_Combination(int Input_Array[], int n, int Length)   int Empty_Array[]=new int[Length];   PossibleCombinations(Input_Array, n, Length, 0, Empty_Array, 0);  >   public static void main (String[] args)   int Input_Array[] = 10,30, 50, 70, 90, 100>;  int Length = 3;  int n = Input_Array.length;  Print_Combination(Input_Array, n, Length);  > > 

The code above will generate all the possible combinations of the given array in the form of three numbers. See output:

10 30 50 10 30 70 10 30 90 10 30 100 10 50 70 10 50 90 10 50 100 10 70 90 10 70 100 10 90 100 30 50 70 30 50 90 30 50 100 30 70 90 30 70 100 30 90 100 50 70 90 50 70 100 50 90 100 70 90 100 

Sheeraz is a Doctorate fellow in Computer Science at Northwestern Polytechnical University, Xian, China. He has 7 years of Software Development experience in AI, Web, Database, and Desktop technologies. He writes tutorials in Java, PHP, Python, GoLang, R, etc., to help beginners learn the field of Computer Science.

Источник

Print all possible combinations of r elements in a given array of size n

Given an array of size n, generate and print all possible combinations of r elements in array. For example, if input array is and r is 2, then output should be , , , , and .
Following are two methods to do this.
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 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[].
Following diagram shows recursion tree for same input.

Following is the implementation of the above approach.

C++

C

Java

Python3

C#

PHP

Javascript

1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5

Time Complexity: O(n^2)
Auxiliary Space: O(r). We use a temporary array data[] of size r to store current combination.

How to handle duplicates?
Note that the above method doesn’t handle duplicates. For example, if input array is and r is 2, then the program prints and as two different combinations. We can avoid duplicates by adding following two additional things to above code.
1) Add code to sort the array before calling combinationUtil() in printCombination()
2) Add following lines at the end of for loop in combinationUtil()

// Since the elements are sorted, all occurrences of an element // must be together while (arr[i] == arr[i+1]) i++;

See this for an implementation that handles duplicates.
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.
This method is mainly based on Pascal’s Identity, i.e. n_cr = n-1_cr + n-1_cr-1
Following is implementation of method 2.

Источник