Разделяй и властвуй алгоритм для генерации n-битных строк?

Question

Может кто-нибудь сказать, пожалуйста, как генерировать n-битные строки (все возможные комбинации), т.е. подсчитывать биты от 0 до 2^n-1, используя подход "разделяй и властвуй".

Я смог сделать это с помощью следующего алгоритма, но сложность пространства, а также сложность времени имеют значение O(2^n). Может ли кто-нибудь дать мне лучший алгоритм (используя "Разделяй и властвуй"), который требует меньше места, чем этот.

ArrayList generate(int n)
 {
      if(n==1) 
         {  
            Create an arrayList and store strings "0" and "1";
         }
     else
    {
         generate(n-1)

         now recompose the solution to get 2^n strings and return this arraylist
         "PROBLEM here is that the length of the array list is also getting
         exponential"

    }
 }

Answer 1

Я считаю, что вас неправильно поняли. Генерация битовой строки сама по себе не является проблемой, поэтому вы не можете предложить решение для нее. Возможно, вы оставили часть проблемы. Например, вы можете определить представление решения, используя битовую строку, а затем попытаться найти оптимальную битовую строку для данной проблемы.

Еще одна вещь, в общем случае временная сложность задачи, представленной в виде n-битной строки, всегда равна O(2^n), если проблема не определена. Затем вы можете использовать критерии задачи для уменьшения любой сложности. Но прежде чем проблема будет определена, генерация и обход n-битной строки всегда требует от вас стремления к каждой возможной комбинации 2 ^ n.

РЕДАКТИРОВАТЬ:

Вот псевдокод для разделяй и властвуй, если необходимо:

solution breakdown(problem p)
{
    if (smallenough(p))
    {
        return solve(p);
    }
    problem[] subproblems = divide(p);
    solution[] subsolutions;
    for (i=0; i<count(subproblems); i++)
    {
        subsolutions[i] = breakdown(subproblems[i]);
    }
    return reconstruct(subsolutions);
}