あるテキストに連続しないドットを挿入して、重複なしの文字列を生成したい。

Question

例えばABCDEFGというワードがあった時、
下記のようにドット1つ挿入して文字列を生成することはできたのですが、
A.B.CDEFG
A.BC.DEFG
のようにドット2つ以上使ってさらに可能な限り文字列を生成するよい方法はないでしょうか。
最大で文字数-1個のドットを使う形になります。

var text = 'ABCDEFG';
let gens_arr = [];
for( let i=1; i<text.length; i++ ){
	let gen = text.slice(0, i) + '.' + text.slice(i)

	//重複は除外
	if( -1 === gens_arr.indexOf(gen) ){
		gens_arr.push(gen);
	}
}
console.log(gens_arr);

ログ
A.BCDEFG
AB.CDEFG
ABC.DEFG
ABCD.EFG
ABCDE.FG
ABCDEF.G

Answer 1

まずは、全パターンがどれだけあるか数学的に考えてみましょう。

入れるべき箇所は文字の間の6箇所、それぞれに「入れる」「入れない」の2通りがあるので、全体のパターン数は2の6乗、64通りです（1つも入れないのを除けば63通り）。

あとは、0～63を2進数で表して、1の来る位置にピリオドを入れる、というようにすればいいでしょう。

Comments

[Anon_]

発想はわかるのですが、PGで書くとどのように書けばよいかがわからなくなってしまいまして。。

Answer 2

面白い問題やね。
こんなん考えたで。

まずは理屈からいくわ。

• 'ABCDEFG'という7文字の文字列が与えられたときに、たとえばB、D、G の前にピリオドを挿入する操作は、それぞれの文字が文字列'ABCDEFG'のどこの位置にあるかのインデクスの集合で表すことができる。

　

• つまり、'ABCDEFG' から 'A.BC.DEF.G' を作る操作を、 集合{ 1, 3, 6 } で表すことにする。

　　

• ​このようにピリオドを挿入する位置を表すことにすると、ピリオドを挿入する位置は 1 以上 6（＝与えられた文字列の長さ - 1）以下の整数なので、これらの整数の集合を 　　

X = { 1, 2, 3, 4, 5, 6 }
とする。

• このようにピリオドを入れる位置の集合Xを定めると、'ABCDEFG'の文字間に、連続しないドットを挿入する、すべての操作の集合 P(X) は、（ひとつもピリオドを挿入しないこともひとつの操作と扱って、） X のべき集合 で表すことができる。すなわち

P(X)　＝ { A | A ⊆ X } ＝ { ∅, {1}, {2}, {3}, ・・・ {1, 2}, {1, 3}, ・・・ , { 1, 2, 3, 4, 5, 6 } }

次にコードやねんけど。

• X は配列 [1, 2, 3, 4, 5, 6 ] で実装するで。

　

• 集合を表すことを想定した配列から、その集合のべき集合を表す配列を得るコードは、探せば良さげなやつが色々と見つかるんで、ありがたく流用さしてもらう。今回はロゼッタコードのここに載ってるJSのやつ

function powerset(ary) {
    var ps = [[]];
    for (var i=0; i < ary.length; i++) {
        for (var j = 0, len = ps.length; j < len; j++) {
            ps.push(ps[j].concat(ary[i]));
        }
    }
    return ps;
}

を使うで。

• それと、元の文字列と、ピリオドを挿入する位置を表す配列を受け取って、ピリオドを挿入した文字列を返す関数を作っとくで。とりま、こんなやつ

function insertPeriods(str, positions) {
  const chunks = [...positions, str.length].map((pos, i, ary) => {
    const start = i > 0 ? ary[i-1] : 0
    return str.substring(start, pos);
  });

  return chunks.join('.');  
}

でええのんちゃうか。

• ここまで準備しとけば、あとは、

// 与えられる文字列
const text = 'ABCDEFG';

// ピリオドを挿入する位置の集合Xを表す配列
const X = [...Array(text.length - 1)].map((_, i) => i + 1);
 
// X のべき集合 P(X) を表す配列 （※空集合を表す空配列も含まれる）
const PX = powerset(X);

// PXに含まれるすべてのピリオド挿入位置をtext に適用した文字列を出力
for (const periodPositions of PX) {
  console.log(insertPeriods(text, periodPositions));
}

で、ピリオド入りの文字列の全パターンが出力されますわ ➡ サンプル

**補足： ** Xのべき集合を、数学で書くとき、「２のX乗」みたいに書くこともあってん。意味するところとして、X の要素の数を |X| と書くとすると、Xのべき集合の要素の数は 2の|X|乗になるねん。今回の例だと、X = {1, 2, 3, 4, 5, 6} で、要素の数は 6 個やから、そのべき集合の要素数は　2の6乗の64やねん。これは、'ABCDEFG'から作られるピリオド入れた文字列のパターン数に一致するゆうこっちゃ。ただし、64パターンの中には、0個のピリオドを入れる、つまりピリオドを入れないという操作で得られる、元の文字列と同じ文字列も含まれんで。（なぜゆうたら、べき集合には必ず空集合∅が含まれとるからやねん）

さらに追伸： 要素n個の集合のべき集合を、再帰と、0以上(2のn乗-1)以下の整数に対するビット操作の２通りで作ろうゆう人がおったわ➡ Power Set Algorithm with Recursion or Bits
ビット操作でやるのやったら、こちらさんが書いたコード

var powerSet = function (str) {
  const results = [];
  for (let i = 0; i < 1 << str.length; i++) {
    let subset = "";
    for (let j = 0; j < str.length; j++) {
      if (i & (1 << j)) {
        subset += str[j];
      }
    }
    results.push(subset);
  }
  return results;
};

の、 if (i & (1 << j)) { 　でやってる & や << だったりが参考になるやもしれんね〜

Comments

[Anon_]

理解するのに時間がかかって御礼言うのがおそなってしまいましたわ。

powerset()の処理がまさにやりたかったことやで！
最初何やってるか理解できへんかったから、logに出力して頑張って理解したで。重複を後から削除するとかいうかっこ悪いコードもなく、おかげさんでめちゃくちゃ綺麗なコードで、やりたいことが実装できたで。
ほんまに感謝ですわ！

[Anon_]

補足のビット操作の方のpowerSet変数に、そのまま置き換えその後のコードは同じら同じもので動作したのですが、return値の中身を確認すると違う値が入っています。
これはどういった理屈なのでしょうか。。

[退会済みユーザー]

> やりたいことが実装できたで。

ゆうことで、おめでとさん！

さて、

> 補足のビット操作の方のpowerSet変数に、
> ・・・
> これはどういった理屈なのでしょうか。。

の件も調べてみたで。

ビット操作の方のpowerSet() 関数は、引数名が str になっていて、文字列を受け取る想定になってますが、これに、[1, 2, 3, 4, 5, 6 ] という整数の配列を渡してもエラーにはならず、べき集合に相当する配列を返してくれます。

ただし、このビット操作の方のpowerSet()が返してくれるのは、ロゼッタコードに載っているほうのfunction powerset(ary) とは違うて、以下のような、数字の文字列を要素とする配列です。

[
'', '1', '2', '12', '3', '13',
'23', '123', '4', '14', '24', '124',
・・・・
'2356', '12356', '456', '1456', '2456', '12456',
'3456', '13456', '23456', '123456'
]

このような配列が変数PXに入ってきて、各文字列が

for (const periodPositions of PX) {
console.log(insertPeriods(text, periodPositions));
}

で、insertPeriods(text, periodPositions) の第二引数して渡されます。

それで、

insertPeriods(str, positions)

のほうも確認したんやけど、第二引数の positions には [1, 5, 6] みたいな整数の配列が入ってくる想定で作りましたんやけど、(ビット操作のほうが返すPowerSet の要素である） '156' のような文字列でも、問題なく動くようになってましたわ。というのは、ポイントとして２点あって、

1) 文字列は（配列と同様に）反復可能(iterable) なので、スプレッド構文（... ）によって（エラーにならず）要素に展開される。

ただし、 positions が文字列 '156' の場合、 ...positions によって、 整数のシーケンス 1, 5, 6 ではなく、一文字の文字列のシーケンス '1', '5', '6' に展開される。なので、

function insertPeriods(str, positions) {
　const chunks = [...positions, str.length].map((pos, i, ary) => {　

んとこのmapに渡している関数の第1引数の pos には、最後の str.length 以外は、整数やなく文字列で数字が入ってきます。それで、エラーになるかゆうたら、ならない。それはなぜかゆうたら

2) str.substring(start, pos);　の第二引数 pos は整数でなく文字列が入ってきても、それが整数に変換できるのであれば、あんじょう変換後の整数が渡されたものとして動作してくれる。

ようになっているからやった。それで全体として、

> 補足のビット操作の方のpowerSet変数に、そのまま置き換えその後のコードは同じら同じもので動作した

ゆう結果になったわけやね。
（ちなみに、念のため、JavaScript やなくTypeScript で、substring の第二引数に文字列の数字渡すコード書いたら「第二引数は number | undefined やから文字列はあかんで」ゆうエラーになりましたわ。）

ところが、
> そのまま置き換えその後のコードは同じら同じもので動作した
ゆう結果になるためには、ビット操作のほうのpowerSet 関数に渡す配列が、'ABCDEFG'んときの
[1, 2, 3, 4, 5, 6]
みたいに、要素の整数が全部一桁だったらよいのやけど、最初に与えられる文字列が、'ABCDEFG' やのうて、AからKまで含む 'ABCDEFGHIJK' になったらアカンようになるで。
そのカラクリはこうや。
'ABCDEFGHIJK' は 11文字あるので、 powerset関数に渡される配列は
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
になります。
なので、これを元のロゼッタコードのpowerset() に渡すと、配列の配列が返されるわけやけど、その要素の例えば
[2, 10]
を考えると、この [2, 10] を insertPeriods( 'ABCDEFGHIJK' , positions) の第二引数として渡すと、CとKの前にピリオドを入れた

AB.CDEFGHIJ.K

が返ってきます。これは意図通りです。

ところが、ビット操作の方のpowerSet() から返されたべき集合を表す配列では、その要素が数字を連結した文字列なので、[2, 10] に相当する要素は '210' という文字列ですわ。で、この'210' ゆう文字列が、insertPeriodsの第二引数に渡ってきて、スプレッド ... で展開されると、('2' と '10' やなくて）
'2', '1', '0'
の３つに展開されてしまって、結果どうなるかゆうたら、
insertPeriods('ABCDEFGHIJK', '210');
を実際やってみると分かりますが、

AB.B.A.ABCDEFGHIJK

ゆう、わやな文字列になってしまいます。

なので、
> そのまま置き換えその後のコードは同じら同じもので動作
するんは、10文字の 'ABCDEFGHIJ' までやな。これだと、powerset　関数に渡す配列は
[1, 2, 3, 4, 5, 6, 7, 8, 9] で、要素がどれも一桁の整数やからね。

ほなまた〜

[Anon_]

とてもわかりやすい解説をありがとうございました。
ロゼッタコードの方を使用させていただこうと思います。