迹忆客 专注技术分享

本文介绍如何在 Java 中生成数组元素的所有可能组合。

在 Java 中使用递归生成所有可能的组合

首先，我们创建一个空数组来存储输出。这个想法是一个一个地修复元素，然后使用递归。

最后，当初始数组中的元素数量等于组合的大小时，我们打印初始数组。让我们尝试在 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; x<r; x++) {
                System.out.print(Empty_Array[x]+" ");
            }
            System.out.println("");
            return;
        }

        for (int y=Start_Element; y<=End_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);
    }
}

上面的代码将以三个数字的形式生成给定数组的所有可能组合。见输出：

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

在 Java 中使用包括-排除法生成所有可能的组合

同样，我们创建一个空数组并使用 Pascal 恒等问题来生成数组的所有可能组合。

在这种方法中，我们考虑给定数组的元素并使用这两种情况进行递归。第一种情况是当前组合中包含的元素。

第二种情况是当前组合中排除了该元素。让我们尝试在 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; y<Length; 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);
    }
}

上面的代码将以三个数字的形式生成给定数组的所有可能组合。见输出：

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