LINUX.ORG.RU

[как?] алгоритм: перестановки без повторов


0

0

Subj

К примеру задана входная последовательность: 1 2 1

Надо получить все уникальные комбинации: (1 1 2) (1 2 1) (2 1 1)

Метод сгенерировать всё, а потом удалить повторы не подходит, т.к. на каждой итерации выполняются некоторая функция с сгенерированной последовательностью и по результатам этой функции дальнейшая генерация комбинаций может быть прервана.

На данный момент используется хэш (где комбинация — ключ) для проверки уникальности.

Есть ли более правильный метод генерации уникальных комбинаций?

★★★★★

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

(defun combinations (lst &optional res) 
(if (null lst)
        (format t "Out: ~{~a ~}~%" res)
        (loop for i in (remove-duplicates lst) do
              (combinations (remove i lst :count 1) (cons i res)))))

вместо (format ...) будет функция по результатам которой дальнейшая работа может быть остановлена.

sdio ★★★★★
() автор топика

Можно попробовать сгенерировать все комбинации в лексикографическом порядке. В С++ для этого есть метод next_permutation (я только не помню, работает ли он на множествах с одинаковыми элементами. В любом случае, разобравшись как он работает, его можно модифицировать и на случай множеств с одинаковыми элементами.

Zhenyok
()

Лексикографический перебор. next_permutation именно его юзает.

Brainerazer
()

Лексикографически перебрать – довольно просто.

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

            2112
           /    \
1122 - 1212      2121 - 2211
           \    /
            1221

Miguel ★★★★★
()

permn(1:3)

[[1]]
[1] 1 2 3

[[2]]
[1] 1 3 2

[[3]]
[1] 3 1 2

[[4]]
[1] 3 2 1

[[5]]
[1] 2 3 1

[[6]]
[1] 2 1 3

permn

function (x, fun = NULL, ...)
{
if (is.numeric(x) && length(x) == 1 && x > 0 && trunc(x) ==
x)
x <- seq(x)
n <- length(x)
nofun <- is.null(fun)
out <- vector(«list», gamma(n + 1))
p <- ip <- seqn <- 1:n
d <- rep(-1, n)
d[1] <- 0
m <- n + 1
p <- c(m, p, m)
i <- 1
use <- -c(1, n + 2)
while (m != 1) {
out[[i]] <- if (nofun)
x[p[use]]
else fun(x[p[use]], ...)
i <- i + 1
m <- n
chk <- (p[ip + d + 1] > seqn)
m <- max(seqn[!chk])
if (m < n)
d[(m + 1):n] <- -d[(m + 1):n]
index1 <- ip[m] + 1
index2 <- p[index1] <- p[index1 + d[m]]
p[index1 + d[m]] <- m
tmp <- ip[index2]
ip[index2] <- ip[m]
ip[m] <- tmp
}
out
}

psv1967 ★★★★★
()

У Кнута про перестановки много есть.

urxvt ★★★★★
()
Ответ на: комментарий от sdio

Generates all permutations of the elements of x, in a minimal- change order. If x is a positive integer, returns all permutations of the elements of seq(x). If argument «fun» is not null, applies a function given by the argument to each point. "..." are passed unchanged to the function given by argument fun, if any.

Reingold, E.M., Nievergelt, J., Deo, N. (1977) Combinatorial Algorithms: Theory and Practice. NJ: Prentice-Hall. pg. 170.

psv1967 ★★★★★
()
Ответ на: комментарий от psv1967

psv1967> а в чем проблема? просвети

В подаче материала. Ты бы еще бинарник дал и сказал: «запускай и все дела!»

sdio ★★★★★
() автор топика
Ответ на: комментарий от psv1967

Я понимаю, что большинство технарей косноязычны, но если ты пришел учить, то делай это правильно, тем более тебе никто в спину не дышит.

sdio ★★★★★
() автор топика
Ответ на: комментарий от sdio

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

я привел тебе код функции на каждую комбинацию которой применяется функция и возвращается список.

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

впрочем мы на лоре, все в порядке :)

psv1967 ★★★★★
()
Ответ на: комментарий от sdio
(asdf:operate 'asdf:load-op 'alexandria)

(let ((hash (make-hash-table :test 'equal)))
  (catch 'end
    (alexandria:map-permutations
     (alexandria:named-lambda permutation-handler (item)
       (multiple-value-bind (value present-p) (gethash item hash)
         (unless present-p
           (when (you-predicate item)
             (throw 'end))
           (set (gethash item hash)
                (you-permutation-handler item))))))
    (you-sequence))
  (alexandria:hash-table-values hash))
archimag ★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.