Cách tạo kết hợp các giá trị trong Java?

Question

Tôi có bản đồ sau: Map<Integer,String[]> map = new HashMap<Integer,String[]>();

Khóa là số nguyên và giá trị là mảng (cũng có thể được thay thế bằng danh sách).

Bây giờ, tôi muốn có được tất cả các kết hợp có thể có của các giá trị trong số các khóa. Ví dụ, giả sử bản đồ chứa các mục sau:

key 1: "test1", "stackoverflow" 
key 2: "test2", "wow" 
key 3: "new" 

Các tổ hợp bao gồm

("test1","test2","new") 
("test1","wow","new") 
("stackoverflow", "test2", "new") 
("stackoverflow", "wow", "new") 

Đối với điều này tôi tưởng tượng một phương pháp boolean hasNext() mà trả về true nếu có một cặp tiếp theo và một phương pháp thứ hai mà chỉ trả về bộ giá trị tiếp theo (nếu có).

Làm cách nào để thực hiện điều này? Bản đồ cũng có thể được thay thế bằng một cấu trúc dữ liệu khác.

Answer 1

Thuật toán là về cơ bản gần như giống với thuật toán tăng cho số thập phân ("x -> x + 1").

Ở đây, lớp iterator:

import java.util.Iterator; 
import java.util.Map; 
import java.util.NoSuchElementException; 
import java.util.TreeSet; 

public class CombinationsIterator implements Iterator<String[]> { 

    // Immutable fields 
    private final int combinationLength; 
    private final String[][] values; 
    private final int[] maxIndexes; 

    // Mutable fields 
    private final int[] currentIndexes; 
    private boolean hasNext; 

    public CombinationsIterator(final Map<Integer,String[]> map) { 
     combinationLength = map.size(); 
     values = new String[combinationLength][]; 
     maxIndexes = new int[combinationLength]; 
     currentIndexes = new int[combinationLength]; 

     if (combinationLength == 0) { 
      hasNext = false; 
      return; 
     } 

     hasNext = true; 

     // Reorganize the map to array. 
     // Map is not actually needed and would unnecessarily complicate the algorithm. 
     int valuesIndex = 0; 
     for (final int key : new TreeSet<>(map.keySet())) { 
      values[valuesIndex++] = map.get(key); 
     } 

     // Fill in the arrays of max indexes and current indexes. 
     for (int i = 0; i < combinationLength; ++i) { 
      if (values[i].length == 0) { 
       // Set hasNext to false if at least one of the value-arrays is empty. 
       // Stop the loop as the behavior of the iterator is already defined in this case: 
       // the iterator will just return no combinations. 
       hasNext = false; 
       return; 
      } 

      maxIndexes[i] = values[i].length - 1; 
      currentIndexes[i] = 0; 
     } 
    } 

    @Override 
    public boolean hasNext() { 
     return hasNext; 
    } 

    @Override 
    public String[] next() { 
     if (!hasNext) { 
      throw new NoSuchElementException("No more combinations are available"); 
     } 
     final String[] combination = getCombinationByCurrentIndexes(); 
     nextIndexesCombination(); 
     return combination; 
    } 

    private String[] getCombinationByCurrentIndexes() { 
     final String[] combination = new String[combinationLength]; 
     for (int i = 0; i < combinationLength; ++i) { 
      combination[i] = values[i][currentIndexes[i]]; 
     } 
     return combination; 
    } 

    private void nextIndexesCombination() { 
     // A slightly modified "increment number by one" algorithm. 

     // This loop seems more natural, but it would return combinations in a different order than in your example: 
//  for (int i = 0; i < combinationLength; ++i) { 

     // This loop returns combinations in the order which matches your example: 
     for (int i = combinationLength - 1; i >= 0; --i) { 
      if (currentIndexes[i] < maxIndexes[i]) { 
       // Increment the current index 
       ++currentIndexes[i]; 
       return; 
      } else { 
       // Current index at max: 
       // reset it to zero and "carry" to the next index 
       currentIndexes[i] = 0; 
      } 
     } 
     // If we are here, then all current indexes are at max, and there are no more combinations 
     hasNext = false; 
    } 

    @Override 
    public void remove() { 
     throw new UnsupportedOperationException("Remove operation is not supported"); 
    } 

} 

đây việc sử dụng mẫu:

final Map<Integer,String[]> map = new HashMap<Integer,String[]>(); 
map.put(1, new String[]{"test1", "stackoverflow"}); 
map.put(2, new String[]{"test2", "wow"}); 
map.put(3, new String[]{"new"}); 

final CombinationsIterator iterator = new CombinationsIterator(map); 
while (iterator.hasNext()) { 
    System.out.println(
     org.apache.commons.lang3.ArrayUtils.toString(iterator.next()) 
    ); 
} 

It in chính xác những gì được chỉ định trong ví dụ của bạn.

---

P.S. Bản đồ thực sự là không cần thiết; nó có thể được thay thế bằng một mảng đơn giản của mảng (hoặc danh sách các danh sách). Hàm khởi tạo sau đó sẽ trở nên đơn giản hơn một chút:

public CombinationsIterator(final String[][] array) { 
    combinationLength = array.length; 
    values = array; 

    // ... 

    // Reorganize the map to array - THIS CAN BE REMOVED. 

Answer 2

Tôi coi đây là một thách thức để xem liệu các API Java 8 mới có hỗ trợ các loại vấn đề này hay không. Vì vậy, đây là giải pháp của tôi cho vấn đề:

public class CombinatorIterator implements Iterator<Collection<String>> { 
    private final String[][] arrays; 
    private final int[] indices; 
    private final int total; 
    private int counter; 

    public CombinatorIterator(Collection<String[]> input) { 
     arrays = input.toArray(new String[input.size()][]); 
     indices = new int[arrays.length]; 
     total = Arrays.stream(arrays).mapToInt(arr -> arr.length) 
       .reduce((x, y) -> x * y).orElse(0); 
     counter = 0; 
    } 

    @Override 
    public boolean hasNext() { 
     return counter < total; 
    } 

    @Override 
    public Collection<String> next() { 
     List<String> nextValue = IntStream.range(0, arrays.length) 
       .mapToObj(i -> arrays[i][indices[i]]).collect(Collectors.toList()); 

     //rolling carry over the indices 
     for (int j = 0; 
       j < arrays.length && ++indices[j] == arrays[j].length; j++) { 
      indices[j] = 0; 
     } 

     counter++; 
     return nextValue; 
    } 
} 

Lưu ý rằng tôi không sử dụng bản đồ làm đầu vào vì khóa bản đồ thực sự không đóng bất kỳ vai trò nào ở đây. Bạn có thể sử dụng map.values() mặc dù truyền vào đầu vào cho trình lặp. Với mã kiểm tra sau:

List<String[]> input = Arrays.asList(
    new String[] {"such", "nice", "question"}, 
    new String[] {"much", "iterator"}, 
    new String[] {"very", "wow"} 
); 
Iterator<Collection<String>> it = new CombinatorIterator(input); 
it.forEachRemaining(System.out::println); 

đầu ra sẽ là:

[such, much, very] 
[nice, much, very] 
[question, much, very] 
[such, iterator, very] 
[nice, iterator, very] 
[question, iterator, very] 
[such, much, wow] 
[nice, much, wow] 
[question, much, wow] 
[such, iterator, wow] 
[nice, iterator, wow] 
[question, iterator, wow]