Ответ 1
Я сделаю это, построив минимальный дефинитивный конечный автомат для языка. Если вы начинаете с регулярного выражения, это можно сделать автоматически Thompson Construction, за которым следует построение подмножества и минимизация. См. Это описание, например.
С 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 и путем отсечения поиска при достижении пределов ресурсов.
редактировать
Вот пример Java-игры, в котором я жестко закодировал DFA для простых двоичных литералов с плавающей запятой с дополнительным знаком "минус". Это использует немного другую схему, чем псевдокод выше, чтобы получить строгий порядок сортировки вывода и разместить диапазоны символов.
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();
}
}