Tạo tất cả các từ có thể có của Chiều dài n

Question

Given:

• Một số nhân vật trong input String.
• Một số nguyên N

Làm thế nào tôi có thể tạo ra tất cả những từ có thể có chiều dài chính xác của N?

Nếu tôi có input = {"a", "b", "a"} và N=2, sau đó sản lượng nên là: ab,aa,ba (không có bản sao)

---

Tôi đã tìm kiếm cho điều này, và tất cả tôi nhận được một số thuật toán mà tôi không thể hiểu đúng hơn là triển khai thực hiện. Tôi hiểu rằng tôi cần phải thực hiện một phương pháp đệ quy, nhưng tôi bị kẹt ở điểm sau khi điều kiện dừng.

public void generate(String input, int length) {   
    if(length == 0) { 
     System.out.println(input); 
     return; 
    } 
    //Not sure about this part 
    String[] a = input.split(""); 
    for(int i =0; i<a.length; i++) { 
     loop(input+a[i], length-1); 
    } 
} 

Answer 1

Điều này cần thực hiện thủ thuật và làm việc với bất kỳ input và N. Hành vi không được xác định rõ cho N = 0 hoặc N > input.length()

public static void generate(String input, int N) { 
    generate("", input, new HashSet<String>(), N); 
} 

private static void generate(String str, String input, Set<String> dup, int N) { 
    if (str.length() == N && dup.add(str)) 
     System.out.println(str); 
    else 
     //remove a char form input and add it to str 
     for (int i = 0; i < input.length(); i++) 
      generate(
       str + input.charAt(i), 
       input.substring(0, i) + input.substring(i + 1), 
       dup, N); 
} 

này đã được chuyển thể từ tổng quát hơn "tính toán tất cả hoán vị" vấn đề. Trong vấn đề chung không có kiểm tra trùng lặp và str được in khi input.isEmpty(). Hãy cho tôi biết nếu bạn cần bất kỳ làm rõ.

Answer 2

này hoạt động tốt cũng cho chuỗi rỗng hoặc n == 0.

Các heavylifting là trong lần thứ hai quá tải combination() phương pháp (một trong đó có bốn thông số). Quá tải đầu tiên chỉ đơn giản dịch chuỗi đầu vào thành List<Character> và chuẩn bị một bộ băm trống trong đó kết quả được lưu trữ:

Set<String> combination(String input, int n) { 
    List<Character> letters = new ArrayList<Character>(); 
    for (int i = 0; i < input.length(); ++i) 
    letters.add(input.charAt(i)); 
    Set<String> results = new HashSet<String>(); 
    combination("", letters, n, results); 
    return results; 
} 

void combination(String soFar, List<Character> letters, int n, 
    Set<String> results) { 
    if (n == 0) { 
    results.add(soFar); 
    return; 
    } 

    int startIndex = soFar.length(); 
    if (startIndex >= letters.size()) 
    return;  

    for (int i = startIndex; i < letters.size(); ++i) { 
    // ch is the next candidate to add to the result that we're 
    // building (soFar) 
    char ch = letters.get(i); 
    // Swap the characters at positions i and position startIndex. 
    char temp = letters.get(startIndex); 
    letters.set(i, temp); 
    letters.set(startIndex, ch); 

    // add ch to soFar, compute combinations of length n-1. 
    // as startIndex is essentially soFar.length() this means that 
    // the recursive call will only process the remainder of the list. 
    combination(soFar + ch, letters, n - 1, result); 

    // Swap the characters back - restore the original state. 
    letters.set(i, ch); 
    letters.set(startIndex, temp); 
    }