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

http://cppalgo.blogspot.com/2011/02/3.html

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

(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 ...) будет функция по результатам которой дальнейшая работа может быть остановлена.

google://lisp permutations
http://forum.codecall.net/classes-code-snippets/15479-lisp-permutations.html

Это не то

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

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

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

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

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

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
}

?

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

дык алгоритм, повторяй и все дела

Спасибо, мне такого не надо.

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> а в чем проблема? просвети

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

ааа, единицы у тебя не уникальные

друг, тебя ждет успех :)

http://www.linux.org.ru/jump-message.jsp?msgid=6292418&cid=6292457

Решение уже есть. Я изначально remove-duplicates не туда вписал и этого не заметил, поэтому решил что «придуманный» алгоритм не верен.

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

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

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

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

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

Кажется ты единственный кто не понял задачи.

неа :) см. ниже :)