Kết hợp: tạo tất cả "trạng thái" - kết hợp mảng

Question

Tôi có một dãy số nguyên: n[].

Ngoài ra, tôi có một mảng (Nr[]) chứa n.length số nguyên. Tôi cần phải tạo ra tất cả các kết hợp của n[] trong một cách sau:

/* let n.length == 3 and Nr[0] = 2, Nr[1] = 3, Nr[2] = 3 */ 
n = {0, 0, 0}; 
n = {1, 0, 0}; 
n = {2, 0, 0}; 
n = {0, 1, 0}; 
n = {0, 2, 0}; 
n = {0, 3, 0}; 
n = {0, 0, 1}; 
... 
n = {1, 1, 0}; 
n = {1, 2, 0}; 
n = {1, 3, 0}; 
n = {2, 1, 0}; 
n = {2, 2, 0}; 
n = {2, 3, 0}; 
n = {1, 1, 1}; 
... 
n = {0, 1, 1}; 
// many others 

Mục đích là để tìm tất cả các kết hợp của n, nơi n[i] có thể 0 to Nr[i].

Tôi không thành công ... Cách giải quyết trong Java? Hoặc không có trong Java ...

Answer 1

Bạn có thể muốn sử dụng recursion, thử tất cả các khả năng cho từng chỉ mục và đệ quy gọi với subarray, "không có" phần tử cuối cùng.

public static void printPermutations(int[] n, int[] Nr, int idx) { 
    if (idx == n.length) { //stop condition for the recursion [base clause] 
     System.out.println(Arrays.toString(n)); 
     return; 
    } 
    for (int i = 0; i <= Nr[idx]; i++) { 
     n[idx] = i; 
     printPermutations(n, Nr, idx+1); //recursive invokation, for next elements 
    } 
} 

gọi với:

public static void main(String[] args) { 
    /* let n.length == 3 and Nr[0] = 2, Nr[1] = 3, Nr[2] = 3 */ 
    int[] n = new int[3]; 
    int Nr[] = {2,3,3 }; 
    printPermutations(n, Nr, 0); 
} 

sẽ giúp bạn:

[0, 0, 0] 
[0, 0, 1] 
[0, 0, 2] 
[0, 0, 3] 
[0, 1, 0] 
[0, 1, 1] 
[0, 1, 2] 
[0, 1, 3] 
[0, 2, 0] 
[0, 2, 1] 
[0, 2, 2] 
[0, 2, 3] 
[0, 3, 0] 
[0, 3, 1] 
[0, 3, 2] 
[0, 3, 3] 
[1, 0, 0] 
[1, 0, 1] 
[1, 0, 2] 
[1, 0, 3] 
[1, 1, 0] 
[1, 1, 1] 
[1, 1, 2] 
[1, 1, 3] 
[1, 2, 0] 
[1, 2, 1] 
[1, 2, 2] 
[1, 2, 3] 
[1, 3, 0] 
[1, 3, 1] 
[1, 3, 2] 
[1, 3, 3] 
[2, 0, 0] 
[2, 0, 1] 
[2, 0, 2] 
[2, 0, 3] 
[2, 1, 0] 
[2, 1, 1] 
[2, 1, 2] 
[2, 1, 3] 
[2, 2, 0] 
[2, 2, 1] 
[2, 2, 2] 
[2, 2, 3] 
[2, 3, 0] 
[2, 3, 1] 
[2, 3, 2] 
[2, 3, 3] 

Lưu ý tuy nhiên - rằng việc sử dụng phương pháp này không in tất cả các yếu tố như bạn mô tả, nhưng theo một thứ tự khác nhau sau đó của bạn thí dụ.

Answer 2

Lưu ý: Không giống như logic câu hỏi, mã sau không độc quyền, như là tiêu chuẩn trong Java, ví dụ: đầu vào của 3 sẽ đếm 0-2 (bao gồm), chứ không phải từ 0 đến 3.

này có thể được thực hiện mà không đệ quy như thế này:

public static void printPermutations(int... size) { 
    int total = 1; 
    for (int i : size) 
     total *= i; 
    int[] n = new int[size.length]; 
    for (int value = 0; value < total; value++) { 
     int remain = value; 
     for (int i = size.length - 1; i >= 0; i--) { 
      n[i] = remain % size[i]; 
      remain /= size[i]; 
     } 
     System.out.println(Arrays.toString(n)); 
    } 
} 

thử nghiệm

printPermutations(2, 3, 3); 

Đầu ra

[0, 0, 0] 
[0, 0, 1] 
[0, 0, 2] 
[0, 1, 0] 
[0, 1, 1] 
[0, 1, 2] 
[0, 2, 0] 
[0, 2, 1] 
[0, 2, 2] 
[1, 0, 0] 
[1, 0, 1] 
[1, 0, 2] 
[1, 1, 0] 
[1, 1, 1] 
[1, 1, 2] 
[1, 2, 0] 
[1, 2, 1] 
[1, 2, 2] 

---

Là một bài tập trong luồng Java 8, đây là một lớp để lặp hoặc phát trực tuyến hoán vị.

Làm thế nào để sử dụng:

// Using Iterator 
for (int[] n : Permutations.iterable(2, 3, 3)) 
    System.out.println(Arrays.toString(n)); 

// Using streams 
Permutations.stream(2, 3, 3) 
      .parallel() 
      .map(Arrays::toString) // this will be done in parallel 
      .forEachOrdered(System.out::println); 

// Getting all 
int[][] results = Permutations.get(2, 3, 3); 
for (int[] n : results) 
    System.out.println(Arrays.toString(n)); 

Cả ba sản xuất đầu ra tương tự như trên.

Đây là mã:

class Permutations implements Spliterator<int[]>, Iterator<int[]> { 

    public static Stream<int[]> stream(int... sizes) { 
     return StreamSupport.stream(spliterator(sizes), false); 
    } 

    public static Spliterator<int[]> spliterator(int... sizes) { 
     long total = sum(sizes); 
     return (total == 0 ? Spliterators.emptySpliterator() : new Permutations(sizes.clone(), 0, total)); 
    } 

    public static Iterable<int[]> iterable(int... sizes) { 
     long total = sum(sizes); 
     if (total == 0) 
      return Collections.emptyList(); 
     int[] clonedSizes = sizes.clone(); 
     return new Iterable<int[]>() { 
      @Override public Iterator<int[]> iterator() { return new Permutations(clonedSizes, 0, total); } 
      @Override public Spliterator<int[]> spliterator() { return new Permutations(clonedSizes, 0, total); } 
     }; 
    } 

    public static int[][] get(int... sizes) { 
     long total = sum(sizes); 
     if (total == 0) 
      return new int[0][]; 
     if (total > Integer.MAX_VALUE) 
      throw new IllegalArgumentException("Invalid sizes (overflow): " + Arrays.toString(sizes)); 
     Permutations generator = new Permutations(sizes.clone(), 0, total); 
     int[][] result = new int[(int) total][]; 
     for (int i = 0; i < result.length; i++) 
      result[i] = generator.next(); 
     return result; 
    } 

    private static long sum(int[] sizes) { 
     long total = 1; 
     for (int size : sizes) { 
      if (size < 0) 
       throw new IllegalArgumentException("Invalid size: " + size); 
      try { 
       total = Math.multiplyExact(total, size); // Java 8+: Fail on overflow 
      } catch (@SuppressWarnings("unused") ArithmeticException e) { 
       throw new IllegalArgumentException("Invalid sizes (overflow): " + Arrays.toString(sizes)); 
      } 
     } 
     return total; 
    } 

    private final int[] sizes; 
    private final long end; 
    private long  next; 

    Permutations(int[] sizes, long start, long end) { 
     this.sizes = sizes; 
     this.end = end; 
     this.next = start; 
    } 

    @Override 
    public boolean hasNext() { 
     return (this.next < this.end); 
    } 

    @Override 
    public int[] next() { 
     if (this.next == this.end) 
      throw new NoSuchElementException(); 
     long value = this.next++; 
     int[] arr = new int[this.sizes.length]; 
     for (int i = arr.length - 1; i >= 0; i--) { 
      arr[i] = (int) (value % this.sizes[i]); 
      value /= this.sizes[i]; 
     } 
     return arr; 
    } 

    @Override 
    public int characteristics() { 
     // Note: Can easily be made SORTED by implementing a Comparator<int[]> 
     return ORDERED | DISTINCT | NONNULL | IMMUTABLE | SIZED | SUBSIZED; // not SORTED or CONCURRENT 
    } 

    @Override 
    public long estimateSize() { 
     return this.end - this.next; 
    } 

    @Override 
    public boolean tryAdvance(Consumer<? super int[]> action) { 
     if (this.next == this.end) 
      return false; 
     action.accept(next()); 
     return true; 
    } 

    @Override 
    public Spliterator<int[]> trySplit() { 
     if (this.next > this.end - 2) 
      return null; 
     long split = (this.end - this.next)/2 + this.next; 
     Permutations prefix = new Permutations(this.sizes, this.next, split); 
     this.next = split; 
     return prefix; 
    } 

    @Override 
    public void forEachRemaining(Consumer<? super int[]> action) { 
     Spliterator.super.forEachRemaining(action); 
    } 

}