これは、言語の最小の決定論的有限オートマトンを構築することで行います。正規表現から始めている場合、これはトンプソンの構築とそれに続くサブセットの構築と最小化によって自動的に行うことができます。たとえば、この説明を参照してください。
DFA があれば、次のようなアルゴリズムを使用できます。
Let P = { < START, [""] > } be a set of pairs <State, list of strings>
for n = 0, 1, ... Max
Let P' = {} be a new set
while P is not empty
Remove the pair <s, L> from P
For each transition s -- c --> t in alpha order of c
if t is an accepting state,
output l + c for each string l in L
put <t, L + c> in P' (** i.e. append c to each string in L)
end
Set P = P'
end
**重複が簡単に発生する可能性があるため、マークされたステップは真のセット挿入である必要があることに注意してください。
これはコアアルゴリズムです。P出力の長さに応じて指数関数的に大きくなる可能性がありますが、これは将来の出力文字列のすべての可能性を追跡するための代償にすぎません。あなたが言及した順序/サイズ/スペースの制約は、リストLでソートされた順序を維持し、リソースの制限に達したときに検索を切断することで確保できます。
編集
これは、オプションのマイナス記号を使用して、単純なバイナリ浮動小数点リテラルの DFA をハードコーディングしたおもちゃの Java の例です。これは、上記の疑似コードとは少し異なるスキームを使用して、厳密にソートされた出力順序を取得し、文字範囲に対応します。
import java.util.Comparator;
import java.util.TreeSet;
public class Test{
public static class DFA {
public static class Transition {
final int to;
final char lo, hi; // Character range.
public Transition(int to, char lo, char hi) {
this.to = to;
this.lo = lo;
this.hi = hi;
}
public Transition(int to, char ch) {
this(to, ch, ch);
}
}
// transitions[i] is a vector of transitions from state i.
final Transition [] [] transitions;
// accepting[i] is true iff state i is accepting
final boolean [] accepting;
// Make a fresh immutable DFA.
public DFA(Transition [] [] transitions, boolean [] accepting) {
this.transitions = transitions;
this.accepting = accepting;
}
// A pair is a DFA state number and the input string read to get there.
private static class Pair {
final int at;
final String s;
Pair(int at, String s) {
this.at = at;
this.s = s;
}
}
// Compare pairs ignoring `at` states, since
// they are equal iff the strings are equal.
private Comparator<Pair> emitOrder = new Comparator<Pair>() {
@Override
public int compare(Pair a, Pair b) {
return a.s.compareTo(b.s);
}
};
// Emit all strings accepted by the DFA of given max length.
// Output is in sorted order.
void emit(int maxLength) {
TreeSet<Pair> pairs = new TreeSet<Pair>(emitOrder);
pairs.add(new Pair(0, ""));
for (int len = 0; len <= maxLength; ++len) {
TreeSet<Pair> newPairs = new TreeSet<Pair>(emitOrder);
while (!pairs.isEmpty()) {
Pair pair = pairs.pollFirst();
for (Transition x : transitions[pair.at]) {
for (char ch = x.lo; ch <= x.hi; ch++) {
String s = pair.s + ch;
if (newPairs.add(new Pair(x.to, s)) && accepting[x.to]) {
System.out.println(s);
}
}
}
}
pairs = newPairs;
}
}
}
// Emit with a little DFA for floating point numbers.
public void run() {
DFA.Transition [] [] transitions = {
{ // From 0
new DFA.Transition(1, '-'),
new DFA.Transition(2, '.'),
new DFA.Transition(3, '0', '1'),
},
{ // From 1
new DFA.Transition(2, '.'),
new DFA.Transition(3, '0', '1'),
},
{ // From 2
new DFA.Transition(4, '0', '1'),
},
{ // From 3
new DFA.Transition(3, '0', '1'),
new DFA.Transition(4, '.'),
},
{ // From 4
new DFA.Transition(4, '0', '1'),
}
};
boolean [] accepting = { false, false, false, true, true };
new DFA(transitions, accepting).emit(4);
}
public static void main (String [] args) {
new Test().run();
}
}