Last active
September 19, 2022 06:36
-
-
Save ExcaliburZero/7539f57b9a50608f2355 to your computer and use it in GitHub Desktop.
Heap's Algorithm - Java Implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* Heap's algorithm | |
* | |
* Gives all permutations for the numbers 1 through n. | |
* | |
* Java implementation for psuedocode on the algorithm's Wikipedia article: | |
* https://en.wikipedia.org/wiki/Heap%27s_algorithm | |
*/ | |
import java.util.Scanner; | |
public class Main { | |
public static void main(String[] args) { | |
// Scanner to take in input from user | |
Scanner kb = new Scanner(System.in); | |
// Prompt the user for the value of n | |
System.out.print("n = "); | |
int n = kb.nextInt(); | |
// Create and fill an array with the numbers 1 to n | |
int [] myArray = new int[n]; | |
for(int i = 0; i < n; i++) { | |
myArray[i] = i + 1; | |
} | |
// Run generation function | |
generate(n, myArray); | |
} | |
/** | |
* The method used to generate all of the possible permutations of the | |
* numbers 1 through n. | |
* | |
* @param n The number of numbers to create permutations of | |
* @param a The array of numbers 1 through n | |
*/ | |
public static void generate(int n, int[] a) { | |
// Placeholder for swapping values | |
int tmp; | |
// If a new permutation has been found then print it | |
if(n == 1) { | |
// Print out the found permutation | |
for(int i = 0; i < a.length; i++) { | |
System.out.print(a[i]); | |
} | |
System.out.println(); | |
} | |
else { // If a new permutation has not yet been found | |
for(int i = 0; i < (n-1); i++) { | |
generate(n-1, a); | |
if(n % 2 == 0) { | |
// Swap entry i with entry n-1 | |
tmp = a[i]; | |
a[i] = a[n-1]; | |
a[n-1] = tmp; | |
} | |
else { | |
// Swap entry 0 with entry n-1 | |
tmp = a[0]; | |
a[0] = a[n-1]; | |
a[n-1] = tmp; | |
} | |
} | |
generate(n-1, a); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment