All combinations array java

Java java get all combinations of array

For the first step (0), I fill the arrays with the numbers from x, leaving their remaining elements uninitialized: Then I fill the remaining elements of each array step by step. Solution: A recursive implementation of any algorithm is comprised of two parts: base case — a condition that terminates a branch of recursive calls and represents an edge case for which result is known in advance; recursive case — a part where the logic resides and the recursive calls are made.

Create a list of combinations recursively

A recursive implementation of any algorithm is comprised of two parts:

• base case — a condition that terminates a branch of recursive calls and represents an edge case for which result is known in advance;
• recursive case — a part where the logic resides and the recursive calls are made.

For this task a base case will be a situation when size of the combination equals to a target size (denoted as r in your code, in the code below I gave it a name targetSize ).

Explanation of the recursive logic :

• Every method call tracks its own combination ;
• Every combination unless it reaches the targetSize is used as a blue-print for other combinations ;
• Each item from the source of data can be used only once , hence when it’s being added to a combination it must be removed from the source.

The type ArrayList which you are using to store the combination isn’t a good choice. Arrays and generics do not play well together. List> will be more appropriate for this purpose.

Also in my code List is used as a source of data instead of an array, which isn’t a complicated conversion and can be achieved easily.

Pay attention to the comments in the code.

 private List> createCombination(List source, List comb, int targetSize) < if (comb.size() == targetSize) < // base condition of the recursion List> result = new ArrayList<>(); result.add(comb); return result; > List> result = new ArrayList<>(); Iterator iterator = source.iterator(); while (iterator.hasNext()) < // taking an element from a source Integer item = iterator.next(); iterator.remove(); // in order not to get repeated the element has to be removed // creating a new combination using existing as a base ListnewComb = new ArrayList<>(comb); newComb.add(item); // adding the element that was removed from the source result.addAll(createCombination(new ArrayList<>(source), newComb, targetSize)); // adding all the combinations generated > return result; > 

For the input

 createCombination(new ArrayList<>(List.of(1, 2, 3)), new ArrayList<>(), 2)); 

It’ll produce the output

How to get all possible combinations from two arrays?, You can use streams to get all possible combinations of two arrays. First, iterate over the numbers array

Get all combinations for arbitrary number of elements

I have an idea how to solve this with an iterative algorithm, without recursion:

import java.util.ArrayList; import java.util.Arrays; import java.util.List; class Main < static ListgetAll(int n, int[] x) < Listcombinations = new ArrayList<>(); // First step (0) // Create initial combinations, filled with the first number. for (int number = 0; number < x.length; number++) < int[] array = new int[n]; // the final size of each array is already known array[0] = x[number]; // fill the first number combinations.add(array); >// In each following step, we add one number to each combination for (int step = 1; step < n; step++) < // Backup the size because we do not want to process // the new items that are added by the following loop itself. int size = combinations.size(); // Add one number to the existing combinations for (int combination = 0; combination < size; combination++) < // Add one number to the existing array int[] array = combinations.get(combination); array[step] = x[0]; // For all additional numbers, create a copy of the array for (int number = 1; number < x.length; number++) < int[] copy = Arrays.copyOf(array, array.length); copy[step] = x[number]; combinations.add(copy); >> > return combinations; > public static void main(String[] args) < int[] x = ; int n = 3; // Calculate all possible combinations List combinations = getAll(n, x); // Print the result for (int[] combination : combinations) < System.out.println(Arrays.toString(combination)); >> > 

Each array has a well known size (n) so I can create them immediately with the final size.

For the first step (0), I fill the arrays with the numbers from x, leaving their remaining elements uninitialized:

Then I fill the remaining elements of each array step by step. But during that, the number of possible combinations increases, so I makes copies of the existing arrays and add all possible combinations to the result list.

The next step (1) fills the second column:

[3, ?, ?] update to [3, 3, ?] copy to [3, 5, ?] copy to [3, 7, ?] [5, ?, ?] update to [5, 3, ?] copy to [5, 5, ?] copy to [5, 7, ?] [7, ?, ?] update to [7, 3, ?] copy to [7, 5, ?] copy to [7, 7, ?] 

The next step fills the third column:

[3, 3, ?] update to [3, 3, 3] copy to [3, 3, 5] copy to [3, 3, 7] [3, 5, ?] update to [3, 5, 3] copy to [3, 5, 5] copy to [3, 5, 7] [3, 7, ?] update to [3, 7, 3] . and so on [5, 3, ?] [5, 5, ?] [5, 7, ?] [7, 3, ?] [7, 5, ?] [7, 7, ?] 

My code uses arrays of int , but that works as well with double . I think that algorithm will work with any number of iterations.

Here is a recursive way of doing that.

private static void combine(int n, double[] x, List> combinations, List combination) < if (combination.size() == n) < combinations.add(combination); >else < for (int i = 0; i < x.length; i++) < ListnewCombination = new ArrayList<>(combination); newCombination.add(x[i]); combine(n, x, combinations, newCombination); > > > public static List> getCombinations(int n, double[] x) < List> combinations = new ArrayList<>(); combine(n, x, combinations, new ArrayList<>()); return combinations; > public static void main(String[] args) < getCombinations(2, new double[] ).forEach(System.out::println); > 

The same way but with double[] .

private static void combine(int n, double[] x, List combinations, double[] combination) < if (combination.length == n) < combinations.add(combination); >else < for (int i = 0; i < x.length; i++) < double[] newCombination = Arrays.copyOf(combination, combination.length + 1); newCombination[combination.length] = x[i]; combine(n, x, combinations, newCombination); >> > public static List getCombinations(int n, double[] x) < Listcombinations = new ArrayList<>(); combine(n, x, combinations, new double[] <>); return combinations; > public static void main(String[] args) < getCombinations(2, new double[] ).forEach(doubleArray -> ); > 

Algorithm to get all the combinations of size n from an array (Java)?, 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

Get all possible combinations of two array of string

import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; import static java.util.stream.Collectors.toList; public class Perm2 < public static void main(String[] args) < ListlistA = Arrays.asList("1", "2", "3"); List listB = Arrays.asList("a", "b", "c"); List result = perm2(listA, 2, listB, 1); result.forEach(System.out::println); System.out.println("--- count = " + result.size()); > private static List perm2(List listA, int numA, List listB, int numB) < if (numA == 0 && numB == 0) return Collections.singletonList(""); ListforSelect = new ArrayList<>(); if (numA > 0) forSelect.addAll(listA); if (numB > 0) forSelect.addAll(listB); List result = new ArrayList<>(); for (String elem : forSelect) < ListnewListA = without(listA, elem); int newNumA = numA - (listA.contains(elem) ? 1 : 0); List newListB = without(listB, elem); int newNumB = numB - (listB.contains(elem) ? 1 : 0); result.addAll( perm2(newListA, newNumA, newListB, newNumB).stream() .map(s -> elem + s) .collect(toList())); > return result; > private static List without(List list, String elem) < return list.stream().filter(e ->e != elem).collect(toList()); > > 

I assume that all elements from listA and listB are distinct and that the numbers of elements to choose are in the range 0..length.

Find all combinations of an array and get top k sum elements, Next we need to iterate over positive values, from smallest to largest. For each of these values we calculate sums of new combinations (at the

Источник

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.

Источник

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 

Источник