Supponiamo di avere una lunga pila di numeri. C'è un altro stack intermedio e uno stack di destinazione da restituire alla fine. Le sole due operazioni consentite sono il trasferimento della cima del vecchio stack all'elemento superiore dello stack intermedio e il trasferimento dell'elemento superiore dello stack intermedio nella parte superiore del nuovo stack. Elenca tutti i possibili nuovi stack che possono essere prodotti, supponendo che lo stack originale sia esaurito.
Uso Racket / Scheme. Le soluzioni puramente funzionali sono più preferibili;)
Qualche idea su come farlo? Con alcuni handwaving sembra che la funzione seguente preveda correttamente se una certa sequenza di output è possibile, dato che la sequenza di input è ordinata da piccola a grande:
(define (possible? lst)
(match lst
[(cons a b)
(and (if (andmap (λ(x) (< x a)) b) (sorted? b) #t) (possible? b))]
[x #t]))
quindi posso semplicemente generare tutte le permutazioni della lista di input e filtrare quelle impossibili.
Sembra che ci dovrebbe essere una soluzione più elegante, che preferibilmente utilizza ricorsione e programmazione funzionale invece di loop e mutazione annidate.