Thuật toán để tìm sự kết hợp đơn giản nhất của các số nguyên chưa được sử dụng

Question

Tôi đang tìm một thuật toán để tìm sự kết hợp đơn giản nhất của các số nguyên từ 0 đến 5 (đó là số có số lượng số nguyên ít nhất) chưa được sử dụng (các kết hợp được sử dụng nằm trong danh sách).

Đơn đặt hàng không quan trọng và các kết hợp phải được trả về trong danh sách.

Ví dụ, danh sách với con số sử dụng có thể nhìn như thế này:

{{0}, {1}, {2}, {3}, {4}, {0,0}, {0,1}, {0,2}, ..., {2,1}, {2,2}, ..., {1,5,4}, ...}

Trong này trường hợp, thuật toán sẽ trả về một danh sách với {5}, vì {5} là kết hợp bao gồm các số nguyên ít nhất.

Nếu danh sách có vẻ như thế này:

{{0}, {1}, {2}, {3}, {4}, {5}, {0,0}, {0,1 }, {0,2}, {0,3}, {0,5}, ...}

thuật toán sẽ trả về danh sách có 0 và 4 ({0,4}).

Vì nó được sử dụng trong Java, một câu trả lời Java là thích hợp hơn nhưng mã giả hoặc các ngôn ngữ lập trình khác cũng có thể sử dụng được.

Cảm ơn bạn trước!

Answer 1

Tôi đoán ví dụ 2 sai: cho {{0}, {1}, {2}, {3}, {4}, {5}, {0,1}, {0,2}, {0,3}, {0,5}, ...} giải pháp nhỏ nhất là {0,0}, không {0,4}

giải pháp hoàn thiện là ở đây:

import java.util.*; 

public class Algorithm { 

    static List<List<Integer>> getChildren(List<Integer> node){ 
     List<List<Integer>> children = new ArrayList<List<Integer>>(); 
     for(int i = 0; i < 6; i++){ 
      List<Integer> child = new ArrayList<Integer>(node); 
      child.add(i); 
      children.add(child); 
     } 
     return children; 
    } 

    static List<Integer> find(Queue<List<Integer>> queue, Set<List<Integer>> set){ 

     for(;;){ 
      List<Integer> head = queue.poll(); 
      if(!set.contains(head)){ 
       return head; 
      } else { 
       for(List<Integer> child : getChildren(head)){ 
        queue.add(child); 
       } 
      } 
     } 
    } 

    public static void main(String[] arg) { 
     Queue<List<Integer>> queue = new LinkedList<List<Integer>>(); 
     for(int i = 0; i < 6; i++){ 
      queue.add(Collections.singletonList(i)); 
     } 
     // Example {{0},{1},{2},{3},{4},{5},{0,1},{0,2},{0,3},{0,5},...} 
     Set<List<Integer>> task = new HashSet<List<Integer>>(); 
     task.add(Arrays.asList(0)); 
     task.add(Arrays.asList(1)); 
     task.add(Arrays.asList(2)); 
     task.add(Arrays.asList(3)); 
     task.add(Arrays.asList(4)); 
     task.add(Arrays.asList(5)); 
     task.add(Arrays.asList(0, 1)); 
     task.add(Arrays.asList(0, 2)); 
     task.add(Arrays.asList(0, 3)); 
     task.add(Arrays.asList(0, 5)); 

     System.out.println(find(queue, task)); 
    } 

} 

Answer 2

Chỉ cần thử từng kết hợp theo thứ tự, bắt đầu bằng ngắn nhất và dừng lại khi bạn chưa sử dụng kết hợp? Bạn đã thử điều đó, nó có vẻ rất rõ ràng thực sự?

Answer 3

Đối với vấn đề đó, tôi sẽ tạo ra một đối tượng cụ thể để lưu trữ một phần tử (số duy nhất hoặc tuple của numer):

class Tuple { 
    String key; 
    Set<Integer> tuple; 
} 

Mấu chốt sẽ là contatenation của các con số, ra lệnh. Trong ví dụ của bạn, các phím sẽ là "0" "1" "2" "3" "4" "5" "01" "02" "03" "05".

Bạn có thể sử dụng Bản đồ để lưu trữ bộ dữ liệu, với khóa - giá trị liên kết.

Vì các khóa tôn trọng thứ tự logic, việc tìm kiếm bộ túp tự do tiếp theo thật dễ dàng. Bạn chỉ cần bắt đầu từ "0" và tăng khóa (sử dụng thứ tự đã xác định), kiểm tra trong Bản đồ để xác minh xem tuple đã được sử dụng hay chưa.

Trong ví dụ này, tuple miễn phí đầu tiên có khóa "04". Từ khóa này, việc tạo Tuple liên quan rất dễ dàng.

Answer 4

Một đầy đủ (ngây thơ) giải pháp:

import java.util.*; 

public class Test { 

    public static String increment(String str) { 
     if (str.isEmpty()) return "0"; 
     int i = str.length() - 1; 
     if (str.charAt(i) < '5') 
      return str.substring(0, i) + (char) (str.charAt(i) + 1); 
     return increment(str.substring(0, i)) + "0"; 
    } 


    public static String nextUnused(Set<String> used) { 
     String s = "0"; 
     while (used.contains(s)) 
      s = increment(s); 
     return s; 
    } 

    public static void main(String args[]) { 
     Set<String> used = new HashSet<String>(Arrays.asList("0", "1", "2", "3", 
       "4", "00", "01", "02", "21", "22", "154")); 
     for (int i = 0; i < 10; i++) { 
      String toUse = nextUnused(used); 
      System.out.println("Adding " + toUse); 
      used.add(toUse); 
     } 
    } 
} 

Output:

Adding 5 
Adding 03 
Adding 04 
Adding 05 
Adding 10 
Adding 11 
Adding 12 
Adding 13 
Adding 14 
Adding 15 

Bạn có thể có thể tăng tốc độ nó lên khá một chút bằng cách áp dụng memoization đến increment-method.

Answer 5

Nếu danh sách bạn đã đặt hàng, có 2 phương pháp mà tôi có thể nghĩ về điều đó sẽ tốt hơn tìm kiếm tuyến tính.

Giả sử rằng bạn sẽ không hoàn toàn lấp đầy không gian kết hợp, bạn có thể sử dụng biến thể tìm kiếm nhị phân.

Trước tiên, hãy gọi từng bộ kích thước 'x' một nhóm. Vì vậy, 0,1,2,3,4,5 là nhóm 1, {0,0} đến {5,5} là nhóm 2.

Bắt đầu với nhóm 1, kiểm tra vị trí danh sách chứa giá trị cuối cùng trong nhóm nếu họ ở đó. Ví dụ: List[5] == 5. Nếu có, chuyển sang nhóm 2 và lặp lại. Nếu không, hãy tiến hành tìm kiếm nhị phân bên trong nhóm đó luôn ưu tiên phía dưới, cuối cùng bạn sẽ tìm thấy giá trị bị thiếu đầu tiên.

---

Nếu không, nếu bạn mong đợi để sử dụng toàn bộ không gian kết hợp cuối cùng, chỉ cần thực hiện tìm kiếm nhị phân trên toàn bộ không gian kết hợp, kiểm tra nếu giá trị ở vị trí phù hợp với giá trị kỳ vọng nếu các giá trị trước tất cả các tồn tại.