This is a java program to generate and print all the subsets using the Gray Code Order. The reflected binary code, also known as Gray code after Frank Gray, is a binary numeral system where two successive values differ in only one bit (binary digit). The gray code equivalent of a binary number is (number >> 1) ^ number, i.e. right-shift the number by one and EX-ORing with the original number.
Here is the source code of the Java Program to Generate All Subsets of a Given Set in the Gray Code Order. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
//This is a java program to generate all subsets of given set of numbers using gray code order import java.util.Random; import java.util.Scanner; public class Gray_Code_Permutation { public static int[] grayCode(int N) { int[] grayCode = new int[(int) Math.pow(2, N)]; int[] binary = new int[(int) Math.pow(2, N)]; for (int i = 0; i < Math.pow(2, N); i++) grayCode[i] = (i >> 1) ^ i; for (int i = 0; i < Math.pow(2, N); i++) { int b = 1; binary[i] = 0; while (grayCode[i] > 0) { binary[i] += (grayCode[i] % 2) * b; grayCode[i] /= 2; b = b * 10; } } return binary; } public static void main(String args[]) { Random random = new Random(); Scanner sc = new Scanner(System.in); System.out.println("Enter the number of elements in the set: "); int N = sc.nextInt(); int[] sequence = new int[N]; for (int i = 0; i < N; i++) sequence[i] = Math.abs(random.nextInt(100)); System.out.println("The elements in the set : "); for (int i = 0; i < N; i++) System.out.print(sequence[i] + " "); int[] mask = new int[(int) Math.pow(2, N)]; mask = grayCode(N); System.out.println("\nThe permutations are: "); for (int i = 0; i < Math.pow(2, N); i++) { System.out.print("{ "); for (int j = 0; j < N; j++) { if (mask[i] % 10 == 1) System.out.print(sequence[j] + " "); mask[i] /= 10; } System.out.println("}"); } sc.close(); } }
Output:
$ javac Gray_Code_Permutation.java $ java Gray_Code_Permutation Enter the number of elements in the set: 4 The elements in the set : 36 75 15 59 The permutations are: { } { 36 } { 36 75 } { 75 } { 75 15 } { 36 75 15 } { 36 15 } { 15 } { 15 59 } { 36 15 59 } { 36 75 15 59 } { 75 15 59 } { 75 59 } { 36 75 59 } { 36 59 } { 59 } Enter the number of elements in the set: 3 The elements in the set : 73 36 36 The permutations are: { } { 73 } { 73 36 } { 36 } { 36 36 } { 73 36 36 } { 73 36 } { 36 }
Related posts:
Giới thiệu Design Patterns
Java Program to Find the Shortest Path from Source Vertex to All Other Vertices in Linear Time
Java Program to Generate a Sequence of N Characters for a Given Specific Case
Tránh lỗi ConcurrentModificationException trong Java như thế nào?
Custom Cascading in Spring Data MongoDB
Spring MVC Content Negotiation
Java Program to Implement Knight’s Tour Problem
Giới thiệu Google Guice – Injection, Scope
Spring REST API with Protocol Buffers
Java Program to Implement Bloom Filter
Mệnh đề if-else trong java
Java Program to Generate Random Hexadecimal Byte
JWT – Token-based Authentication trong Jersey 2.x
So sánh Array và ArrayList trong Java
Java Program to Implement Affine Cipher
Java Program to add two large numbers using Linked List
More Jackson Annotations
Java Program to Find Inverse of a Matrix
Java Program to Check Whether Graph is DAG
Hướng dẫn Java Design Pattern – Mediator
Giới thiệu thư viện Apache Commons Chain
Converting Between a List and a Set in Java
How To Serialize and Deserialize Enums with Jackson
Working with Tree Model Nodes in Jackson
Java Program to Implement the Alexander Bogomolny’s UnOrdered Permutation Algorithm for Elements Fro...
Java Program to Construct an Expression Tree for an Prefix Expression
Extract links from an HTML page
How to Get All Spring-Managed Beans?
CyclicBarrier in Java
Iterating over Enum Values in Java
Java Program to Perform Addition Operation Using Bitwise Operators
Sending Emails with Java