2016-01-30 68 views
0

所以我正在處理一個問題,我需要生成不僅是特定長度的二進制字符串的排列,而且還包含特定數量的1和零。我有一個算法來做到這一點,但是它是遞歸的,我正在處理64位無符號整數,所以它們有可能對於函數來說太大而無法處理。希望有人能幫助我,或建議我應該看看另一種算法。任何幫助將非常感激。非遞歸二進制字符串排列生成器

+2

你有沒有考慮過使用std :: next_permutation? – user3188346

+0

字符串的最大長度是多少? – Lingxi

+0

最大長度爲64字符 –

回答

0

如果你做了遞歸權,你可以處理長度爲64等二進制序列。

在下面的算法中,遞歸的深度由序列的長度(在你的情況下是64)限定,並且在遞歸的每個級別中,我們只在堆棧上放置幾個字節。不是儲存所有的結果,只要準備就緒,我們就輸出一個序列,所以我們不會在內存中積累大量的序列。請注意0​​變量是如何通過遞歸傳遞的。

#include <functional> 
#include <iostream> 

void create_all_binary_subsequence(std::string& s, int offset, int num_of_ones, std::function<void(const std::string& s)> callback) 
{ 
    if (num_of_ones == 0) 
     callback(s); 
    else { 
     for (int i = offset; i <= (int)s.size() - num_of_ones; ++i) { 
      s[i] = '1'; 
      create_all_binary_subsequence(s, i + 1, num_of_ones - 1, callback); 
      s[i] = '0'; 
     } 
    } 
} 

void create_all_binary_sequences(int num_of_ones, int length, std::function<void(const std::string& s)> callback) { 
    std::string s(length, '0'); 
    create_all_binary_subsequence(s, 0, num_of_ones, callback); 
} 

int main(int argc, char *argv[]) 
{ 
    create_all_binary_sequences(3, 5, [](const std::string& s) { 
     std::cout << s.c_str() << "\n"; 
    }); 
    return 0; 
} 

,輸出是

11100 
11010 
11001 
10110 
10101 
10011 
01110 
01101 
01011 
00111 
+0

太棒了,感謝您的幫助。不過,我需要將生成的排列作爲整個字符串。有沒有辦法讓我使用這個現有的代碼做到這一點?我嘗試了一下你在seq [i]上的演員陣容,並且我也嘗試將這個char數組設置爲一個字符串,但這兩個都沒有奏效。 –

+0

好的。我修改了算法,使用std :: string而不是char數組。它現在更短,更快 –

2

我會建議依靠這個任務的標準庫。您可以使用std::next_permutation函數,它將爲您提供所有可能的排列方式。請看看這個例子:

#include <iostream> 
#include <algorithm> 
#include <array> 

template <class T> 
void print(const T& array) 
{ 
    std::cout << "{ "; 
    for(bool i : array) { std::cout << i << " "; } 
    std::cout << "}" << std::endl; 
} 

int main() 
{ 
    std::array<bool, 5> data = { false, false, true, true, true }; 

    print(data); 

    while(std::next_permutation(std::begin(data), std::end(data))) 
    { 
      print(data); 
    } 
} 

,這將導致像這樣的東西:

{ 0 0 1 1 1 } 
{ 0 1 0 1 1 } 
{ 0 1 1 0 1 } 
{ 0 1 1 1 0 } 
{ 1 0 0 1 1 } 
{ 1 0 1 0 1 } 
{ 1 0 1 1 0 } 
{ 1 1 0 0 1 } 
{ 1 1 0 1 0 } 
{ 1 1 1 0 0 } 

編輯:

如果你希望能夠挑選1和0的數在運行時,你需要排列爲字符串的形式,你可以準備第一個排列爲std::string並使用std::next_permutation就可以了。例如:

#include <iostream> 
#include <algorithm> 
#include <string> 

std::string constructFirstPermutation(size_t numberOfZeros, size_t numberOfOnes) 
{ 
    std::string result; 
    result.reserve(numberOfZeros + numberOfOnes); 
    result.append(numberOfZeros, '0'); 
    result.append(numberOfOnes, '1'); 

    return result; 
} 

int main() 
{ 
    std::string data = constructFirstPermutation(5,10); 

    std::cout << data << std::endl; 

    while(std::next_permutation(std::begin(data), std::end(data))) 
    { 
     std::cout << data << std::endl; 
    } 
} 
+0

'矢量'值得避免 - 這可悲的不是你可能期望的。 'deque '或'vector '不太可能導致悲傷。 –

+0

@AlanStokes如果可能的話,或者簡單地說'bool [n]'。 – Lingxi

+0

@AlanStokes我已將'vector '更改爲'array '。不知道'矢量'問題,謝謝 – user3188346