Kombinatoryki: generuj wszystkie "stany" - kombinacje tablic

Question

Mam tablicę liczb całkowitych: n[].

Mam również tablicę (Nr[]) zawierającą liczby całkowite n.length. Muszę wygenerować wszystkie kombinacje n[] w następujący sposób:

/* 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 

Celem jest znalezienie wszystkich kombinacji n, gdzie n[i] może być 0 to Nr[i].

Nie udało mi się ... Jak rozwiązać problem w Javie? Lub nie w Java ...

Answer 1

Może chcesz użyć recursion, wypróbować wszystkie możliwości dla każdego indeksu i rekursywnie wywołać z subarray, „bez” ostatniego elementu.

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 
    } 
} 

powołać się:

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); 
} 

będzie Ci:

[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] 

Uwaga jednak - że za pomocą tej metody można wydrukować wszystkie elementy, jak opisuje, ale w innej kolejności, wówczas przykład.

Answer 2

Uwaga: W przeciwieństwie do logiki pytań, poniższy kod jest górny wyłączny, podobnie jak standard w Javie, np. wejście 3 będzie liczyć od 0 do 2 (włącznie), a nie od 0 do 3.

Można to zrobić bez rekursji tak:

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)); 
    } 
} 

test

printPermutations(2, 3, 3); 

Wyjście

[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] 

---

Jako ćwiczenie w Javie 8 strumieni, tutaj jest klasa do iteracji lub przesyłania strumieniowego permutacji.

Jak używać:

// 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)); 

Wszystkie trzy produkować taki sam efekt jak wyżej.

Oto kod:

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); 
    } 

}