Java 中的排列程序

2024 年 9 月 10 日 | 阅读 3 分钟

组合学的排列基本思想是在多个顺序中排列一系列项。我们将通过几种在 Java 中创建排列的技术，并附带代码示例和详细说明。

排列是如何发生的？

排列是元素在特定序列中的组织。它涉及以特定的线性或顺序排列集合的成员。例如，考虑集合 A={11,66}。在此问题中，只有两种可能的排列：{11,66} 和 {66,11}。该集合没有其他可能的排列。

方法 1：递归技术

递归方法是创建排列的最简单技术之一。此 Java 程序使用递归来创建数组的排列。

PermutationsRecursive.java

import java.util.*;
public class PermutationsRecursive {
    public static void generate(int[] a, int len) {
        if (len == 1) {
            System.out.println(Arrays.toString(a));
        } else {
            for (int j = 0; j < len; j++) {
                int temp = a[j];
                a[j] = a[len - 1];
                a[len - 1] = temp;
                generate(a, len - 1);
                temp = a[j];
                a[j] = a[len - 1];
                a[len - 1] = temp;
            }
        }
    }
    public static void main(String[] args) {
        int[] a = {100, 120 , 230};
	int n=a.length;
        generate (a, n);
    }
}

输出

[100, 120, 230]
[100, 230, 120]
[120, 100, 230]
[120, 230, 100]
[230, 100, 120]
[230, 120, 100]

解释

此代码使用递归创建数组的排列。它通过交换数组中的元素来输出创建的各种排序。在最简单的情况下，当 n（数组长度）等于 1 时，数组将被打印。

方法 2：字典序（Lexicographic Sequence）

字典序是创建排列的另一种方法。当您需要按特定顺序查找排列时，可以使用此方法逐个生成排列。此 Java 程序生成按字典序排序的排列。

PermutationsLexicographic.java

import java.util.*;

public class PermutationsLexicographic {
    public static void generate (int[] a) {
        Arrays.sort(a);
        boolean hasNext = true;
        while (hasNext) {
            System.out.println(Arrays.toString(a));
	Int n=a.length;
            int i = n - 2;
            while (i >= 0 && a[i] >= a[i + 1]) {
                i--;
            }            
            if (i < 0) {
                hasNext = false;
            } else {
                int j = n - 1;
                while (a[j] <= a[i]) {
                    j--;
                }
                swap(a, i, j);
                reverse(a, i + 1);
            }
        }
    }

    public static void swap(int[] arr, int a, int b) {
        int t = arr[a];
        arr[a] = arr[b];
        arr[b] = t;
    }

    public static void reverse(int[] a, int first) {
	int n=a.length;
        int last = n-1;
        while (first< last) {
            swap(a, first, last);
            first++;
            last--;
        }
    }

    public static void main(String[] args) {
        int[] a = {100, 120, 230};
        generate (a);
    }
}

输出

[100, 120, 230]
[100, 230, 120]
[120, 100, 230]
[120, 230, 100]
[230, 100, 120]
[230, 120, 100]

解释

此代码中的项首先被排序，然后我们通过迭代查找下一个字典序更大的排列。`generatePermutations` 方法利用了一个事实，即识别最右边可以增加的元素为每一步提供了基础。

方法 3：不使用外部库

PermutationsWithoutLibraries.java

import java.util.*;
public class PermutationsWithoutLibraries{
    public static void generate(ArrayList<Integer> nums, ArrayList<Integer> combination, ArrayList<List<Integer>> answer) {
        if (nums.isEmpty()) {
            answer.add(new ArrayList<>(combination));
            return;
        }

        for (int j = 0; j < nums.size(); j++) {
            int cur = nums.get(j);
            combination.add(cur);
            ArrayList<Integer> remainingPart = new ArrayList<>(nums);
            remainingPart.remove(j);
            generate(remainingPart, combination, answer);
            combination.remove(combination.size() - 1);
        }
    }

    public static void main(String[] arguments) {
        List<Integer> nums = List.of(100, 120, 230);
        ArrayList<List<Integer>> combinations = new ArrayList<>();
        generate(new ArrayList<>(nums), new ArrayList<>(), combinations);

        for (List<Integer> perm : combinations) {
            System.out.println(perm);
        }
    }
}

输出

[100, 120, 230]
[100, 230, 120]
[120, 100, 230]
[120, 230, 100]
[230, 100, 120]
[230, 120, 100]

解释

在此代码中，我们使用组件列表、当前排列和用于保存结果的列表来构建一个名为 `generatePermutations` 的递归函数。通过将每个元素添加到当前排列并从剩余组件中删除它，该函数会迭代生成所有可能的排列。

结论

创建排列是一个常见的问题，可以通过多种方法解决。我们研究了三种使用 Java 的方法：字典序、递归和使用 Collections。您选择的策略将取决于您的特定需求和限制。这些示例应该有助于您理解 Java 排列生成的概念，并为更复杂的排列相关任务奠定基础。

下一个主题Java 中的 Profile Annotation

Java 中的排列程序

排列是如何发生的？

方法 1：递归技术

方法 2：字典序（Lexicographic Sequence）

方法 3：不使用外部库

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中的排列程序

排列是如何发生的？

方法 1：递归技术

方法 2：字典序（Lexicographic Sequence）

方法 3：不使用外部库

结论

相关帖子

Java 中替换 ArrayList 中的元素

Java 中的托普利茨矩阵

Java 中的 Giuga 数

ISBN Number Java

How to Get Value from JSON Object in Java Example

Java 中的 Strobogrammatic 数

Java Program to Find Pythagorean Triplets in an Array

Java 中的 HMAC 加密

Java Boyer Moore

Java 8 vs Java 11

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器