在Java中打印大小为n的给定整数数组中r元素的所有可能排列 [英] print all possible permutations of r elements in a given integer array of size n in Java
问题描述
给定一个大小为n的数组,生成并打印数组中r元素的所有可能排列。
Given an array of size n, generate and print all possible permutations of r elements in array.
例如,如果n为4,则输入数组为[0 ,1,2,3],并且r是3,那么输出应该是
For example, if n is 4, input array is [0, 1, 2, 3], and r is 3, then output should be
[0, 1, 2]
[0, 1, 3]
[0, 2, 1]
[0, 2, 3]
[0, 3, 1]
[0, 3, 2]
[1, 0, 2]
[1, 0, 3]
[1, 2, 0]
[1, 2, 3]
[1, 3, 0]
[1, 3, 2]
[2, 0, 1]
[2, 0, 3]
[2, 1, 0]
[2, 1, 3]
[2, 3, 0]
[2, 3, 1]
[3, 0, 1]
[3, 0, 2]
[3, 1, 0]
[3, 1, 2]
[3, 2, 0]
[3, 2, 1]
输入数组中的所有元素都是整数,从0到n-1。如何使用Java打印所有可能的排列?
All elements in the input array are integers, from 0 to n-1. How can I use Java to print all possible permutations?
重要提示:单个排列中所有元素的数量并不总是原始数组的大小。它小于或等于原始数组的大小。此外,每个排列中元素的顺序都很重要。
我在n = 4和r = 3时编写了一些代码。如果n = 100且r = 50,我的代码将非常难看。当参数只有n和r时,有没有聪明的方法呢?
I have written some code when n=4 and r=3. If n = 100 and r = 50, my code will be really ugly. Is there any smart way to do this when parameters are only n and r?
public static void main(String[] args) {
// original array
ArrayList < Integer > items = new ArrayList < > ();
// all permutations
ArrayList < ArrayList < Integer >> allPermutations = new ArrayList < ArrayList < Integer >> ();
// define the end item of the original array.
// this is n, suppose it's 4 now.
int endItem = 4;
for (int i = 0; i < endItem; i++) {
items.add(i);
}
// r means how many elements in each single permutation
// suppose it's 3 now, i have to write for-loop three times
// if r is 100, i have to write for-loop 100 times
// first of the "r"
for (int i = 0; i < items.size(); i++) {
// second of the "r"
for (int j = 0; j < items.size(); j++) {
// can't be identical to i
if (j == i)
continue;
// third of the "r"
for (int k = 0; k < items.size(); k++) {
// can't be identical to i or j
if (k == i || k == j)
continue;
// a single permutation
ArrayList < Integer > singlePermutation = new ArrayList < > ();
singlePermutation.add(items.get(i));
singlePermutation.add(items.get(j));
singlePermutation.add(items.get(k));
// all permutations
allPermutations.add(singlePermutation);
}
}
}
for (ArrayList < Integer > permutation: allPermutations) {
System.out.println(permutation);
}
System.out.println(allPermutations.size());
}
推荐答案
移动解决方案从问题到答案:
Moved solution from question to answer:
解决方案:
感谢较旧的编码器,我设法找到了解决方案。
Thanks to older coder, I managed to find the solution.
public class PermutationTest10 {
// a is the original array
// k is the number of elements in each permutation
public static ArrayList<ArrayList<Integer>> choose(ArrayList<Integer> a, int k) {
ArrayList<ArrayList<Integer>> allPermutations = new ArrayList<ArrayList<Integer>>();
enumerate(a, a.size(), k, allPermutations);
return allPermutations;
}
// a is the original array
// n is the array size
// k is the number of elements in each permutation
// allPermutations is all different permutations
private static void enumerate(ArrayList<Integer> a, int n, int k, ArrayList<ArrayList<Integer>> allPermutations) {
if (k == 0) {
ArrayList<Integer> singlePermutation = new ArrayList<Integer>();
for (int i = n; i < a.size(); i++){
singlePermutation.add(a.get(i));
}
allPermutations.add(singlePermutation);
return;
}
for (int i = 0; i < n; i++) {
swap(a, i, n-1);
enumerate(a, n-1, k-1, allPermutations);
swap(a, i, n-1);
}
}
// helper function that swaps a.get(i) and a.get(j)
public static void swap(ArrayList<Integer> a, int i, int j) {
Integer temp = a.get(i);
a.set(i, a.get(j));
a.set(j, temp);
}
// sample client
public static void main(String[] args) {
// n is the end item of the array.
// if n = 5, the array is [0, 1, 2, 3, 4, 5]
// k is the number of elements of each permutation.
int n =5;
int k =3;
// create original array
ArrayList<Integer> elements = new ArrayList<> ();
for (int i =0; i < n; i ++){
elements.add(i);
}
ArrayList<Integer> a = new ArrayList<> ();
for (int i = 0; i < n; i ++){
a.add(elements.get(i));
}
System.out.println(choose(a, k));
}
}
这篇关于在Java中打印大小为n的给定整数数组中r元素的所有可能排列的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!