Permutation of Numbers in Java

2025年4月2日 | 阅读 8 分钟

在本节中，我们将创建一个Java程序来查找数字的排列和循环排列。在继续本节之前，首先我们将通过示例理解排列。

排列

在数学中，排列是一种方法或技术，通过它可以确定集合中可能的排列。在考虑顺序的情况下选择和排列项目的数量。简而言之，排列就是排列的数量。在确定排列时，请牢记顺序。它用字母P表示。

换句话说，这是一种技术，通过它可以按特定顺序从给定的 n 个对象中排列（或选择）r 个对象。

在数学上，我们可以使用以下公式找到数字的排列

其中，

P： P 是排列的数量。

n： n 是集合中对象的总数。

r： r 是从集合中选择对象的数量。

!：这个符号表示阶乘。

例如，如果 XYZ 是一个单词，那么该单词的可能排列是

XYZ, XZY, YXZ, YZX, ZXY, ZYX

因此，我们可以以六种不同的方式排列单词 XYZ。

让我们看一个示例。

示例：有六个人参加短剧表演。有多少种方式可以颁发一等奖和二等奖？

解决方案

给定

n=6, r=2, P=?

根据上述公式

分子和分母中都出现了 4, 3, 2, 1，因此它们被抵消了。

P(6,2)=6*5

P(6,2)=30

因此，有 30 种可能的奖项组合方式来颁发一等奖和二等奖。

让我们在 Java 程序中实现上述方法。

PermutationExample1.java

import java.util.*;  
public class PermutationExample1
{  
public static void main(String args[])  
{  
//totalobjects=n, selectedobjects=r
int totalobjects, selectedobject, permutation, f1, f2;  
//creating a constructor of the Scanner class
Scanner sc = new Scanner(System.in);  
System.out.println("Enter the Value of n and r: ");  
//reading the value of n 
totalobjects = sc.nextInt();  
//reading the value of r
selectedobject = sc.nextInt();  
f1 = totalobjects;  
for (int i = totalobjects - 1; i >= 1; i--)  
{  
f1 = f1 * i;  
}  
int number;  
number = totalobjects - selectedobject;  
f2 = number;  
for (int i = number - 1; i >= 1; i--)  
{  
//determining the factorial
f2 = f2 * i;  
}  
permutation = f1 / f2;  
//prints the permutation
System.out.println("The permutation of P(n, r) = "+permutation);  
}  
}  

输出

Enter the Value of n and r: 
7 4
The permutation of P(n, r) = 840

让我们创建另一个 Java 程序，查找大于自身数字的数字 n 的排列。

PermutationExample2.java

public class PermutationExample2
{
//main() method
public static void main(String args[]) 
{
//the number to be permutate	
int number = 123;
findPermutation(number);
}
//static method to find the permutation
static void findPermutation(int number) 
{
int temp = number, count = 0;
//iteration over the specified digit 
while (temp > 0) 
{
//increments the count variable by 1 i the above condition returns true    
count++;
//divides the variable temp by 10
temp = temp / 10;
}
//using vector to print the permutation of N
int[] num = new int[count];
// Store digits of N
// in the vector num
while (number > 0)
{
//finds the remainder and store the digit in vector num
num[count-- - 1] = number % 10;
number = number / 10;
}
//iterate over each permutation and find the permutations that are greater than N
while (findsNextpermutation(num)) 
{

for (int i = 0; i < num.length; i++)
//print all the permutations of N
System.out.print(num[i]);
//throw the cursor to the new line
System.out.print("\n");
}
}
//the user-defined function finds all the permutation greater than the number itself
static boolean findsNextpermutation(int[] p) 
{
for (int a = p.length - 2; a >= 0; --a)
if (p[a] < p[a + 1])
for (int b = p.length - 1;; --b)
if (p[b] > p[a]) 
{
//swapping logic
int t = p[a];
p[a] = p[b];
p[b] = t;
for (++a, b = p.length - 1; a < b; ++a, --b)
{
//swapping logic
t = p[a];
p[a] = p[b];
p[b] = t;
}
return true;
}
return false;
}
}

输出

使用 Heap 算法

这是一个迭代算法。通过使用 Heap 算法，我们可以找到 n 个对象的所有排列。

该算法生成前 n-1 个元素 (n-1)! 的排列，并将最后一个元素附加到每个排列中。这将生成所有以最后一个元素结尾的排列。
如果 n 是奇数，则交换第一个和最后一个元素；如果 n 是偶数，则交换第 i 个元素（i 是从 0 开始的计数器）和最后一个元素，并重复上述算法直到 i 小于 n。
在每次迭代中，该算法将生成所有以当前最后一个元素结尾的排列。

让我们用 Java 程序实现该算法。

PermutationExample3.java

public class PermutationExample3
{
//method to print permutations of specified array
void printPermutations(int array[], int n)
{
for (int i = 0; i < n; i++)
System.out.print(array[i] + " ");
//throws the cursor to the next line
System.out.println();
}
//finds permutation using Heap Algorithm
void findPermutation(int array[], int size, int n)
{
// if size becomes 1, it prints the obtained permutation
if (size == 1)
printPermutations(array, n);
for (int i = 0; i < size; i++) 
{
findPermutation(array, size - 1, n);
//if the length of the array is odd, it swaps the 0th element with the last element 
if (size % 2 == 1) 
{
//performing swapping	
int temp = array[0];
array[0] = array[size - 1];
array[size - 1] = temp;
}
//if the size of the array is even, it swaps the ith element with the last element
else 
{
//taking a temp variable for swapping	
int temp;
//performing swapping 
temp = array[i];
array[i] = array[size - 1];
array[size - 1] = temp;
}
}
}
//main() method
public static void main(String args[])
{
PermutationExample3 p = new PermutationExample3();
//defining an array whose permutation is to find
int array[] = { 8, 2, 6, 7 };
//calling the user-defined method
p.findPermutation(array, array.length, array.length);
}
}

输出

使用递归算法

递归算法使用回溯。它通过每次迭代交换一个元素来确定数字的排列。

让我们用 Java 程序实现该算法。

PermutationExample4.java

public class PermutationExample4 
{ 
public static void main(String args[]) 
{ 
//string to permutate 	
String str = "come"; 
//determines the length of the given string
int length = str.length(); 
PermutationExample4 per= new PermutationExample4();
//calling the method to find the permutation
per.permutation(str, 0, length-1); 
} 
//function that determines the permutations
//str: is the string to permutate
//si: is the starting index
//li: is the last index
private void permutation(String str, int si, int li) 
{ 
if (si == li) 
System.out.println(str); 
else
{ 
for (int i = si; i <= li; i++) 
{ 
//calling user-defined swapping method
str = swapChar(str,si,i); 
//calling permutation() method
permutation(str, si+1, li); 
str = swapChar(str,si,i); 
} 
} 
} 
//user-defined method to swap characters
public String swapChar(String str, int i, int j) 
{ 	
char temp; 
//converts string into character array 
char[] chArray = str.toCharArray(); 
temp = chArray[i] ; 
chArray[i] = chArray[j]; 
chArray[j] = temp; 
//returns string after swapping
return String.valueOf(chArray); 
} 
} 

输出

come
coem
cmoe
cmeo
cemo
ceom
ocme
ocem
omce
omec
oemc
oecm
moce
moec
mcoe
mceo
meco
meoc
eomc
eocm
emoc
emco
ecmo
ecom

随机算法

我们也可以应用随机算法来确定数字的排列。当 n 的值很大时使用它。该算法通过混洗数组来生成排列。对于混洗，Java Collections 类提供了 shuffle() 方法。

shuffle() 方法使用默认的随机源随机排列指定的 List。它以向后（从最后一个元素到第二个元素）的方向遍历列表。它将选定的元素与当前位置随机交换。该方法运行时间为线性。该方法的签名是

生成循环排列

由单个循环组成的排列称为循环排列。它以固定的偏移量移动集合的所有元素。该技术可以应用于任何整数，以任意数量的位置循环右移或左移。如果一个集合的元素为 {a, b, c}，则

循环排列向左移动一位生成：{c, a, b}
循环排列向右移动一位生成：{a, b, c}

假设 n 是要查找其循环排列的数字。我们可以通过以下步骤找到循环排列。它生成下一个排列。

remainder = number % 10;
div = number / 10;
number = (pow(10, n - 1)) * remainder + div;

我们执行上述步骤，直到得到原始数字。一旦我们得到原始数字，我们就停止执行上述步骤并返回余数。

例如，求以下分数的除法

2/7 = 0.285714...

4/7 = 0.571428...

1/7 = 0.142857...

让我们创建一个 Java 程序，生成所有可能的循环排列。

PermutationExample5.java

public class PermutationExample5 
{ 
//the function finds the total number of digits in a number 
static int noOfDigits(int N) 
{ 
int count = 0; 
while (N>0) 
{
//increments the variable count by 1 if n>0	
count++; 
//divides the variable n by 10 
N = N / 10; 
} 
//returns the total number of digits
return count; 
} 
//the function generates the cyclic permutations
static void cyclicPermutation(int N) 
{ 
int num = N; 
int n = noOfDigits(N); 
while (true) 
{ 
System.out.println(num); 
//the next three statements generate the cyclic permutations
int remainder = num % 10; 
int dev = num / 10; 
num = (int)((Math.pow(10, n - 1)) * remainder + dev); 
//if the condition is true, it exits from the loop
if (num == N) 
break; 
} 
} 
//main() method 
public static void main (String args[]) 
{ 
//number to permutate	
int N = 9871; 
//calling the user-defined method
cyclicPermutation(N); 
} 
} 

输出

下一个主题Void-keyword-in-java

Permutation of Numbers in Java

排列

使用 Heap 算法

使用递归算法

随机算法

生成循环排列

联系信息

关注我们

教程

面试题

在线编译器

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

Permutation of Numbers in Java

排列

使用 Heap 算法

使用递归算法

随机算法

生成循环排列

相关帖子

Amicable Pair Number in Java

Java 中的 java.net.MulticastSocket 类

Java 程序使用两个线程打印奇偶数

Java 中的摇摆排序

Java SwingWorker 类

Java 中打印二叉树的所有回文级别

Read CSV File in Java

DecimalFormat getMaximumIntegerDigits() method in Java

Java 中的接口变量

Java 8 和 Java 9 的区别

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器