Взял числа от 1 до 9 (без перестановок), четыре арифметические операции (+, -, *, /) и построил декартов квадрат: все возможные размещения операций на все возможные расстановки скобок. И этот сучок не влазит в 32 гига рамы! Не пойму, мощность квадрата = C_8 * 4^8 = 93'716'480 ~ 100 млн. Это что, одна формула занимает больше 3*10^10 / 10^8 = 300 байт?

Формула - во вложенном списке, т.е. 9 + 8 = 17 элементов. Ну, добавим терминаторы +8 = 25. Это что, по 12 байт на элемент? Что за оверхед. Ну, возможно racket лочит память в стиле коллекций дотнета, c выравниванием до 2^n. Вполне возможно, если хранить списки в массивах.

Ладно, хуй с ним, снял лимит по памяти. Тот елозил свопом всю ночь, но так и не доелозил. А для 8 элементов за 2 минуты считается, и занимает 5-6 Гб. Это C_7 * 4^7 = ~7 млн формул. Ну, понятно, что по мегабайту такие маленькие списки не могут занимать, просто сборки мусора не было. Но всё равно, слишком много, мне кажется.

Теперь два-три варианта вижу, или переложить алгоритм на ... Немерле? Хаскелл бы хорошо, но думаю, там по памяти не лучше, чем Схема будет. Или проиндексировать квадрат и оставлять только индексы. Размещения индексируются естественным образом по два байта (4^8 = 2^16). Для скобок (двоичных деревьев с 9 листьями) естественной нумерации не знаю, но можно индексировать через рекурсию, которой они строятся (она ведь детерминированная). Или ещё проще, вдоль одного измерения квадрата - индексировать, вдоль второго - нет. Наверное, так и сделаю.

А у бразильца-то было 6 операций в конце, а не 4. Так что мощность будет C_8 * 6^8 = ~2.4 млрд, однако. И хотя, если делать то же, что и бразилец (поиск разложения числа, анализ лакун), то прямое произведение хранить не нужно, и достаточен лишь перебор, но я хочу построить 3-мерный график на этом квадрате и, вообще, посмотреть на все возможные способы разложения, пересчитать варианты и т. д. Здесь, однако, надо начинать с упрощённых случаев.

((+ 1 (+ 2 3))
 (* 1 (+ 2 3))
 (- 1 (+ 2 3))
 (/ 1 (+ 2 3))
 (+ 1 (* 2 3))
 (* 1 (* 2 3))
 (- 1 (* 2 3))
 (/ 1 (* 2 3))
 (+ 1 (- 2 3))
 (* 1 (- 2 3))
 (- 1 (- 2 3))
 (/ 1 (- 2 3))
 (+ 1 (/ 2 3))
 (* 1 (/ 2 3))
 (- 1 (/ 2 3))
 (/ 1 (/ 2 3))
 (+ (+ 1 2) 3)
 (* (+ 1 2) 3)
 (- (+ 1 2) 3)
 (/ (+ 1 2) 3)
 (+ (* 1 2) 3)
 (* (* 1 2) 3)
 (- (* 1 2) 3)
 (/ (* 1 2) 3)
 (+ (- 1 2) 3)
 (* (- 1 2) 3)
 (- (- 1 2) 3)
 (/ (- 1 2) 3)
 (+ (/ 1 2) 3)
 (* (/ 1 2) 3)
 (- (/ 1 2) 3)
 (/ (/ 1 2) 3))

(define (formulae variables)
  (define (split-and-recombine position)
    (define-values (left right) (split-at variables position))
    (flatten-unary-subtrees
     (cartesian-product (formulae left) (formulae right))))
  (if ((length variables) . < . 3)
      (list variables)
      (append*
       (map split-and-recombine
            (numbers 1 ((length variables) . - . 1))))))