swizard (swizard) wrote,
swizard
swizard

Category:
  • Location:
  • Music:

Зодачкоъ

Очередная проблемка / вопросец, ок? =)

Задачка, скорее, олимпиадная по духу, но неожиданно понадобилась на практике. Итак, формальное видоизмененное условие: предположим, лежит на полу куча монеток. Можно взять любые N штук. Так вот, надо получить все возможные варианты взятия :) Типа

Лежало [1, 5, 10, 50], можно брать по N=3
Вариант 1: [1, 5, 10]
Вариант 2: [1, 5, 50]
Вариант 3: [1, 10, 50]
Вариант 4: [5, 10, 50]

Лежало [1, 5, 10, 50], можно брать по N=2
Вариант 1: [1, 5]
Вариант 2: [1, 10]
Вариант 3: [1, 50]
Вариант 4: [5, 10]
Вариант 5: [5, 50]
Вариант 6: [10, 50]

Признаюсь честно, я с ней тупил весьма долго :) В итоге родил вчера в метро что-то кривое c множественной рекурсией =) но хочу грамотного решения :)

Мое решение (scheme):
(define (perm-list l n)
  (cond
   ((or (< (length l) n) (<= n 0)) '())
   ((= n 1) l)
   ((= n 2) (perm-pairs l))
   (else
    (let ((h (car l)))
      (append
       (map (lambda (rl) (cons h rl))
            (perm-list (cdr l) (- n 1)))
       (perm-list (cdr l) n))))))

(define (perm-pairs l)
  (if (null? l) '()
      (append
       (map (lambda (el) (list (car l) el)) (cdr l))
       (perm-pairs (cdr l)))))


| (perm-list '(1 5 10 50) 3)
((1 5 10) (1 5 50) (1 10 50) (5 10 50))

| (perm-list '(1 5 10 50) 2)
((1 5) (1 10) (1 50) (5 10) (5 50) (10 50))
Tags: code
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 24 comments