Почему моя обратная функция меняет все мои пары, кроме одной? - PullRequest
Новая
       29

Почему моя обратная функция меняет все мои пары, кроме одной?

0 голосов
/ 09 марта 2020

т.е. мне дано это (все возможные комбинации для внесения изменений за 11): 

(list 1 1 1 1 1 1 1 5 5 5 5 1 1 1 10 10 10 1 1 25 25 25 25 25 25)

Мой код должен вернуть: 

((7 . 1) (4 . 5) (3 . 1) (3 . 10) (2 . 1) (6 . 25))

, чтобы он был более читабельным.

Однако возвращается: 

((7 . 1) (4 . 5) (1 . 3) (3 . 10) (2 . 1) (6 . 25))

Я не знаю, как изменить порядок ВСЕХ моих пар.

Это мой код: 

(define (rev pair) ;; function reverses a pair, not a list.
   (map (lambda (e) (cons (cdr e) (car e))) pair)) 
(define (rle coins)
  (if (null? coins)
      '()
      (let loop ((firsts (list (car coins)))
                 (but-firsts (cdr coins)))
        (if (or (null? but-firsts)
                (not (equal? (car firsts) (car but-firsts))))
            (rev (cons (cons (car firsts) (length firsts))
                       (rle but-firsts)))
            (rev (loop (cons (car but-firsts) firsts) (cdr but-firsts)))))))

Это мой тест: 

(rle (list 1 1 1 1 1 1 1 5 5 5 5 1 1 1 10 10 10 1 1 25 25 25 25 25 25))

Ответы [ 2 ]

0 голосов
/ 10 марта 2020

Во-первых, некоторое систематическое c тестирование (тестовые случаи должны быть систематическими c и как можно меньшими, не большими и произвольными): 

> (rle '(2))
'((1 . 2))
> (rle '(2 3))
'((1 . 2) (3 . 1))
> (rle '(2 3 4))
'((1 . 2) (3 . 1) (1 . 4))
> (rle '(2 3 4 5))
'((1 . 2) (3 . 1) (1 . 4) (5 . 1))
> (rle '(2 3 4 5 6))
'((1 . 2) (3 . 1) (1 . 4) (5 . 1) (1 . 6))

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

> (rle '(5 5 6))
'((5 . 2) (1 . 6))
> (rle '(5 5 6 6))
'((5 . 2) (6 . 2))
> (rle '(5 5 6 6 6))
'((5 . 2) (3 . 6))
> (rle '(5 6 6 6))
'((1 . 5) (6 . 3))

Когда элементы повторяются, порядок кажется немного непредсказуемым.

Давайте посчитаем, сколько раз вы rev каждый элемент, используя тройные элементы с счетчик как car: 

;; Flip the order of a pair.
(define (flip x)
  (cons (cdr x) (car x)))

;; Add one to the car of each element and flip its cdr.
(define (rev list)
  (map (lambda (x) (cons (+ 1 (car x)) (flip (cdr x)))) list))

(define (rle coins)
  (if (null? coins)
      '()
      (let loop ((firsts (list (car coins)))
                 (but-firsts (cdr coins)))
        (if (or (null? but-firsts)
                (not (equal? (car firsts) (car but-firsts))))
            (rev (cons (cons 0 (cons (car firsts) (length firsts)))
                       (rle but-firsts)))
            (rev (loop (cons (car but-firsts) firsts) (cdr but-firsts)))))))

Это создает список, который сообщает, сколько раз rev было применено к каждому элементу в результате. 

> (rle '(99))
'((1 1 . 99))
> (rle '(99 99))
'((2 99 . 2))
> (rle '(99 99 99))
'((3 3 . 99))
> (rle '(99 99 99 100))
'((3 3 . 99) (4 100 . 1))
> (rle '(99 99 99 100 100))
'((3 3 . 99) (5 2 . 100))

Как вы Можно видеть, что каждый элемент «переворачивался» много раз - по одному разу для каждого повторения.
Это происходит потому, что вы применяете rev к каждому частичному результату, а не только к окончательному списку.
Элементы, которые было перевернуто четное число раз "назад".

Теперь ваш пример ввода: 

> (rle (list 1 1 1 1 1 1 1 5 5 5 5 1 1 1 10 10 10 1 1 25 25 25 25 25 25))
'((7 7 . 1) (11 4 . 5) (14 1 . 3) (17 3 . 10) (19 2 . 1) (25 6 . 25))

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

Лучшее решение - построить ваши пары в том порядке, в котором вы хотите, чтобы вам не приходилось настраивать их впоследствии; реализация оставлена ​​как упражнение.
(Реализация - это очень незначительное изменение в вашей процедуре и удаление rev.)

0 голосов
/ 09 марта 2020

Почему бы не написать классическую рекурсивную функцию с хвостовым вызовом? Потому что мое мнение таково, что именованные циклы - это ужасные конструкции - непонятно для читателя. 

(define (rle coins (acc '()))
  (if (null? coins)
      (reverse acc)
      (rle (cdr coins)
           (if (and (not (null? acc)) (equal? (cdar acc) (car coins)))
               (cons (cons (+ 1 (caar acc)) 
                           (cdar acc))
                     (cdr acc))
               (cons (cons 1 (car coins))
                           acc)))))

Это правильно: 

(rle (list 1 1 1 1 1 1 1 5 5 5 5 1 1 1 10 10 10 1 1 25 25 25 25 25 25))
;; '((7 . 1) (4 . 5) (3 . 1) (3 . 10) (2 . 1) (6 . 25))
...