所以我正在處理一個問題,我需要生成不僅是特定長度的二進制字符串的排列,而且還包含特定數量的1和零。我有一個算法來做到這一點,但是它是遞歸的,我正在處理64位無符號整數,所以它們有可能對於函數來說太大而無法處理。希望有人能幫助我,或建議我應該看看另一種算法。任何幫助將非常感激。非遞歸二進制字符串排列生成器
回答
如果你做了遞歸權,你可以處理長度爲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
太棒了,感謝您的幫助。不過,我需要將生成的排列作爲整個字符串。有沒有辦法讓我使用這個現有的代碼做到這一點?我嘗試了一下你在seq [i]上的演員陣容,並且我也嘗試將這個char數組設置爲一個字符串,但這兩個都沒有奏效。 –
好的。我修改了算法,使用std :: string而不是char數組。它現在更短,更快 –
我會建議依靠這個任務的標準庫。您可以使用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;
}
}
'矢量
@AlanStokes如果可能的話,或者簡單地說'bool [n]'。 – Lingxi
@AlanStokes我已將'vector
- 1. 遞歸非二進制,非排序樹搜索使用C#lambas
- 2. 停止遞歸生成器和排列
- 3. 遞歸字符串數組的排列
- 4. 無遞歸的字符串排列
- 5. 遞歸排列字符串崩潰
- 6. 帶遞歸的字符串排列
- 7. 遞歸二進制搜索和排序
- 8. Java中的字符串排列(非遞歸)
- 9. 遞歸序列生成器
- 10. MySQL比較二進制排序與二進制字符串
- 11. 在java中遞歸生成一個字符串的所有排列
- 12. 非遞歸版本排列
- 13. Python非遞歸排列
- 14. 比較字符串二進制(非字母數字字符)
- 15. 瞭解遞歸生成排列
- 16. 遞歸二進制搜索
- 17. 二進制遞歸搜索
- 18. 從字符串到二進制列表
- 19. PHP - 如何使用控制字符或二進制數據生成字符串?
- 20. 遞歸二進制到十進制
- 21. 字符串到二進制[]
- 22. Json_encode二進制字符串
- 23. 字符串爲二進制
- 24. 二進制字符串
- 25. 遞歸產生排列
- 26. 十六進制字符串到二進制字符串
- 27. 二進制字符串到十六進制字符串java
- 28. Ruby:十六進制字符串到二進制字符串
- 29. 遞歸置換生成的字符
- 30. 將二進制字符串轉換爲二進制文字
你有沒有考慮過使用std :: next_permutation? – user3188346
字符串的最大長度是多少? – Lingxi
最大長度爲64字符 –