均等分割

最初を適当に決めて、残りを再帰で均等に。
頭の悪いアルゴリズムなので、計算量とかスタックとかがいろいろ大変なことになっている。

#include <iostream>
#include <list>
#include <iterator>
#include <locale>
#include <cassert>

using namespace std;

pair<list<wstring>,size_t> divid_len(size_t num, const wchar_t* str, size_t len) {
  if ( num == 1 ) {
    for ( ; ; ++len ) {
      if ( *(str+len) == L'\0' ) {
        list<wstring> l;
        l.push_back(wstring(str,len));
        return make_pair(l, len);
      }
    }
  } else {
    for ( ; ; ++len ) {
      pair<list<wstring>, size_t> other = divid_len(num - 1, str + len, len);
      if ( abs(static_cast<long>(other.second - len)) <= 1 ) {
        list<wstring>& l = other.first;
        l.push_front(wstring(str,len));
        return make_pair(other.first, max(len, other.second));
      }
    }
    assert(false);
  }
}

list<wstring> divid(size_t size, const wchar_t* str) {
  return divid_len(size, str, 0).first;
}

int main() {
  locale::global(locale(""));
  const wchar_t* sample = L"ゆめよりもはかなき世のなかをなげきわびつゝあかしくらすほどに四月十よひにもなりぬれば木のしたくらがりもてゆく";
  list<wstring> ans;
  ans = divid(4, sample);
  copy(ans.begin(), ans.end(), ostream_iterator<wstring, wchar_t>(wcout, L"\n"));
  ans = divid(5, sample);
  copy(ans.begin(), ans.end(), ostream_iterator<wstring, wchar_t>(wcout, L"\n"));
  ans = divid(6, sample);
  copy(ans.begin(), ans.end(), ostream_iterator<wstring, wchar_t>(wcout, L"\n"));
  return 0;
}