文字列を全ての組み合わせで２つに分割する

[山崎]

毎度お世話になっております、山崎です。
今回は、文字列の分割についての方法をお伺いに参りました。

ある文字列Ｓを、考えられる全ての組み合わせで　文字列Ａと文字列Ｂの２つの文字列に分割し、その文字列を得る
というプログラムを考えているのですが、何日考え続けても有効なプログラムが浮かんできません。

分割の条件としては、
・文字列Ｓは'A'から'Z'までの文字で構成され、同じ文字は２つ以上存在しない。長さは２文字以上。
・各文字列中の文字の並び順が違っても区別しない。"AC"と"CA"は同じもの。（常にA→Zの順でソートされる）
・文字列Ａ，Ｂは１文字以上。

例えば文字列Ｓが"ABCD"だとします。
そうするとこれは、（文字列Ａ,文字列Ｂ　の順番で記述しています）
A,BCD　　　B,ACD　　　C,ABD　　　D,ABC
AB,CD　　　AC,BD　　　AD,BC　　　BC,AD　　　BD,AC　　　CD,AB
ABC,D　　　ABD,C　　　ACD,B　　　BCD,A
この１４通りに分割することができます。

文字列Ｓが"AB"のときは
A,B　と　B,A　の２通りが考えられます。

言うまでもないかもしれませんが、文字列Ａが決まれば自動的に文字列Ｂも決まります。

私は以下のコードのように、文字列Ａの文字数によってswitch文を分岐させ、
文字列Ａがn文字のときはfor文のn重ループで文字列Ｓから１ループで１文字ずつ合計n個選びＡを決める、
という方法を考えたのですが、この方法ではnが大きな数値のときに対応できません。

void GetStrA(char* S)
{
	for(int i=1;i<strlen(S);i++)
		switch(i)
		{
		case 1:
			for(...){
				//文字列Ｓから１文字選び文字列Ａとする。
				//Ａを保存する
			}
				break;
		case 2:
			for(...)
				for(...){
					//文字列Ｓから１文字ずつ選び文字列Ａに加える
					//Ａを保存する
				}
			break;
		case 3:
			for(...)
				for(...)
					for(...){
						//文字列Ｓから１文字ずつ選び文字列Ａに加える
						//Ａを保存する
					}
			break;
		case ...
			...
		}
}

なお、Ｓを分割して得た文字列Ａ、Ｂの保存のやり方は特に指定はありません。
文字列型のvectorにpushする、というのが適当でしょうか。
Ａが決まればＢも自然に決まるので、ここではＢを求める処理は記述していません。

どうすれば、文字列Ｓを上の条件を満たす考えられる全ての組み合わせで２つに分割できるのでしょうか。

[ねこ]

ぱっと見て答えてるので間違ってるかもしれません。

１．FOR文で1～文字数－１までループ
２．文字数分のパターン( 文字数ｘ(文字数－１))ループ
　　４文字なら１２３４，１２４３、１４２３等すべてのパターンを取得する

３．パターンに対応する文字をBYTE型で取得。ABCDで1234なら65,66,67,68(・・・だったかな)
４．Aのバイトコード(65)を引いてシフトする↑の例なら (1 << 0, 1 << 1, 1 << 2, 1 << 3)となる
５．５で求めた値をパイプでつなげる( １，３分けなら「①と②|③|④」 )
６．A，B配列(ベクターでもなんでも良い)に５で計算した値( DWORD )を格納
７．格納する毎にＡ，Ｂに既に追加された値をチェックして同じ値なら追加しない
８．全パターンが格納されるので、取得時はビットから逆キャストして文字コードを取得する

４～６でビットにしているのはアルファベットが２６個(32ビット未満)で
そのまま保持しているとABCとBCA等を比較する際に何通りかのチェックが必要で手間だからです。
ビットにしておくとif( ( A == B )で済みます。
取得時は値に対して
for( int i = 0; i < 26; i++ ) {
if( ( 1 << i ) & 配列の値 ) {
char( 65 + i )をどっか追加
}
}

見直してみて自分でもすごく分かりにくい説明だと思いました。
他にもっと簡単なやり方知ってる方は僕のを無視して書き込んでやってくださいorz

[たいちう]

こんな感じでいいんでない

int n = Sの長さ;
for (int i = 1; i < (1 << n) - 1; i++) {
for (int j = 0; j < n; j++) {
if (i & (1 << j))
S[j]をAに追加
else
S[j]をBに追加
}
AとBを表示
}

[non]

２つに分けた文字列で左側のグループに必ずAが含まれるとしたら、
１４通りではなく
A,BCD　　　B,ACD　　　C,ABD　　　D,ABC
AB,CD　　　AC,BD　　　AD,BC　　　BC,AD　　　BD,AC　　　CD,AB
ABC,D　　　ABD,C　　　ACD,B　　　BCD,A
７通りですよね。
ですから、かならずAが含まれている文字列のみを表示するように作ってみました。
プログラムの説明は面倒なのでしません。自分で考えてね。

#include<stdio.h>
#include<string.h>

char str[/url]="ABCD";
char str1[100];
void disp(int n,int m,int z)
{
	int i;
	if(n==z-1)
		return;
	for(i=m+1;i<z;i++){
		str1[n]=str;
		str1[n+1]='\0';
		puts(str1);
		disp(n+1,i,z);
	}
}
int main(void)
{
	str1[0]=str[0];
	puts(str1);
	disp(1,0,strlen(str));
	return;
}

[山崎]

ねこさん、たいちうさん、nonさん、ご返答誠にありがとうございます。
おかげさまで、文字列の分割を実現することができました。

今回は、たいちうさんのコードを参考とさせて頂きました。
ねこさんとnonさんの方法も後ほど検討させて頂きますね。

たいちうさんのコードを見て大感激しました…！！
私が何日考えても思いつかなかったアルゴリズムを、
たった数行のコードで実現なさってしまいますとは…！
尊敬と同時に、私の腕の無さを実感いたしました。
これからも精進したいと思います。

ご返事くださった皆様、誠にありがとうございました。

[たいちう]

そこまで書かれると少し照れるな。
コードを理解できて感激できるならば、山崎さんもなかなかです。
今後このパターンを応用できることでしょう。

# preタグを付け忘れて見にくくなってすみません。