मेरे पास एक सरणी है जिसमें 3 फ़ाइलों में कुल पंक्तियाँ हैं। उदाहरण: [3,4,5]। मैं संख्याओं के एक क्रम का उत्पादन करना चाहूंगा, जो उस सरणी को शून्य तरीके से एक व्यवस्थित तरीके से शून्य कर दे, जिससे मुझे तीन फाइलों में लाइनों का हर संयोजन मिल जाए। यह उदाहरण 3 फ़ाइलों / लंबाई -3 सरणी का उपयोग करता है, लेकिन एल्गोरिथ्म किसी भी मनमानी लंबाई के साथ एक सरणी काम करने में सक्षम होना चाहिए।

ऊपर के उदाहरण के लिए, समाधान जैसा दिखेगा:

[3,4,5]  (line 3 from file 1, line 4 from file 2, line 5 from file 3)  
[3,4,4]  
[3,4,3]  
[3,4,2]  
[3,4,1]  
[3,4,0]  
[3,3,5]  
[3,3,4]  
[3,3,3]  
[3,3,2]  

और इसी तरह...

इस पुनरावर्ती के लिए एल्गोरिथ्म का निर्माण करने का मेरा पहला प्रयास सरणी में एक स्थिति को घटाता है, और जब वह स्थिति शून्य तक पहुंच जाती है - इससे पहले की स्थिति को घटाता है। हालाँकि मैं पिछले दो पदों की तुलना में कम होने वाली गिरावट को दूर रखने में सक्षम नहीं हूँ।

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

    public class FilePositionGenerator {

        public static void main(String[] args) {
            int[] starterArray = {2, 2, 2};
            int[] counters = starterArray.clone();
            List<Integer> results = new ArrayList<Integer>();

            FilePositionGenerator f = new FilePositionGenerator();
            f.generateFilePositions(starterArray, counters, (starterArray.length - 1), results);
        }//end main

        void generateFilePositions(int[] originalArray, int[] modifiedArray, int counterPosition, List<Integer> results) {

            if (modifiedArray[counterPosition] == 0 && counterPosition > 0) {
                modifiedArray[counterPosition] = originalArray[counterPosition];
                counterPosition = counterPosition - 1;
            } else {
                modifiedArray[counterPosition] = modifiedArray[counterPosition] - 1;
                System.out.println(Arrays.toString(modifiedArray));
                generateFilePositions(originalArray, modifiedArray, counterPosition, results);
            }
        }
    }  

मुझे लगता है कि एक चर लंबाई सरणी से निपटने के लिए, एल्गोरिथ्म पुनरावर्ती होना चाहिए, लेकिन मुझे इसके माध्यम से सोचने में परेशानी हो रही है। इसलिए मैंने एक अलग दृष्टिकोण आजमाने का फैसला किया।

एल्गोरिथ्म का उत्पादन करने का मेरा दूसरा प्रयास एक दोहरी सूचक विधि का उपयोग करता है जो वर्तमान उलटी गिनती की स्थिति [सबसे सही स्थिति] पर एक संकेतक रखता है, और अगले गैर-सही स्थिति (पॉइंटरपॉइंट) के लिए एक संकेतक जो कि सबसे सही स्थिति शून्य तक पहुंचने पर कम हो जाएगा। । इस तरह:

import java.util.Arrays;

class DualPointer {
    public static void main(String[] args) {
        int[] counters = {2, 2, 2}; // initialize the problem set
        int[] original = {2, 2, 2}; // clone a copy to reset the problem array
        int[] stopConditionArray = {0, 0, 0};   // initialize an object to show what the stopCondition should be
        int pivotLocation = counters.length - 1;    // pointer that starts at the right, and moves left
        int counterLocation = counters.length - 1;  // pointer that always points to the rightmost position
        boolean stopCondition = false;

        System.out.println(Arrays.toString(counters));
        while (stopCondition == false) {

            if (pivotLocation >= 0 && counterLocation >= 0 && counters[counterLocation] > 0) {
                // decrement the rightmost position
                counters[counterLocation] = counters[counterLocation] - 1;
                System.out.println(Arrays.toString(counters));
            } else if (pivotLocation >= 0 && counters[counterLocation] <= 0) {
                // the rightmost position has reached zero, so check the pivotPointer
                // and decrement if necessary, or move pointer to the left
                if (counters[pivotLocation] == 0) {
                    counters[pivotLocation] = original[pivotLocation];
                    pivotLocation--;
                }
                counters[pivotLocation] = counters[pivotLocation] - 1;
                counters[counterLocation] = original[counterLocation]; // reset the rightmost position
                System.out.println(Arrays.toString(counters));
            } else if (Arrays.equals(counters, stopConditionArray)) {
                // check if we have reached the solution
                stopCondition = true;
            } else {
                // emergency breakout of infinite loop
                stopCondition = true;
            }

        }
    }
}

दौड़ने पर, आप 2 स्पष्ट समस्याएं देख सकते हैं:

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

नंबर एक, pivotPointer ठीक से नहीं बढ़ता है जब pivotPointer और currentCountdown एक से अधिक सरणी सेल से अलग हो। दूसरे, लाइन counters[pivotLocation] = counters[pivotLocation] - 1; पर एक arrayIndexOutOfBounds है कि अगर तय है, एल्गोरिथ्म को पूरी तरह से ठीक से चलाने से तोड़ता है।

किसी भी सहायता की सराहना की जाएगी।

2
mitchellmc 29 नवम्बर 2015, 16:45

2 जवाब

सबसे बढ़िया उत्तर

मैं एक अलग दृष्टिकोण सुझाता हूँ।

पुनरावर्तन में विचार प्रत्येक पुनरावर्ती कॉल में समस्या के आकार को कम करना है, जब तक कि आप एक तुच्छ मामले तक नहीं पहुंचते हैं, जिसमें आपको एक और पुनरावर्ती कॉल करने की आवश्यकता नहीं है।

जब आप पहली बार n तत्वों की एक सरणी के लिए पुनरावर्ती विधि कहते हैं, तो आप अंतिम सूचकांक (n-1) के मूल्यों की सीमा पर एक लूप में पुनरावृति कर सकते हैं, पहले के सरणी के लिए सभी संयोजनों को उत्पन्न करने के लिए पुनरावर्ती कॉल करें एन -1 तत्व, और आउटपुट को जोड़ती है।

यहाँ कुछ आंशिक जावा / आंशिक छद्म कोड हैं:

पहली कॉल:

List<int[]> output = generateCombinations(inputArray,inputArray.length);

पुनरावर्ती विधि List<int[]> generateCombinations(int[] array, int length):

List<int[]> output = new ArrayList<int[]>();
if length == 0 
    // the end of the recursion
    for (int i = array[length]; i>=0; i--)
        output.add (i)
else
    // the recursive step
    List<int[]> partialOutput = generateCombinations(array, length - 1)
    for (int i = array[length]; i>=0; i--)
        for (int[] arr : partialOutput)
            output.add(arr + i)
return output

पुनरावर्ती विधि List<int[]> लौटाती है। इसका मतलब है कि "output.add (i)" में आपको एक एकल तत्व के साथ एक इंट सरणी बनाना चाहिए और इसे सूची में जोड़ना चाहिए, जबकि output.add(arr + i) में आप एक सरणी बना लेंगे। arrength + 1 तत्व; और इसके बाद मेरे द्वारा गिरफ्तार किए गए तत्वों को कॉपी करें।

0
Eran 29 नवम्बर 2015, 14:18

पुनरावृत्ति के बारे में मजेदार बात यह है कि आप इसे वही कर सकते हैं जो आप इसे चाहते हैं। इस स्थिति में, आपके सरणी की संख्या के i सूचकांक में प्रत्येक संख्या के लिए, हम इसे प्रत्येक संख्या के साथ सूचकांक i + 1 तक जोड़ना चाहते हैं, जब तक कि हम सरणी के अंत तक नहीं पहुंच जाते। आपके द्वारा सभी विकल्पों के माध्यम से चलाने के बाद यह ट्रिक इंडेक्स i पर वापस नहीं आती है।

जावास्क्रिप्ट कोड:

var arr = [3,4,5];
var n = arr.length;

function f(cs,i){
  // base case
  if (i == n){
    console.log(cs.join(','));
    return;
  }

  // otherwise
  while (cs[i] >= 0){
    // copy counts
    _cs = cs.slice();

    // recurse
    f(_cs,i + 1);

    // change number at index i
    cs[i]--;
  }
}

f(arr,0);
0
גלעד ברקן 30 नवम्बर 2015, 03:12