In tất cả hoán vị của một chuỗi bằng ArrayList trong Java

Trong bài toán này, chúng ta được cung cấp một chuỗi có kích thước n và chúng ta phải in ra tất cả các hoán vị của chuỗi. Nhưng lần này chúng ta phải in hoán vị này bằng ArrayList.

Hãy lấy một ví dụ để hiểu vấn đề -

Đầu vào - string =‘XYZ’

Đầu ra - XYZ, XZY, YXZ, YZX, ZXY, ZYX

Để giải quyết vấn đề này, chúng ta sẽ tạo ra tất cả các hoán vị của ký tự trong chuỗi. Chúng tôi sẽ sử dụng một hàm đệ quy và sẽ trả về arrayList.

Ví dụ

Sau đây là triển khai ArrayList của thuật toán -

import java.util.ArrayList;
public class Main{
   static void printArrayList(ArrayList<String> combo) {
      combo.remove("");
      for (int i = 0; i < combo.size(); i++)
      System.out.print(combo.get(i)+"\t");
   }
   public static ArrayList<String> generatePermutation(String str) {
      if (str.length() == 0) {
         ArrayList<String> empty = new ArrayList<>();
         empty.add("");
         return empty;
      }
      char ch = str.charAt(0);
      String subStr = str.substring(1);
      ArrayList<String> lastCombination = generatePermutation(subStr);
      ArrayList<String> newCombination = new ArrayList<>();
      for (String val : lastCombination) {
      for (int i = 0; i <= val.length(); i++) {
            newCombination.add(val.substring(0, i) + ch + val.substring(i));
         }
       }
      return newCombination;
    }
   public static void main(String[] args) {
      String str = "NOPQ";
      System.out.println("Permutations of string are :");
      printArrayList(generatePermutation(str));
   }
}

Đầu ra

Permutations of string are :
NOPQ ONPQ OPNQ OPQN NPOQ PNOQ
PONQ POQN NPQO PNQO PQNO
PQON NOQP ONQP OQNP OQPN
NQOP QNOP QONP QOPN NQPO
QNPO QPNO QPON