Petitverse

重複ありだと無限に生成できるので、とりあえず重複なし。
こういうプログラム苦手なので間違ってたらすみません。

多分動的計画法と呼ばれる方法を使うと出来ると思います。
動的計画法はプログラミングの最難関と呼ばれるぐらい難しいので、とりあえずプログラムだけ書きます。

あっ。DP(動的計画法の略)じゃ無理だ。別の方法使います。(DPあんまり使えないのでもしかしたらDPでもいけるかも)
DIM ALL$[0]
DEF DEL(A[],J)
　VAR L=LEN(A)-1
　DEM R$[0]
　FOR I=0 TO L
　　IF I!=J THEN
　　　PUSH R$,A[I]
　　ENDIF
　NEXT I
　RETURN R$
END
DEF DFS DIC$,STR$
　VAR L=LEN(DIC$)
　VAR I%
　PUSH ALL$,STR$
　FOR I%=0 TO L-1
　　PUSH ALL$,STR$+DIC$[I%]
　　DFS DEL(DIC$,I%),STR$+DIC$[I%]
　NEXT I%
END

(動作未確認)

あと文字の種類多いととんでもない時間かかります。
Out Of Memory出るかも。

あ、こういうことだと思いました。

DTC=4:DIM P$[DTC]
MAX=POW(2,DTC):DIM A$[MAX]
FOR I1=0 TO DTC-1
READ P$[I1]
NEXT
FOR I2=0 TO MAX-1
FOR I3=0 TO DTC-1
IF (I2 AND POW(2,I3))!=0 THEN A$[I2]=A$[I2]+P$[I3]
NEXT
? A$[I2]
NEXT

3DSが使えず空で打ってるのでミスとかあるかもです…

こういちさんのプログラムは例えば"ABCDEF"と"DEFABC"は別物として考える、
ジプッチャさんのプログラムは"ABCDEF"と"DEFABC"は同じものとして数える、ということですね。
しかし前者の場合例えばDATAが10個の時答えは9864100通りになりますが、
プチコンはそんなに計算できるのでしょうか...?
後者の場合は1024通りですが
(計算間違えてたらすみません)

二つ名メーカー？

対象の数が漠然としてるから分かりづらいだけで
例えば10個の文字列をDATAとして登録しておいて
再生成する文字列の構成要素に使えるのはそのうちの５つ以内ってルールを仮定してみると
10+10^2+10^3+10^4+10^5で111110通り
これを一般化して登録文字列の数をN、使える数をMとすると
N^1+N^2+…+N^M　通り
う〜ん…、気が遠くなりますね・・・

メモリの問題は、再生成された文字列は別スロットに随時書き出して
配列は組み合わせに使用する登録ワード格納用としてのみ使うとかすればクリアできるんじゃないんです？