~matubara/ChangeLog / 2007-11 →移動しました

■ 配列の順列の列挙 [ruby]

class Array
  def perm()
    if self.length <= 1 then
      [self]
    else
      a=self[1..-1].perm;
      c=[];
      a.each { |x|
        0.upto(x.length) { |y|
          c.push( (y==0 ? [] : x[0..y-1]) +
                  [ self[0] ] +
                  x[y..-1])
        }
      }
      c.uniq
    end
  end
end

"123".split(//).perm.each{ |x|
  p x
}

["1", "2", "3"]
["2", "1", "3"]
["2", "3", "1"]
["1", "3", "2"]
["3", "1", "2"]
["3", "2", "1"]

ruby 1.9 ではArrayクラスにある

(2007-12-18T22:27:03+0900)
C++だと std::next_permutation
http://cplusplus.com/reference/algorithm/next_permutation.html

■ Rubyにおける改行 [ruby]

オブジェクトとメソッドのあいだには改行があってはいけないようです。
↓コンパイルエラー

p(1
  + 2)

p(1+
  2)

■ C++におけるユニコード文字列は std::wstring で [programming][cxx]

C++でユニコード文字といえば
ICU4C
があるけれど、
・APIが非常にJava的なので、あまり使いたくない(STLと相性が悪い)
・正規化処理等を含んでいるので、単に格納して単なる文字列と同じように使いだけの場合にはオーバースペック
などという問題がある。

そこで vector<short> とか考えたけれど、
入出力とかソートとかそれはそれで用意しなければならない。
Javaと違って、統一interfaceをimplementsしてそれを満たせば終わりというわけじゃないので、
面倒。

実は2バイト文字が格納できて入出力もサポートされていて、
かつSTLに対応済（というかSTLの中にある）の
std::wstring
がある。

std::wstring は言語仕様上、単に、
1文字が8ビットより大きいバージョンの std::string
としか定義されていない。
文字長とか文字集合とか、エンコーディングとか、ソート順序とかは全部処理系依存。
この辺が原因で、ポータビリティがないとされている。
(2007-12-18T22:41:39+0900) : 実際、文字コードの指定方法（名前）に関して、Linux同士でも互換性がない。また、複数のエンコーディングを扱うのも苦手。

その辺はあくまで言語仕様の話で、存在する実装では
windows と linux で、wstring = UTF-16文字列
ソートはUTF-16の辞書式らしい。（要出典）
linux では UTF-16 を 32ビットのintに入れて格納しているので、メモリはかなり食う。
wstring の作成は
・処理系がlocaleを持っている
・ソースコードが locale のエンコーディングで書かれている
・扱うデータが locale のエンコーディングで書かれているものだけ
という前提だったら、

std::wstring s;
std::wcin >> s;

という感じでやれる。
このとき、cinを混在させるとなんかややこしいことになった気がするので注意。

■ 均等分割 [cxx]

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

#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;
}

■ なんどめかの「知っていない」 [lx]

「知ってる？」

に対するもっとも適切な応答が

「知ってる」

もしくは

「知らない」

という非対称なペアであること、あるいはもっと端的には、
「知っていない」という表現がほとんど非文法的であることが近年問題になっているわけですが、
簡単に内省による分析をしてみると、

・「知る」は情報の摂取が起こるという”変化”に対応している
・「知っている」は情報を持っているという”変化した結果状態”に対応している
・「知らない」は情報を持っていないという”変化しなかった状態”に対応している
・「知っていない」は？？？

ということが起きているようです。
似たような、しかしもっと普通の規則に従う動詞である「消える」の場合は次のようになります。

・「消える」は”変化”に対応している
・「消えている」は”変化した結果状態”に対応している
・「消えない」は”変化が起きない（変化前状態が繰り返される）”に対応している
・「消えていない」は”変化しなかった結果状態”に対応している

すでに観察されている通り、「ない」の有無での対称性が崩れているという問題と同時に、

・「知る」に関して”変化が起きない”を端的に表す形式がない
   （それを表すには、ふつう、「知ることがない」等の形式を用いる）

という問題（？）が起きていることが分かります。

以上のような、「知る」に関する例外性を説明する説として、
大きくわけて2通りの説が提案されています。


0. 単なる不規則変化
英語等の屈折語になじみのある人の多くは、このように解釈するようです。
つまり、「知っている」の否定は（なぜか｜歴史的混乱があって）「知らない」になり、
これはたまたま「知る」の否定と同じ形をしている、というような解釈です。
しかし、動詞の活用に関して規則性が崩れる、という現象は、
日本語のような膠着語ではかなり受け入れがたく、またこの現象以外にないのではないかと思います。
ですので、ここではこの解釈は不可能、としておきます。

1. 「知る」という単語（に対応する事象）の内在的性質に起因する

1.1. 「知っている？」と聞かれた時点で知るから
http://cellistmiya.typepad.jp/blog/2006/07/__3533.html

「ｘｘを知っている？」と質問された人は、質問されたという事実により、そのことに関する知識を得てしまった、ということになる。そのため、常識を持った大人であれば、質問を受けた途端、そのことについて「知っていない」とはパラドクスになり、そうは言えなくなってしまうのではないか。

「（もしいま訊かれなかったら）知らない（でいただろう）」という感じの解釈。

「（私の声が）聞こえてるー？」「聞こえてない」

という対話に対して「いや聞こえてるんじゃん」というツッコミができることと、
似たような状況が起こっているという解釈です。

1.2. 変化が常に完全な形で起こるから
「消えていない」に類する変化動詞のテイル化形式の意味の構造を内省によって分析してみると、

「（何かが）消えそうな事象が起きたが、それは成し遂げられなかった。そして今に至る」

というようなシナリオが典型的だと思われますが、「知っていない」の場合は、

「（私が）（何かを）知りそうな事象が起きたが、それは成し遂げられなかった。そして今に至る」

のなかでの、”知りそうな”という部分があり得ないように思われます。
なぜかというと、”（私が）知りそうな”という中途半端な状態は存在しにくいからです。
（通常、”知りそうな”状態になった時点で”知った”ことになる）
これが”私が”でなく”彼が”の場合は、（知るという事象を客観視できるので）
「知っていない」の許容度がかなりあがると思うのですがどうでしょうか？

知覚に関する変化＋状態動詞である、
「見える」「聞こえる」等も似たような意味の構造を持っていると思われます。

「見えてる？」「見えない」
「聞こえてる？」「聞こえない」

ただし、「見える」「聞こえる」は変化と状態の双方に用いることができる（上記からテイルを除去してもあまり意味が変わらない）ので、完全に同種とはいえません。

2. 「知る」という単語に関して起こった歴史的変化に起因する

まともな資料分析はしてないですが、

身の程を知る
親の心子知らず

などのように、そもそも「知る」が（「いる」のような）状態動詞であるように見える文例があり、
しかも古い感じです。
(Wed Dec 12 03:17:53 2007) 追記：「知らず」は現代語と共通の用法のようにも思えるので不適当でした。
そこで、

・「知る」は過去状態を示す（こともできる？）動詞だったが、いまは変化動詞。ただし一部に状態動詞の用法が残っている

という仮説を立てることができます。

現代でも

「知ってる？」「（俺が）知るかよ！」
「知ってる？」「（俺が）知るわけない」

という文においては、
「知る」の部分の意味に状態が含まれていると思われます。

いっぽう

「消えてる？」「消えるかよ」

では「消える」の部分は変化を示しています。

（この対比はあまり合意がとれないかもしれません……）