मेरे पास वजन की एक सरणी है, उदाहरण के लिए

[1, 0, 3, 5]

दो तारों के बीच की दूरी को अलग-अलग बिट्स के वजन के योग के रूप में परिभाषित किया जाता है, जैसे:

size_t distance(const std::string& str1, const std::string& str2, const std::vector<size_t>& weights) {
  size_t result = 0;
  for (size_t i = 0; i < str1.size(); ++i) {
    if (str1[i] != str2.at(i))
      result += weights.at(i);
  }
  return result;
}

और उदाहरण के लिए स्ट्रिंग शुरू करना

'1101'

मुझे इस तरह से क्रमपरिवर्तन उत्पन्न करने की आवश्यकता है कि मूल से सबसे कम दूरी वाले तार पहले जाएं, जैसे:

'1001'  # changed bits: 2nd. Because it has lowest weight. Distance is 0
'0101'  # changed bits: 1st.                               Distance is 1
'0001'  # changed bits: 1st, 2nd.                          Distance is 1
'1011'  # changed bits: 2nd, 3rd.                          Distance is 3
'1111'  # changed bits: 3rd.                               Distance is 3
'0111'  # changed bits: 1st, 3rd.                          Distance is 4
'0011'  # changed bits: 1st, 2nd, 3rd.                     Distance is 4
'1100'  # changed bits: 4th.                               Distance is 5
'1000'  # changed bits: 2nd, 4th.                          Distance is 5
'0100'  # changed bits: 1st, 4th.                          Distance is 6
'0000'  # changed bits: 1st, 2nd, 4th.                     Distance is 6
'1110'  # changed bits: 3rd, 4th.                          Distance is 8
'1010'  # changed bits: 2nd, 3rd, 4th.                     Distance is 8
'0110'  # changed bits: 1st, 3nd, 4th.                     Distance is 9
'0010'  # changed bits: 1st, 2nd, 3rd, 4th.                Distance is 9

मुझे कोड की आवश्यकता नहीं है, मुझे केवल एक एल्गोरिदम चाहिए जो लंबाई एन की स्ट्रिंग प्राप्त करता है, समान लंबाई के वजन की सरणी और मैं इनपुट के रूप में और पूरी सूची उत्पन्न किए बिना और इसे सॉर्ट किए बिना i-th क्रमपरिवर्तन उत्पन्न करता है।

3
devalone 26 अगस्त 2018, 09:56
1
आपने क्या प्रयास किया है? क्या काम नहीं करता? आप जिस समस्या को हल करने का प्रयास कर रहे हैं वह बहुत स्पष्ट नहीं है
 – 
Alan Birtles
26 अगस्त 2018, 09:59
@AlanBirtles, मैंने इसे थोड़ा और स्पष्ट करने की कोशिश की है
 – 
devalone
26 अगस्त 2018, 10:08
एक ही लंबाई के लिए भार की सरणी उत्पन्न करता है। कैसे?
 – 
GolamMazid Sajib
26 अगस्त 2018, 10:17
3
वे वास्तव में क्रमपरिवर्तन नहीं हैं (क्रमपरिवर्तन केवल क्रम बदलते हैं)। '0' और '1' के सभी चार-वर्णों के तार उत्पन्न करने के लिए, संख्याओं को 0 से 15 तक चार बाइनरी अंकों में बदलें।
 – 
molbdnilo
26 अगस्त 2018, 10:19
1
ऐसा लगता है जैसे आप उपरोक्त प्रकार के सभी संभावित तारों को "1101" से उनकी दूरी के अनुसार क्रमबद्ध करना चाहते हैं। यदि हां, तो आप "क्रमपरिवर्तन" शब्द का उल्लेख करना एक लाल हेरिंग का एक सा है।
 – 
Ulrich Eckhardt
26 अगस्त 2018, 12:15

2 जवाब

कठिन समस्या की तरह लगता है।

यदि आप क्रमपरिवर्तन अनुक्रमणिका के लिए size_t का उपयोग कर रहे हैं, तो आपके तार 32 या 64 वर्णों तक सीमित होंगे, अन्यथा आपको क्रमपरिवर्तन अनुक्रमणिका के लिए बड़े पूर्णांक की आवश्यकता होगी। इसलिए, आप स्ट्रिंग्स से size_t बिटमास्क पर स्विच कर सकते हैं।

इस तरह आपका एल्गोरिथ्म अब स्ट्रिंग पर निर्भर नहीं करता है, आप इनपुट स्ट्रिंग बिटमास्क के साथ i-th बिटमास्क, XOR it (^ ऑपरेटर C++ में) पाते हैं, और आपको अपना परिणाम मिल जाता है। कठिन हिस्सा i-th बिटमास्क ढूंढ रहा है लेकिन इस तरह, यानी एल्गोरिदम के आंतरिक लूप में तारों का उपयोग किए बिना, कोड बहुत तेज़ होगा (परिमाण का आदेश)।

अब कठिन हिस्सा यह है कि मुखौटा कैसे खोजा जाए। सामान्य स्थिति के लिए, मैं सोच सकता हूं कि एकमात्र एल्गोरिदम व्यापक खोज है, शायद प्रदर्शन के लिए memoisation के साथ . यह छोटे क्रमपरिवर्तन सूचकांकों के लिए तेज़ होगा लेकिन बड़े सूचकांकों के लिए धीमा होगा।

यदि आप कंपाइल-टाइम पर अपना वज़न जानते हैं, तो आप इंडेक्स को सर्च ट्री में प्रीकंप्यूट कर सकते हैं, लेकिन यह C ++ के बाहर सबसे अच्छा किया जाता है, इस तरह के जटिल एल्गोरिदम के लिए टेम्प्लेट मेटाप्रोग्रामिंग का उपयोग करना बहुत कठिन है।

पी.एस. एक विशेष मामला है जो आपके काम आ सकता है। भार को क्रमबद्ध करें, और जांचें कि क्या निम्नलिखित सत्य है weights[N] == weights[N-1] || weights[N] >= sum( weights[0 .. N-1] सभी 1

BTW, प्रश्न में आपके वज़न उस स्थिति को संतुष्ट करते हैं, क्योंकि 1>=0, 3>=0+1 और 5>=0+1+3, इसलिए यह सरल एल्गोरिथम आपके विशेष वज़न के लिए ठीक काम करेगा।

अपडेट करें: यहां एक संपूर्ण समाधान दिया गया है। यह आपके नमूने से थोड़ा अलग परिणाम प्रिंट करता है, उदा। आपके उदाहरण में आपके पास '1011' फिर '1111' है, मेरा कोड '1111' के तुरंत बाद '1011' प्रिंट करेगा लेकिन उनकी दूरी समान है, यानी मेरा एल्गोरिदम अभी भी ठीक काम करता है।

#include <string>
#include <vector>
#include <algorithm>
#include <stdio.h>

struct WeightWithBit
{
    size_t weight, bit;
};

// Sort the weights while preserving the original order in the separate field
std::vector<WeightWithBit> sortWeights( const std::vector<size_t>& weights )
{
    std::vector<WeightWithBit> sorted;
    sorted.resize( weights.size() );
    for( size_t i = 0; i < weights.size(); i++ )
    {
        sorted[ i ].weight = weights[ i ];
        sorted[ i ].bit = ( (size_t)1 << i );
    }
    std::sort( sorted.begin(), sorted.end(), []( const WeightWithBit& a, const WeightWithBit& b ) { return a.weight < b.weight; } );
    return sorted;
}

// Check if the simple bit-based algorithm will work with these weights
bool willFastAlgorithmWork( const std::vector<WeightWithBit>& sorted )
{
    size_t prev = 0, sum = 0;
    for( const auto& wb : sorted )
    {
        const size_t w = wb.weight;
        if( w == prev || w >= sum )
        {
            prev = w;
            sum += w;
            continue;
        }
        return false;
    }
    return true;
}

size_t bitsFromString( const std::string& s )
{
    if( s.length() > sizeof( size_t ) * 8 )
        throw std::invalid_argument( "The string's too long, permutation index will overflow" );
    size_t result = 0;
    for( size_t i = 0; i < s.length(); i++ )
        if( s[ i ] != '0' )
            result |= ( (size_t)1 << i );
    return result;
}

std::string stringFromBits( size_t bits, size_t length )
{
    std::string result;
    result.reserve( length );
    for( size_t i = 0; i < length; i++, bits = bits >> 1 )
        result += ( bits & 1 ) ? '1' : '0';
    return result;
}

// Calculate the permitation. Index is 0-based, 0 will return the original string without any changes.
std::string permitation( const std::string& str, const std::vector<WeightWithBit>& weights, size_t index )
{
    // Reorder the bits to get the bitmask.
    // BTW, if this function is called many times for the same weights, it's a good idea to extract just the ".bit" fields and put it into a separate vector, memory locality will be slightly better.
    size_t reordered = 0;
    for( size_t i = 0; index; i++, index = index >> 1 )
        if( index & 1 )
            reordered |= weights[ i ].bit;

    // Convert string into bits
    const size_t input = bitsFromString( str );
    // Calculate the result by flipping the bits in the input according to the mask.
    const size_t result = input ^ reordered;
    // Convert result to string
    return stringFromBits( result, str.length() );
}

int main()
{
    const std::vector<size_t> weights = { 1, 0, 3, 5 };

    using namespace std::literals::string_literals;
    const std::string theString = "1101"s;

    if( weights.size() != theString.length() )
    {
        printf( "Size mismatch" );
        return 1;
    }

    if( weights.size() > sizeof( size_t ) * 8 )
    {
        printf( "The string is too long" );
        return 1;
    }

    // Sort weights and check are they suitable for the fast algorithm
    const std::vector<WeightWithBit> sorted = sortWeights( weights );
    if( !willFastAlgorithmWork( sorted ) )
    {
        printf( "The weights aren't suitable for the fast algorithm" );
        return 1;
    }

    // Print all permutations
    const size_t maxIndex = ( 1 << weights.size() ) - 1;
    for( size_t i = 0; true; i++ )
    {
        const std::string p = permitation( theString, sorted, i );
        printf( "%zu: %s\n", i, p.c_str() );
        if( i == maxIndex )
            break;  // Avoid endless loop when the string is exactly 32 or 64 characters.
    }
    return 0;
}
1
Soonts 26 अगस्त 2018, 13:52
बहुत बढ़िया, धन्यवाद, लेकिन मैं पूरी तरह समझ नहीं पा रहा हूं कि यह इस विशेष मामले के लिए क्यों काम करता है
 – 
devalone
26 अगस्त 2018, 19:47

यदि आप केवल ith क्रमपरिवर्तन चाहते हैं, तो आपको केवल वज़न को देखने की ज़रूरत है।

यदि वज़न को रिवर्स सॉर्ट किया गया था, तो [5,3,1,0] कहें और आप 5वां क्रमपरिवर्तन चाहते थे, तो आपको बाइनरी में 0, 1, 0, 1 को 5 = 0101 के रूप में फ़्लिप करना होगा।

तो आपको वजन से इसकी मूल अनुक्रमणिका तक बहुत छोटी मैपिंग की आवश्यकता है। फिर, सबसे बड़े से छोटे को क्रमबद्ध करें, N के द्विआधारी प्रतिनिधित्व के आधार पर Nth क्रमपरिवर्तन को पकड़ें, और मूल स्ट्रिंग के मैप किए गए बिट्स को फ़्लिप करें।

0
James Poag 26 अगस्त 2018, 14:57
"एन के द्विआधारी प्रतिनिधित्व के आधार पर एनएच क्रमपरिवर्तन को पकड़ो" वजन हैं [4, 5, 6], द्विआधारी प्रतिनिधित्व 6 से पहले 4 + 5 = 9 की दूरी लौटाएगा। यह केवल कुछ वज़न के लिए काम करता है (जैसे [1, 0 के लिए ठीक काम करता है] , 3, 5]), कार्यान्वयन के लिए मेरा उत्तर देखें।
 – 
Soonts
26 अगस्त 2018, 20:07
तुम सही हो, मैंने इसके बारे में नहीं सोचा था। केवल अभाज्य संख्या भार के लिए कार्य करता है।
 – 
James Poag
26 अगस्त 2018, 23:13