कॉम्बिनेटोरिक्स: सभी "राज्य" उत्पन्न करें - सरणी संयोजन

Question

मेरे पास पूर्णांक की एक सरणी है: n[]।

इसके अलावा, मेरे पास एक सरणी है (Nr[]) में n.length पूर्णांक हैं। मैं एक के बाद रास्ते में n[] के सभी संयोजनों उत्पन्न करने के लिए की जरूरत है:

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

लक्ष्य n, जहां n[i]0 to Nr[i] हो सकता है के सभी संयोजनों मिल रहा है।

मैं सफल नहीं हुआ ... जावा में इसे कैसे हल करें? या नहीं जावा में ...

Answer 1

आप recursion का उपयोग प्रत्येक सूचकांक के लिए सभी संभावनाओं की कोशिश, और रिकर्सिवली subarray, पिछले तत्व "के बिना" के साथ आह्वान करने के लिए चाहते हो सकता है।

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

आह्वान के साथ:

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

आप मिल जाएगा:

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

नोट तथापि - कि इस पद्धति का उपयोग के रूप में आप का वर्णन प्रिंट सभी तत्वों करता है, लेकिन उसके बाद एक अलग क्रम में अपने उदाहरण।

Answer 2

नोट: प्रश्न तर्क के विपरीत, निम्नलिखित कोड जावा में मानक के रूप में ऊपरी-विशिष्ट है, उदा। 3 के इनपुट 0 से करने के लिए 2 (सम्मिलित), नहीं 0

3. करने के लिए यह इस तरह प्रत्यावर्तन बिना किया जा सकता माना जाएगा:

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

टेस्ट

printPermutations(2, 3, 3); 

आउटपुट

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

---

जावा 8 स्ट्रीम में एक अभ्यास के रूप में, क्रमपरिवर्तन को फिर से चलाने या स्ट्रीम करने के लिए एक कक्षा है।

उपयोग कैसे करें:

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

तीनों उपर दिए गए उत्पादन का उत्पादन।

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

}