Нерекурсивный генератор перестановок двоичной строки

Question

Итак, я работаю над проблемой, когда мне нужно создавать перестановки бинарных строк, которые не только имеют определенную длину, но также содержат определенное количество единиц и нулей. У меня есть алгоритм, который делает это, однако он является рекурсивным, и я имею дело с 64-битными целыми без знака, поэтому существует вероятность того, что они будут слишком большими для обработки функции. Надеюсь, кто-то может помочь мне или предложить другой алгоритм, на который я должен взглянуть. Любая помощь приветствуется.

Answer 1

Если вы выполняете правильную рекурсию, вы можете обрабатывать двоичные последовательности длиной 64 и более.

В следующем алгоритме глубина рекурсии ограничена длиной последовательности (которая равна 64 в вашем случае), и на каждом уровне рекурсии мы кладем только несколько байтов в стек. Вместо сохранения всех результатов мы просто выводим последовательность всякий раз, когда она готова, поэтому мы не накапливаем много последовательностей в памяти. Обратите внимание, как переменная s передается через рекурсию.

#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 

Answer 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 } 

Edit:

Если вы хотите, чтобы иметь возможность выбрать количество единиц и нулей во время выполнения и вам нужно, чтобы перестановка была в виде строки, вы можете подготовить первую перестановку как 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; 
    } 
}