"अर्ध-बराबर" में एक सरणी को उप-विभाजित करने के लिए एल्गोरिदम, वर्दी उप-सरणी

Question

एन तत्वों के साथ एक सरणी को देखते हुए, मैं एम (एम < एन) के बराबर लंबाई के साथ क्रमशः उप-सरणी या लंबाई से अधिक लंबाई के साथ देख रहा हूं 1. उदाहरण के लिए, यदि एन = 12 और एम = 4, तो सभी उप-सरणी में एन/एम = 3 की बराबर लंबाई होगी। यदि एन = 100 और एम = 12, तो मैं लंबाई 8 और 9 के साथ उप-सरणी की अपेक्षा करता हूं, और दोनों आकार समान रूप से मूल सरणी के भीतर फैल जाना चाहिए। यह सरल कार्य लागू करने के लिए थोड़ा सा सूक्ष्म हो गया।

/// The function suggests how an array with num_data-items can be 
/// subdivided into successively arranged groups (intervals) with 
/// equal or "similar" length. The number of intervals is specified 
/// by the parameter num_intervals. The result is stored into an array 
/// with (num_data + 1) items, each of which indicates the start-index of 
/// an interval, the last additional index being a sentinel item which 
/// contains the value num_data. 
/// 
/// Example: 
/// 
/// Input: num_data ........... 14, 
///   num_intervals ...... 4 
/// 
/// Result: result_start_idx ... [ 0, 3, 7, 10, 14 ] 
/// 

void create_uniform_intervals(const size_t   num_data, 
           const size_t   num_intervals, 
           std::vector<size_t>& result_start_idx) 
{ 
    const size_t avg_interval_len = num_data/num_intervals; 
    const size_t last_interval_len = num_data % num_intervals; 

    // establish the new size of the result vector 
    result_start_idx.resize(num_intervals + 1L); 
    // write the pivot value at the end: 
    result_start_idx[ num_intervals ] = num_data; 

    size_t offset  = 0L; // current offset 

    // use Bresenham's line algorithm to distribute 
    // last_interval_len over num_intervals: 
    intptr_t error = num_intervals/2; 

    for(size_t i = 0L; i < num_intervals; i++) 
    { 
     result_start_idx[ i ] = offset; 
     offset += avg_interval_len; 
     error -= last_interval_len; 
     if(error < 0) 
     { 
      offset++; 
      error += num_intervals; 
     } // if 
    } // for 
} 

इस कोड एन = 100 के लिए अंतराल लंबाई की गणना करता है, एम = 12: 8 9 8 8 9 8 8 9 8 मैं Bresenham's line algorithm पर आधारित एक फिल्म है, जो इस तरह दिखता है जब सी में कोडित ++ के साथ आया था 8 9 8

वास्तविक सवाल यह है कि मुझे नहीं पता कि मेरी समस्या को ठीक से कैसे कॉल किया जाए, इसलिए मुझे इसकी खोज में कठिनाई हुई।

• क्या ऐसे कार्य को पूरा करने के लिए अन्य एल्गोरिदम हैं?
• उन्हें कैसे कहा जाता है? शायद नाम आएंगे यदि मैं आवेदन के अन्य क्षेत्रों को जानता था।

मुझे डेटा क्लस्टरिंग के लिए एक बड़े एल्गोरिदम के हिस्से के रूप में एल्गोरिदम की आवश्यकता थी। मुझे लगता है कि यह समानांतर प्रकार (?) को लागू करने के लिए भी उपयोगी हो सकता है।

Answer 1

यदि आपकी भाषा में पूर्णांक विभाजन है जो छंटनी करता है, तो i के आकार की गणना करने का एक आसान तरीका (N*i+N)/M - (N*i)/M के माध्यम से है। उदाहरण के लिए, अजगर कार्यक्रम के लिए

N=100;M=12 
    for i in range(M): print (N*i+N)/M - (N*i)/M 

संख्या 8 8 9 8 8 9 8 8 9 8 8 9. आउटपुट N=12;M=5 के साथ यह 2 2 3 2 3. आउटपुट N=12;M=3 के साथ यह आउटपुट 4 4 4.

यदि आपकी सेक्शन संख्या 0-आधारित के बजाय 1-आधारित है, तो अभिव्यक्ति (N*i)/M - (N*i-N)/M है।

Answer 2

अंतरिक्ष भरने-वक्र और फ्रैक्टल विमान को उप-विभाजित करते हैं और जटिलता को कम करते हैं। उदाहरण के लिए जेड-वक्र, हिल्बर्ट वक्र, मॉर्टन वक्र है।