Функция Scheme / Racket insert -where с подсписками - PullRequest
Новая
       16

Функция Scheme / Racket insert -where с подсписками

0 голосов
/ 06 ноября 2018

Итак, я пытался решить эту проблему:

Учитывая элемент E и список L, вставьте E в каждую позицию в списке L (таким образом, результатом является список списков). Пример: (insert-everywhere 'a '(b c)) даст ((a b c) (b a c) (b c a))

Это достаточно просто, но в моей задаче есть еще одно условие, которое усложняет мне задачу - если элемент L является самим списком, то этот элемент также должен быть вставлен в каждую позицию в подсписке. Например:

(insert-everywhere 'd '(a (b c))) вернется: ((d a (b c)) (a d (b c)) (a (d b c)) (a (b d c)) (a (b c d)) (a (b c) d)).

Это код, который у меня есть (который я в основном поднял с здесь ): 

#lang racket
(define (insert-at pos elmt lst) 
 (if (empty? lst) (list elmt)
 (if (list? (car lst)) (insert-everywhere elmt (car lst))
 (if (= 1 pos)
  (cons elmt lst)
  (cons (first lst) 
        (insert-at (- pos 1) elmt (rest lst)))))))

(define (insert-everywhere sym lst)
  (remove-duplicates
    (map (lambda (i)
      (insert-at i sym lst))
        (range 1 (+ 2 (length lst))))))

где эта строка: (if (list? (car lst)) (insert-everywhere elmt (car lst)) должна обрабатывать подсписки, но она не работает. (Если я запускаю (insert-everywhere 'd '(a (b c))) с кодом выше, я получаю ((d a (b c)) (a (d b c) (b d c) (b c d))))

Если у кого-то есть предложения о том, как подойти к этому по-другому, я был бы рад услышать.

1 Ответ

0 голосов
/ 07 ноября 2018

Я бы не стал индексировать, потому что это очень неэффективно. Скорее поверните список ввода и постройте список от начала до конца, получая результаты в обратном порядке. У вас есть текущий список, в который вы добавляете элементы с помощью cons, который вы используете для добавления новых дополнений к результатам, и каждый уровень каждого существующего результата также получает один добавленный элемент.

В качестве параметров у вас есть состояние. Когда я делал ссылку, я использовал result и cur, и обычно моя итерация делалась так для (insert-everywhere 'd '(a b c)): 

lst     cur     results
(c b a) ()      ((d))
(b a)   (c)     ((d c) (c d))
(a)     (b c)   ((d b c) (b d c) (b c d))
()      (a b c) ((d a b c) (a d b c) (a b d c) (a b c d)))

Теперь добавление поддержки для подсписков просто делает с ними то же самое, а затем создает карту так, что вы создаете один результат для каждого подсписка в результате, добавляя cur в дополнение к добавлению его в качестве элемента.

Обратите внимание, что все новые результаты просто добавляются с добавленным вставленным элементом, и все остальные получают новый элемент во фронте, который является первым элементом ввода. cur будет расти и будет использоваться совместно, поэтому только элементы до вставленного элемента будут уникальными для этого подрезультата.

У меня есть работающая реализация, но преждевременно получать решение преждевременно. Повеселись.

...