Как ускорить код?
Там от "цикла в цикле" - одно название. Средняя длина вложенного цикла равна l/(l-1), а вовсе не k. То есть каждое новое размещение делается из предыдущего за амортизированное O(1)
Никак не ускорить. Во-первых, если вы со сгенерированными размещениями что-то делаете (хотя бы выводите), то сам код генерации уже не медленнее этого. Быстрее может быть только считать что вам там надо умно без генерации вообще.

Во-вторых, как вам уже сказали - амортизационно это все будет O(s). Потому что внутренний цикл делает "лишних" операций суммарно столько, сколько l-1 на конце всех размещений. Их 0 в l^(n-1)*(l-1) размещениях, 1 в l^(n-2)*(l-1), и т.д. если все это просуммировать, то результат будет меньше l^n - количества итераций внешнего цикла.